After each move, the Solver stores certain information about the current state of the grid in various 'state grids', which - as of Release 1.19 - the user is free to browse through the 'Copy' button. (The grids cannot be accessed from the command-line Solver as their calculation involves a considerable time penalty and the command-line Solver has been optimized to solve quickly rather than to produce helpful output). The state grids should prove informative and will be helpful for users who wish to discuss difficult positions on web-based forums.
The Solver uses four types of state grid:
The state grids presented on this page are associated with the following position:
. 8 . | . . . | 6 1 . 1 . . | . 9 . | 2 . . 2 . . | . . 5 | . . 4 -------+-------+------ 9 . . | . . . | . 7 . . . . | 3 2 6 | . . . . 4 . | . . . | . . 1 -------+-------+------ 6 . . | 8 . . | . . 3 . . 3 | . 1 . | . . 5 . 1 7 | . . . | . 9 .
The Cell State state grid records the possible values that remain for each cell on the grid. The values are displayed separated by the symbol '|'.
3|4|5|7 8 4|5|9 | 2|4|7 3|4|7 2|3|4|7 | 6 1 7|9
1 3|5|6|7 4|5|6 | 4|6|7 9 3|4|7|8 | 2 3|5|8 7|8
2 3|6|7|9 6|9 | 1|6|7 3|6|7|8 5 | 3|7|8|9 3|8 4
------------------------------+------------------------------+---------------------------
9 2|3|5|6 1|2|5|6|8 | 1|4|5 4|5|8 1|4|8 | 3|4|5|8 7 2|6|8
5|7|8 5|7 1|5|8 | 3 2 6 | 4|5|8|9 4|5|8 8|9
3|5|7|8 4 2|5|6|8 | 5|7|9 5|7|8 7|8|9 | 3|5|8|9 2|3|5|6|8 1
------------------------------+------------------------------+---------------------------
6 2|5|9 2|4|5|9 | 8 4|5|7 2|4|7|9 | 1|4|7 2|4 3
4|8 2|9 3 | 2|4|6|7|9 1 2|4|7|9 | 4|7|8 2|4|6|8 5
4|5|8 1 7 | 2|4|5|6 3|4|5|6 2|3|4 | 4|8 9 2|6|8
The Number State state grid records the cells that could possibly be occupied by a given value. Consider the following example for the value '5':
Value 5: ? . ? | . . . | . . . . ? ? | . . . | . ? . . . . | . . 5 | . . . ----------+----------+--------- . ? ? | ? ? . | ? . . ? ? ? | . . . | ? ? . ? . ? | ? ? . | ? ? . ----------+----------+--------- . ? ? | . ? . | . . . . . . | . . . | . . 5 ? . . | ? ? . | . . .
The grid immediately shows that a '5' must occupy the cell (2,8), as that is the only possible candidate cell for the value in Box [1,3].
The Neighbour State state grid is used by the Guess and Composer algorithms to estimate how much new information would be gleaned if some given move were made. Essentially, the grid records the number of dots (see the Number State grid above) that appear in the row, column and box associated with each cell that contains a question mark. A low score indicates that a lot would be learnt by that move - conversely, a high score indicates that little would be learnt.
For instance, in the following excerpt, the cell (6,3) has a score of 7 because there are dots in the cells (6,2), (6,6), (6,9), (3,3), (8,3), (9,3) and (4,1).
Value 5: 14 21 13 | 21 21 21 | 21 21 21 21 13 12 | 21 21 21 | 21 16 21 21 21 21 | 21 21 21 | 21 21 21 ----------+----------+--------- 21 9 8 | 13 12 21 | 12 21 21 10 10 9 | 21 21 21 | 13 12 21 8 21 7 | 12 11 21 | 12 11 21 ----------+----------+--------- 21 14 12 | 21 14 21 | 21 21 21 21 21 21 | 21 21 21 | 21 21 21 13 21 21 | 15 15 21 | 21 21 21
When the Solver is faced with several possible candidate moves for a guess, it will choose the move with the lowest Neighbour State score.
From Release 1.20, the Linear System State state grid is not available for display as it takes a large amount of memory to store, particularly for 4x4 and larger grids. However, the state grid is still calculated internally, so the following information remains relevant.
The Linear System State state grid considers variables of the form d[r,c,v],
which take the value 1 if the cell (r,c) contains the value v
or 0 otherwise. The classic Su Doku puzzle has 27 constraints that apply to the
variables associated with each value - one for each row, column and box - which
makes 243 constraints in all. The Solver will reduce the system of 27
constraints associated with each value according to standard linear algebra
techniques before it displays them. As of Release 1.19, no strategy makes use
of the state grid in order to perform eliminations, though the commentary on
the excerpt below indicates how this might be possible. One problem is that it
would be difficult to produce a human-readable justification for an elimination
made following a reduction of the system of equations.
Of course, there is a further contraint associated with each cell of the form
d[r,c,1]+d[r,c,2]+...+d[r,c,9]=1
However, these additional 81 constraints have been omitted for reasons of computational efficiency.
The excerpt below shows the system of equations satisfied by the variables associated with the value '5'.
d[1,1,5]-d[5,2,5]-d[5,3,5]-d[5,7,5]-d[6,3,5]-d[6,4,5]-d[6,5,5]-d[6,7,5]-d[9,4,5]-d[9,5,5] = -2 d[1,3,5]+d[5,2,5]+d[5,3,5]+d[5,7,5]+d[6,3,5]+d[6,4,5]+d[6,5,5]+d[6,7,5]+d[9,4,5]+d[9,5,5] = 3 d[2,2,5]-d[4,3,5]+d[5,2,5]+d[5,7,5]+d[6,4,5]+d[6,5,5]+d[6,7,5]-d[7,3,5]+d[9,4,5]+d[9,5,5] = 2 d[2,3,5]+d[4,3,5]-d[5,2,5]-d[5,7,5]-d[6,4,5]-d[6,5,5]-d[6,7,5]+d[7,3,5]-d[9,4,5]-d[9,5,5] = -2 d[2,8,5] = 1 d[3,6,5] = 1 d[4,2,5]+d[4,3,5]-d[5,7,5]-d[6,4,5]-d[6,5,5]-d[6,7,5] = -1 d[4,4,5]+d[6,4,5]+d[9,4,5] = 1 d[4,5,5]+d[6,5,5]-d[9,4,5] = 0 d[4,7,5]+d[5,7,5]+d[6,7,5] = 1 d[5,1,5]+d[5,2,5]+d[5,3,5]+d[5,7,5]-d[6,8,5] = 1 d[5,8,5]+d[6,8,5] = 0 d[6,1,5]+d[6,3,5]+d[6,4,5]+d[6,5,5]+d[6,7,5]+d[6,8,5] = 1 d[7,2,5]+d[7,3,5]-d[9,4,5]-d[9,5,5] = 0 d[7,5,5]+d[9,4,5]+d[9,5,5] = 1 d[8,9,5] = 1 d[9,1,5]+d[9,4,5]+d[9,5,5] = 1
Note that:
d[2,8,5] = 1 shows that a '5' must go into the cell
(2.8).d[5,8,5]+d[6,8,5] = 0 shows that a '5' belongs
neither in the cell (5,8) nor (6,8).