Posted By: dean
Date: 2005-08-14 08:22
Summary: How does it work?
Project: SuDoku-X 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 1-9 (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 logico-deductive 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 back-tracks and makes an alternate guess.

 Latest News TZInfo::Data v1.2014.2 Released     Philip Ross - 2014-03-25 22:32(0 Comment) [Read More/Comment(0)] TZInfo v0.3.39 Released     Philip Ross - 2014-03-09 20:23(2 Comments) [Read More/Comment(2)] TZInfo::Data v1.2014.1 Released     Philip Ross - 2014-03-09 20:00(0 Comment) [Read More/Comment(0)] Automatic Ruby 14.2.0 has been released!     id 774 - 2014-02-26 06:23(0 Comment) [Read More/Comment(0)] kramdown 1.3.2 released     Thomas Leitner - 2014-02-16 08:35(0 Comment) [Read More/Comment(0)] [News archive]