File: SOLVING_ALGORITHM

package info (click to toggle)
gnudoq 0.94-2.1
  • links: PTS
  • area: main
  • in suites: jessie, jessie-kfreebsd, wheezy
  • size: 2,696 kB
  • ctags: 232
  • sloc: cpp: 2,695; makefile: 6
file content (138 lines) | stat: -rw-r--r-- 7,167 bytes parent folder | download | duplicates (4)
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>