Sudoku

[lpetrich]

Sudoku is a puzzle game where one puts numbers from 1 to 9 in each cell of a 9*9 grid, subject to these constraints:

Each row and each column must contain only one each of the numbers.

The grid is divided into a 3*3 grid of 3*3 blocks or boxes, each one containing only one each of the numbers.

Rows, columns, and blocks are sometimes collectively known as houses.

One starts with an initial position where some of the grid cells have numbers in them, and one tries to find the remaining ones.


There are numerous variations of this puzzle game. One is to use other symbols. Picture Sudoku has a variety of sets of them, like the Arabic version of Arabic numerals, Roman ones, Chinese ones, colors, and pictures of animals, fruits, flowers, and scenery.

Another is to use a different-sized board with different-sized blocks. Like use m*n blocks arranged in a n*m grid in a (m*n) * (m*n) grid of cells where one places symbols from a set of (m*n) of them.

I've also found multiple overlapping boards and irregular-shaped blocks.


I've found a lot of strategies for solving sudoku boards, and I've implemented some of them in a MacOS Cocoa app that I've written.

 

[lpetrich]

There are a variety of solution techniques for Sudoku, from the elementary to the advanced.

It is often helpful to note what a cell may contain, even if it is more than one symbol. For paper, one can write with a pencil, since you will likely want to erase symbols as the solution proceeds, and some apps and sites let you make note of multiple possible solutions in their displayed boards.

So here goes.

The simplest solution is a naked or open single. If there is some cell that has only one possible symbol in it, then that symbol is the cell's solution, and one can clear it from possible solutions in every other cell of every house that that cell is in.

After that is a naked double. That is two cells in some house that share their two possible solutions. One cannot be sure which symbol is the solution for which cell, but one can clear those symbols from the rest of the cells in that house. Thus, if one has two cells in a house with 1 2, 1 2, one doesn't know which cell gets 1 and which one gets 2, but one can clear 1 and 2 from the rest of those cells' house.

A naked triple is similar, but each cell does not have to contain all three of the symbols that they share. One can have 1 2, 1 3, 2 3 for instance.

One can continue further with naked quadruples and further.

Next up is a hidden single. If some symbol in some cell is the only symbol present in a house with that cell, then that symbol is that cell's solution.

Related is a hidden double. As with naked doubles, one cannot be sure of which symbol goes where, but one can clear out all the other symbols in a house. Thus, if one has 1 2 3, 1 2 4 5 in some house where 1 and 2 are present nowhere else in that house, one can clear the 3 and the 4 and 5, giving 1 2, 1 2.

Hidden triples are similar, and as with naked triples, the cells may have only some of the shared symbols. 1 2 4, 1 3 5 6, 2 3 becomes 1 2, 1 3, 2 3 by clearing the 4 and the 5 and the 6.

One can continue further with hidden quadruples and further.

 

[lpetrich]

An additional technique is intersection exclusion.

Imagine that some symbol is found in the intersection of houses H1 and H2, but not in the rest of H1. Then it will not be present in the rest of H2.

That is most useful for the intersections of blocks and lines, since two parallel lines will not intersect and two perpendicular ones intersect in one cell, thus being a hidden-single case.


Here are some pages on solution techniques:

• Solving technique - Sudopedia
• Sudoku - Basic Techniques and Sudoku - Advanced Techniques
• Sudoku Techniques – Sudoku of the Day
• Sudoku Assistant -- Solving Techniques
• Sudoku Tips - Sudoku Puzzles Solving Techniques

They can be very complicated, and I came to understand some of them only recently.

For X-wing, consider some symbol x that is possible for the intersections of two rows r1 and r2 with two columns c1 and c2. If x is not present elsewhere in r1 and r2, it will not be present elsewhere in c1 and c2. Likewise, if x is not present elsewhere in c1 and c2, it will not be present elsewhere in r1 and r2.

A version with 3 rows and 3 columns is a swordfish, a version with 4 rows and 4 columns a jellyfish, and a version with 5 rows and 5 columns a squirmbag. A variation on the swordfish and higher is a finned fish, and something similar to the X-wing is the XY-wing.

There are other advanced techniques, like forcing chains, that I won't get into.

 

[lpetrich]

Sudoku boards are special cases of "Latin squares", named from mathematician Leonard Euler liking to demonstrate them with Roman / Latin letters. -  Latin square

For a Latin square, the houses are rows and columns - no block constraints. Each row has one of each symbol, and likewise for each column. Every row and every column thus contains a permutation of the symbols.

A002860 - OEIS - Number of Latin squares of order n; or labeled quasigroups.
1, 2, 12, 576, 161280, 812851200, 61479419904000, 108776032459082956800, 5524751496156892842531225600, 9982437658213039871725064756920320000, 776966836171770144107444346734230682311065600000

One can sort them so that the first members of each row and each column are in sorted order. For n*n Latin squares, this reduces their number by n! * (n-1)!

Equivalence by row permutation and column permutation:
A000315 - OEIS - Number of reduced Latin squares of order n; also number of labeled loops (quasigroups with an identity element) with a fixed identity element.
1, 1, 1, 4, 56, 9408, 16942080, 535281401856, 377597570964258816, 7580721483160132811489280, 5363937773277371298119673540771840

Equivalence by row permutation, column permutation, and symbol permutation:
A040082 - OEIS - Number of inequivalent Latin squares (or isotopy classes of Latin squares) of order n.
1, 1, 1, 2, 2, 22, 564, 1676267, 115618721533, 208904371354363006, 12216177315369229261482540

