Do you really need matching pairs?

Programs which generate, solve, and analyze Sudoku puzzles

Do you really need matching pairs?

Postby Qu1zMaster » Sun Jan 22, 2006 10:56 am

This is only my second post, so forgive me if I'm going over old ground here.
I have written a solver program (which I'll post up here after I've tidied it up a bit).
It works as follows (I don't know any of the terminology, so bear with me please):
(1) look at each cell, and try to eliminate all but 1 number.
(2) look at each row, column and box, and try to find if each number has only one place to go.

Whenever (1) has covered the entire grid, if it finds any new numbers, it repeats for another pass. If not, it carries on to (2).
Whenever (2) finds something, it calls (1) again, and so on until it solves or gives up.

It is very successful, solving all puzzles in the Irish Times ( ), which publishes an easy, medium and hard puzzle every day (not Sundays).

I've keyed in some "hardest ever" puzzles, and it just gives up.

I'm planning to add a "guess" stage next, which I think will enable it to solve any puzzle no matter how hard.

My question is:
Is there any need for a "matching pairs" stage? Can you give me an example of a puzzle that can't be solved by (1) and (2) above, but can by finding matching pairs? Apologies if it's a silly question.
Posts: 3
Joined: 22 January 2006

Postby Shazbot » Sun Jan 22, 2006 11:06 am

Yes. You may have a column where the possible candidates look like this:

....(anything else below this).

Because the top two cells can only contain 1 and 2, then 1 must go in one of them, and 2 must go in the other. This is called a "naked pair", and means you can eliminate 1 and 2 from other cells in that column. By doing this, you expose 3 as the only number for the third cell. Your original two tests would not pick this up.

If you look at the following two websites:
you will see a number of other more advanced techniques, along with examples which will show why your two techniques will not be enough. Then there are other advanced techniques - over my head I'm afraid - that are discussed at length in this forum, many with examples of puzzles and step-by-step instructions for the technique.
Posts: 220
Joined: 24 September 2005

Return to Software