Posted By: dean
Date: 20050814 08:22
Summary: How does it work?
Project: SuDokuX Solver
Essentially, just two basic deduction rules are used, which I call 'Purge' & 'Isolate' and which work by a process of elimination. Initially, a puzzle is rendered as a table of sets of possibilities. So in the case of a 9x9 puzzle, all cells consist of the set of integers 19 (except of course, those that are already known).
'Purge', in the simplest case, would look for a cell with just one possibility (i.e. known) and purge all other cells of it. So if a row in the table had a cell set to '7' then '7' is purged as a possibility from all other cells in that row. The same reasoning holds for pairs of possibilities. Lets say that two of the cells in a row each have only the values '3' & '7', then they cannot logically be a possibility anywhere else, and can be purged from all other cells. eg [[..],[134],[37],[..],[..],[37],[..],[789..],[..]] => [[..],[14],[37],[..],[..],[37],[..],[89],[..]]. The same goes for triples and quadruples, etc, etc.
'Isolate' in the simplest case, would look for a cell containing a unique value  one that did not occur anywhere else in the row. Logically, this value can then be isolated as the only possibility for that cell. The same is true for pairs of values. So if two cells contain '3 & '7', but none others contain either a '3' or a '7' then logically, these two values can be isolated in those cells eg [[..],[..],[1379],[..],[..],[237],[..],[..],[..]] => [[..],[..],[37],[..],[..],[37],[..],[..],[..]]. Again, the same holds for triples and quadruples, etc, etc.
If, however, these two rules should prove insufficient to make further progress, then a guess is made as to the value of a particular cell and the logicodeductive methodology continues until an error is encountered in the form of a cell with an empty set i.e. one with no possibilities! In this case, the program backtracks and makes an alternate guess. 
