Latin Squares are mathematical puzzles that require you to fill out a grid of cells in a particular manner: Each column and each row must never repeat a number. If the grid is 4x4, than all numbers between 1 and 4 must be used in each row and column.
There is a large number of puzzles similar to Latin Squares that give you a set of cells and require you to fill them out according to particular rules. This entire family of puzzles belongs to an even larger family of problems known as exact hitting set problems.
Once you translate your puzzle into an exact hitting set problem, you can begin using well known algorithms to analyze them. (For example, Dancing Links and Algorithm X.) The giant constraint matrices can be hard to grok so I created three visualizations of a 4x4 Latin Square. All three are linked to the same model — hovering over a cell in one will show the same cell in each of the others.
The standard representation of a Latin Square is the 4x4 grid. It has been snapped to the top left for visibility. Click to cycle through guesses for a particular cell — if you end up with an invalid combination it will highlight the problem. Hovering will highlight row and column relationships.
The first row and column are filled out with
1 2 3 4 in order to limit the puzzle to its
reduced
form.
This hive plot shows each cell/guess combination as its own node. Each axis is one cell and the nodes along the line represent guesses for that cell. Grey nodes are still valid and invalid options are empty. Hover to highlight row, column and guess relationships.
The colored links represent the four distinct solutions remaining for the Latin Square. As you fill out the Latin Square it will hide the elminated solutions — you can also hover over a node to only show remaining solutions that contain that cell/guess pair.
This matrix shows all constraints and their relationships.
These represent the information fed into Algorithm X. A black square is a
recorded guess; a grey square is still a valid potential guess; white
squares with borders are no longer valid but could be if we had a different
state in the square. A white square with no border is never considered by
the algorithm. (For instance, R1C1#1 and R1#2 are
fundamentally incompatible constraints.)
Hovering on a square will show the same row, column and guess
relationships as the other visualizations. Each cell/guess combination
matches exactly one row constraint (e.g., R1C1#1 and three
column constraints (e.g., R1#1, C1#1 and
R1C1.)
While nothing here explicitly explains how Algorithm X works, the source for this page does contain a full implementation of the solver if you are curious about it. A better visualization of the algorithm itself deserves its own page.