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 1-6 and 8-9 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 1-6 and 8-9 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 1-6 and 8-9 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>
|
