Common consequenes of mutually exclusive possibilities

Advanced methods and approaches for solving Sudoku puzzles

Common consequenes of mutually exclusive possibilities

Postby pdelvigna » Tue Oct 23, 2007 11:34 pm

I've just joined this forum so please excuse any violation of norms or conventions. If there's "rules of conduct" page, please point me to it.

I've been fiddling with sudoko for some months now, and have recently experiment with a solving technique that I've often seen hinted at but never seen directly applied.

Here's the idea briefly. I'll elaborate if it turns out to be worthwhile.

You can apply to a puzzle any consequences that follow from all of N mutually exclusive conditions. For example, suppose we know square 1,1 can contain only 5 or 7. Further suppose that if 5 is put in 1,1, 3 is removed as a candidate from square 1,9. And still further suppose that if 7 is put in square 1,1 3 is also removed as a candidate from square 1,9. We know that we can eliminate 3 as a candidate from square 1,9.

I've automated this approach, and found that it's solved all puzzles I've run through it, considering at most 5 squares, each with two possible values. In general, the technique could be taken much further; it could, for example consider a row with could have the value 5 in one of N possible squares, etc. But that hasn't been necessary.

Carried out by a human, this approach could be very labor-intensive (I've done it with software). Also, it could be categorized as "trial-and-error" though I think that's debatable. Labor-intensive yes, trial and error, I might argue.

Anyway, I'm writring this because I'd appreciate any comments, puzzles to run through the technique, or pointers to descriptions of similar approaches.

Paul
pdelvigna
 
Posts: 1
Joined: 23 October 2007

Postby re'born » Tue Oct 23, 2007 11:41 pm

Hi Paul. Welcome to the forum:)

Your approach is what is called tabling. In particular, your example gives what is known as a tabling verity. The first work done on this that I know of can be found here on the programmer's forum.

Cheers.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby RW » Fri Oct 26, 2007 1:58 pm

Sounds like what Sudoku Explainer calls a "cell forcing chain", sometimes this technique is also called simply "forcing chain". If you let a computer do it systematically on all cells, then it becomes tabling. It will solve most puzzles, depending on how many different techniques are implemented to find the "consequences". For a list of puzzles that the technique most likely will not solve, see here. In many of those, this technique cannot make a single elimination.

The technique is very usable by humans, depending on how long chains you need. See for example my solution here.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006


Return to Advanced solving techniques