## File: SOLVING_ALGORITHM

package info (click to toggle)
gnudoq 0.94-2.2
 `123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138` ``````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 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 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 ``````