Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Representation of a Sudoku
In the paclet Sudoku Hints, a sudoku is given as a Sudoku expression. Knowledge about the structure of a Sudoku expression is not necessary, we have tools for entering a sudoku. This technical note provides more information on the Sudoku expression.
Sudoku puzzles are normally presented as a picture. This is a standard sudoku, with nine 3x3 blocks:
Contents cannot be rendered at this time; please try again later or download this notebook for full functionality »
The nine blocks are not necessarily 3x3-squares. This is a so called jigsaw sudoku:
Contents cannot be rendered at this time; please try again later or download this notebook for full functionality »
We may also have extra blocks. This is a diagonal sudoku:
Contents cannot be rendered at this time; please try again later or download this notebook for full functionality »
It requires that not only in the nine rows, columns and regular blocks, but also in the two extra blocks, the diagonals, all numbers 1, …, 9 will appear.
Sudoku's can be combined to multi sudoku's. Here we have a combination of a jigsaw and a diagonal sudoku:.
Contents cannot be rendered at this time; please try again later or download this notebook for full functionality »
Not rarely we see the X-sudoku, consisting of 5 standard sudoku's in the form of an X, overlapping each other in one of the blocks.
Contents cannot be rendered at this time; please try again later or download this notebook for full functionality »
Many other variants exist.
The goal of the sudoku is to place in each of the cells one of the numbers 1, 2, …, 9 such that in each row, column and block all numbers are different, or equivalent that in each row, column and block all numbers 1, …, 9 will appear.
Like in the examples above, often in some of the cells the number is already given. These numbers are called the clues of the sudoku. That is a bit misleading. They are not giving us a hint on how to solve the sudoku, but limit the number of solutions of the puzzle, hopefully so strong that the sudoku has a unique solution.
The rows, columns and blocks are just groups of nine cells. Therefore:
A sudoku is a list of groups of nine cells. The problem is to assign to each cell one of the numbers 1, …, 9 such that in all groups the numbers will 1, …, 9 will appear.
The first conclusion from this abstract formulation is that there is no difference at all between the various sudoku's. The standard sudoku and the jigsaw sudoku have 27 groups with 81 cells. A diagonal sudoku has 29 groups, also with 81 cells. The X-sudoku has 131 groups with 369 cells. In this paclet, all functions are implemented in terms of groups and therefore all functions will automatically work for all sorts of sudoku's.
The second conclusion is that sudoku puzzles exist that are not so easily given by a picture as above. How would you draw a sudoku that consists of two groups that intersect in three cells?
The simplest sudoku is a sudoku of 9 cells and one group. All solutions are the permutations of 1, …, 9 and we need to give 8 clues for making the solution unique.
Now we turn to representing a sudoku in a Mathematica expression.
Since we want to be able to reconstruct the picture of the sudoku, we have to store more information than only the groups. All pictures of a sudoku are grids, and for being able to draw the sudoku, we have to include the size of the sudoku, the number of rows and columns. The cells of the grid are numbered row bij row from the upper left point of the grid to the lower right point of the grid. Given the size, for each cell now we know where to draw it.
In a picture, the groups are the rows, the columns and the blocks. Rows and columns normally appear as rows and columns of a subsudoku, i.e. the rows and the columns of a 9x9 square in the grid given by the upperleft cell of that square. That upperleft cell is called a rowcolposition, it determines 9 rows and 9 columns.
Similarly, normally the blocks are 3x3 squares of the subsudokus. If so, we call the upper left cell of that subsudoku a blockposition. It yields 9 disjoint 3x3 groups in the 9x9 square of the subsudoku.
The sudoku may have other groups. For these, we have two containers: outlinedgroups and coloredgroups. The difference is only the way they are drawn: an outlined group are drawn with a line around the cells, such as in the jigsaw sudoku, and a colored group is shown by giving the cells of the group a color, such as the diagonals in the diagonal sudoku.
Of course, besides the groups, we need an administration of the values of the cells. When we have a cell in which we did not yet place a number, we can place in that cell only the numbers that have not been placed in other cells of the groups to which our cell belongs, because of all placed numbers in a group have to be different. We call these numbers the candidates in that cell. The administration of the placed numbers and the candidates is done in an association called numbers. The keys of that association are the cell numbers. For a placed number n, the value is the list {n}. When we have candidates, the value is a list starting with 0, followed by the candidates.
Moreover, we need to store parameters for drawing the picture, such as the cell size, whether or not to include the candidates, etc.
A Sudoku expression has one argument, the data of the sudoku. That is an association with four keys: the numbers and the groups, that form the actual sudoku, info for being able to compute the groups and displayoptions. Let us inspect some examples.
In[1]:=
Needs["FredSimons`SudokuHints`"]
In[2]:=
sud=
["M7O7QGHBd@vQs#JFraBhyawl88r#D!nPO34vrjSODi||||v1X6ibxszaEMven0GdI524QPixLTK"]
| SudokuFromString |
Out[2]=
Contents cannot be rendered at this time; please try again later or download this notebook for full functionality »
In[3]:=
sud〚1〛
Out[3]=
This is a diagonal sudoku. The groups can be computed from the info. We have 9 rows and columns, as given by the key rowcolpositions, 9 3x3 blocks as given by the key blockpositions, no further outlined groups and two colored groups, the diagonals.
A considerably more complicated sudoku:
In[4]:=
sud=
["ayIClVvO9MBpE7sDV#Z75Vt%37esuHdGVF5emG@y1KKM6RKxuFJ339ZC$2mqNgZ3GVbBQiAQpzJIzGHXG#||2IgAkmC#pr|2g7vNNk7Zd&NL#qABGY&AORlGxQ12@Upf@Q#U4Cv1Lar0kiRHRGI%8jCHYNRcQ%kGS%ZvFxvcY1Ra!0bfm@e8VtCR15biNnRws5UCtdT#pUqkDJsiBJtwKH5c8luicZIt4D8acny%LJ!Yft|2cPv$LawfHKQ7tt%TFCcLAacu%#4d1u@ljuDJEQ@"]
| SudokuFromString |
Out[4]=
Contents cannot be rendered at this time; please try again later or download this notebook for full functionality »
It consists of a jigsaw and a diagonal sudoku. We have two squares with 9 rows and 9 columns, as seen in rowcolpositions. Standard blocks are only in the second sudoku, as we see in the value of blockpositions. The cages of the jigsaw sudoku are found in outlinedgroups and the two diagonals in coloredgroups.
The next command generates a sudoku that consists only of 9 rows and 9 columns. All other data are added automatically:
It is a latin square. We can find solutions:
We can construct and solve the simplest sudoku: