1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

Quick description of the solving algorithm.
Note: different algorithms are used for the 'Solve' and 'Generate' commands,
this is about the former.
Note: 'bigbox' refers to one of the nine 3x3 square boxes.
The Solver consists of three basic phases:
1 Figure out whether there are 'forced' moves, and perform any such moves that
are found.
'Forced' moves are moves which follow logically from the current
configuration of the board without looking ahead for any moves. There are
two types of such moves:
a 'Forced possibilities'. This is the case if a square only has one allowed
number, e.g. numbers on the same row, column, and bigbox as the square are
placed such that 16 and 89 are forbidden, leaving only 7 to be placed in
the square.
b 'Forced options'. This is the case if a particular number can only be
placed in exactly one blank square of a row, column, or box, because that
number is forbidden in all other blanks. (of that row, column, or box)
2 If there are no forced moves available, find the blank square with the fewest
possibilities of placing a number. Clearly, 2 is the minimum, as 1 would
imply a forced move, and 0 would mean deadlock. (see below)
Try the first possible number which can be used for said square. Back to
phase 1, or phase 2 again if no forced moves are discovered.
3 Deadlock. Deadlock is detected if a move causes any blank square's possible
numbers to drop to 0. If this is the case, the algorithm traces back its
steps. It removes all forced moves since the last time phase 2 was initiated
and tries the next possible number for the square filled in the last phase 2.
If all possibilities for that square have been attempted, a wrong move
must have been made earlier, so all forced moves since the last phase 2 before
that, and the next possible move is tried for that square, etc.
At some point, there are either 0 blank squares left on the board, or deadlock
occurs for all possible moves that result from all choices of the first phase 2.
In the latter case, the puzzle is in fact unsolveable.
Note: It may occur that the *implementation* of this algorithm deems a puzzle
unsolveable even though it isn't. This is due to bugs in the implementation, a
perfect implementation of the algorithm won't have this problem. Such bugs
must be reported (or fixed :) if encountered.
 Phillip Jordan <pmjordan@gmx.at>
Quick description of the solving algorithm.
Note: different algorithms are used for the 'Solve' and 'Generate' commands,
this is about the former.
Note: 'bigbox' refers to one of the nine 3x3 square boxes.
The Solver consists of three basic phases:
1 Figure out whether there are 'forced' moves, and perform any such moves that
are found.
'Forced' moves are moves which follow logically from the current
configuration of the board without looking ahead for any moves. There are
two types of such moves:
a 'Forced possibilities'. This is the case if a square only has one allowed
number, e.g. numbers on the same row, column, and bigbox as the square are
placed such that 16 and 89 are forbidden, leaving only 7 to be placed in
the square.
b 'Forced options'. This is the case if a particular number can only be
placed in exactly one blank square of a row, column, or box, because that
number is forbidden in all other blanks. (of that row, column, or box)
2 If there are no forced moves available, find the blank square with the fewest
possibilities of placing a number. Clearly, 2 is the minimum, as 1 would
imply a forced move, and 0 would mean deadlock. (see below)
Try the first possible number which can be used for said square. Back to
phase 1, or phase 2 again if no forced moves are discovered.
3 Deadlock. Deadlock is detected if a move causes any blank square's possible
numbers to drop to 0. If this is the case, the algorithm traces back its
steps. It removes all forced moves since the last time phase 2 was initiated
and tries the next possible number for the square filled in the last phase 2.
If all possibilities for that square have been attempted, a wrong move
must have been made earlier, so all forced moves since the last phase 2 before
that, and the next possible move is tried for that square, etc.
At some point, there are either 0 blank squares left on the board, or deadlock
occurs for all possible moves that result from all choices of the first phase 2.
In the latter case, the puzzle is in fact unsolveable.
Note: It may occur that the *implementation* of this algorithm deems a puzzle
unsolveable even though it isn't. This is due to bugs in the implementation, a
perfect implementation of the algorithm won't have this problem. Such bugs
must be reported (or fixed :) if encountered.
 Phillip Jordan <pmjordan@gmx.at>
Quick description of the solving algorithm.
Note: different algorithms are used for the 'Solve' and 'Generate' commands,
this is about the former.
Note: 'bigbox' refers to one of the nine 3x3 square boxes.
The Solver consists of three basic phases:
1 Figure out whether there are 'forced' moves, and perform any such moves that
are found.
'Forced' moves are moves which follow logically from the current
configuration of the board without looking ahead for any moves. There are
two types of such moves:
a 'Forced possibilities'. This is the case if a square only has one allowed
number, e.g. numbers on the same row, column, and bigbox as the square are
placed such that 16 and 89 are forbidden, leaving only 7 to be placed in
the square.
b 'Forced options'. This is the case if a particular number can only be
placed in exactly one blank square of a row, column, or box, because that
number is forbidden in all other blanks. (of that row, column, or box)
2 If there are no forced moves available, find the blank square with the fewest
possibilities of placing a number. Clearly, 2 is the minimum, as 1 would
imply a forced move, and 0 would mean deadlock. (see below)
Try the first possible number which can be used for said square. Back to
phase 1, or phase 2 again if no forced moves are discovered.
3 Deadlock. Deadlock is detected if a move causes any blank square's possible
numbers to drop to 0. If this is the case, the algorithm traces back its
steps. It removes all forced moves since the last time phase 2 was initiated
and tries the next possible number for the square filled in the last phase 2.
If all possibilities for that square have been attempted, a wrong move
must have been made earlier, so all forced moves since the last phase 2 before
that, and the next possible move is tried for that square, etc.
At some point, there are either 0 blank squares left on the board, or deadlock
occurs for all possible moves that result from all choices of the first phase 2.
In the latter case, the puzzle is in fact unsolveable.
Note: It may occur that the *implementation* of this algorithm deems a puzzle
unsolveable even though it isn't. This is due to bugs in the implementation, a
perfect implementation of the algorithm won't have this problem. Such bugs
must be reported (or fixed :) if encountered.
 Phillip Jordan <pmjordan@gmx.at>