More complicated: turn each Latin square as a list of (row index, column index, value at those indices as 1 to n) triples. Add to the previous permutations all permutations of these types of values. Transpose is row <-> column, for instance.
A003090 - OEIS - Number of species (or "main classes" or "paratopy classes") of Latin squares of order n.
1, 1, 1, 2, 2, 12, 147, 283657, 19270853541, 34817397894749939, 2036029552582883134196099

Let's see what the smallest reduced ones are.

1:
1

2:
1 2
2 1

3:
1 2 3
2 3 1
3 1 2

4:
1 2 3 4   1 2 3 4   1 2 3 4   1 2 3 4
2 1 4 3   2 1 4 3   2 3 4 1   2 4 1 3
3 4 1 2   3 4 2 1   3 4 1 2   3 1 4 2
4 3 2 1   4 3 1 2   4 1 2 3   4 3 2 1

In the 4*4 reduced Latin squares, the second, third, and forth ones are equivalent by symbol permutation.

One can generalize to more dimensions.

A098679 - OEIS - Total number of Latin cubes of order n.
1, 2, 24, 55296, 2781803520, 994393803303936000

A098843 - OEIS - Number of reduced Latin cubes of order n.
1, 1, 1, 64, 40246, 95909896152

The first three reduced Latin cubes:

1:
1

2:
1 2   2 1
2 1   1 2

3:
1 2 3   2 3 1   3 1 2
2 3 1   3 1 2   1 2 3
3 1 2   1 2 3   2 3 1

Notice that each slice is a Latin square.

 

[Rhea]

I enjoy sudoku.

One of the rules I find often useful is what the Mensa book calls “Gordian Logic.”

This works where if you have 4 cells at the corners of a square (floating, i.e. anywhere in or across houses) such that there is one pair in one column and another pair in another colum, however far apart, that ALSO exist in shared rows (hence picture the corners of a square.)

And then if three of those cells hold identical naked doubles and the fourth holds the digits in the double PLUS at least one different possibility.

Then you may conclude that that fourth square CANNOT be either of the naked double numbers and those can be erased as possibilities.

The logic is that if the four corners of a square hold the same two numbers, then it doesn’t matter which of the two is in which square and this cannot be because by definition the puzzle has one and only one solution.

 

[lpetrich]

What's a quasigroup? That's an abstract-algebra entity with a binary operation where division is well-defined.

For every a and b, there is a unique x and y such that
a * x = b
y * a = b
x and y need not be distinct.

A quasigroup's multiplication table will be a Latin square.

A loop is a quasigroup with an identity element. Calling it e, for every x, x * e = e * x = x

Quasigroups and loops need not have the associative property.

A binary operation with that property is a semigroup. If it also has an identity, it is a monoid. If it has both division and an identity, it is a group.

A binary operation with a set that it operates on is sometimes called a magma. We have two routes to groupishness:

Magma - associativity - Semigroup - identity - Monoid - division - Group
Magma - division - Quasigroup - identity - Loop - associativity - Group

 

[lpetrich]

I enjoy sudoku.

One of the rules I find often useful is what the Mensa book calls “Gordian Logic.”

This works where if you have 4 cells at the corners of a square (floating, i.e. anywhere in or across houses) such that there is one pair in one column and another pair in another colum, however far apart, that ALSO exist in shared rows (hence picture the corners of a square.)

And then if three of those cells hold identical naked doubles and the fourth holds the digits in the double PLUS at least one different possibility.

Then you may conclude that that fourth square CANNOT be either of the naked double numbers and those can be erased as possibilities.

The logic is that if the four corners of a square hold the same two numbers, then it doesn’t matter which of the two is in which square and this cannot be because by definition the puzzle has one and only one solution.

That's also called the unique rectangle: Sudoku - Unique Rectangle

It assumes that a solution will be unique.

Let's say that the corners have
12, 12
12, 123

If we eliminate the 3, we get
12, 12
12, 12

This has solutions
1, 2
2, 1
and
2, 1
1, 2

So we keep the 3. This also works for more:
12, 12
12, 1234

We keep the 34 as possible solutions 3, 4

 

[lpetrich]

Let's consider what sorts of symmetries a solution can have. For a square, it's rotation by 0d, 90d, 180d, and 270d in some direction, and axial and diagonal reflections. Axial = horizontal and vertical.

Rotation by 90d / 270d will move each corner to a neighboring one, and the initial and final positions will be on some line (row or column). The sudoku problem statement thus rules out such rotations. Axial reflections make initial and final positions share a line, and diagonal reflections make some initial positions share a block. Thus, the only possible symmetry is 180d rotation.


Solutions can be related by permutations of rows in each band (row of boxes), permutations of bands, permutations of columns in each stack (column of boxes), permutations of stacks, permutations of symbols, and for square boxes, diagonal reflections.

 Mathematics of Sudoku has the numbers for how many solutions:

• 2*2 = 4 -- 288 -- 3 -- 2
• 2*3 = 6 -- 28,200,960 -- 49
• 2*4 = 8 -- 29,136,487,207,403,520 -- 1,673,187
• 3*3 = 9 -- 6,670,903,752,021,072,936,960 -- 10,945,437,157 -- 5,472,730,538
• 2*5 = 10 -- 1,903,816,047,972,624,930,994,913,280,000 -- 4,743,933,602,050,718
• 3*4 = 12 -- 81,171,437,193,104,932,746,936,103,027,318,645,818,654,720,000
• 2*6 = 12 -- 8,296,278,920,738,107,863,746,324,732,012,492,486,187,417,600,000

The first numbers are the block dimensions and the side length. The next ones are: total numbers of positions, total number of equivalent positions without diagonal reflections, and for square blocks, that number with diagonal reflections.

A 1*n sudoku board is essentially a Latin square, so one can carry over the Latin-square numbers in that case.