SuDoku Deduction Rules
- To: mathgroup at smc.vnet.net
- Subject: [mg59751] SuDoku Deduction Rules
- From: "CyberDean" <astrodean at yahoo.co.uk>
- Date: Sat, 20 Aug 2005 03:13:40 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
In a non-mathematica program I recently wrote, 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. I suspect there maybe more deduction rules, but I don't know what they are... CyberDean