The New Sudoku Players' Forum

[carbon14]

This is a tricky question for me, and possibly for Wayne.

Over the time that I have been playing Sudoku, I have managed to codify the logic that I use to solve the puzzles down to just 5 techniques. And actually 2 of those are just special cases of 1 other.

I have never found a Sudoku puzzle which has required any additional techniques.

The problem I have is that the only puzzles I have played, all came from Wayne, from The Times newspaper (London), from the Times published book, and from the demo of his program.

Is it possible that there are other techniques required for solving sudoku, which I have not yet needed to find, simply because they never crop up in Wayne's puzzles?

[scrose]

I have managed to codify the logic that I use to solve the puzzles down to just 5 techniques. And actually 2 of those are just special cases of 1 other.

What are your five techniques? How do they compare to simes' list? As you noted, some techniques are corollaries of others.

I have never found a Sudoku puzzle which has required any additional techniques.

You and abailes could have a good discussion about this. He believes that some puzzles that require trial-and-error can actually be solved by a form of logic that we have yet to uncover. (I am inclined to agree with him, although there comes a point where logic can become so convoluted that it no longer can be applied easily.)

Is it possible that there are other techniques required for solving sudoku, which I have not yet needed to find, simply because they never crop up in Wayne's puzzles?

Wayne has said that his puzzles do not include swordfish (or jellyfish or squirmbags, for that matter) and do not require the nishio technique. You can find examples of these on the programmers' forum.

[MadOverlord]

"Can all sudoku puzzles be solved by logic?" is the wrong question; the right question is "Can all sudoku puzzles be solved by unaided human logic?"

At their most complex level, logical inferences can be effectively equivalent to brute-force recursion, and are impossible for humans to do without outside aids (like paper, pencil, counters, and so on).

Humans can only go so deep into an "if this, then that, then the other" tree of inferences before our minds "stack overflow" and we can go no deeper. Some people are better at this than others, but the practical limit for most people is 3-5 levels deep. OTOH, humans are very good at global pattern matching, stuff that computers have to do laboriously, step by step.

Stuff like Nishio, and Simple Forcing Chains, is possible for a skilled player to do without outside aids, and for a competent player to do with a couple of assists, like the coins in one's pocket, so they are right at the edge of what it is reasonable for a human to do. X-Wing, Swordfish, and the general case, "Fishy Cycles", rely on pattern matching in humans and so are also fair game.

But IMHO, future "human" techniques will merely be variants of these kind of techniques that catch a few more puzzles, but there won't be a "crack" technique that is the holy grail.

Of course, having said that, it will be announced tomorrow...

[carbon14]

scrose you have answered my question. I checked out Simes' list and Swordfish is not one of the techniques that I use, but you say that Wayne does not use Swordfish in his puzzles.

These are my techniques, and I have not yet found a Pappacom puzzle which my program does not solve.


Background:

there are many so-called sudoku solving programs out there which seem to use purely Nishio or some such to recursively guess at the puzzle until it works. These can be spotted because they will find a solution even if you give them a blank grid. I wanted to test my logic, so I wrote a 'logical' solver. This will stall if it cannot make any progress.

Basic Premise.

The program starts with a blank grid and fills each cell with 9 candidates.
Then it reads the input to the puzzle, which is a list of clues. For each clue it discards the 8 incorrect candidates in the cell. It will subsequently find these as answers during the 'solving' of the puzzle. When it finds an answer, it discards (crosses out) the appropriate candidates in the other cells in the row, column or box.

Rule 1:

If only 1 cell in a row column or box has a particular candidate digit, then that digit must be the answer for that cell.

Rule 2:

If a cell has only one candidate, then that candidate must be the answer for that cell.

Rule 3:

If a candidate digit appears in the cells of a boxcol, but not it the other cells of that box. Then it cannot be a candidate for the other cells in the column...
If a candidate digit appears in the cells of a boxcol, but not in the other cells of that column, then it cannot be a candidate for the other cells in the box.
As above substituting boxrow for boxcol and row for column.

Rule 4: (a more general case of Rule 2)

If n cells in a box, row or column each contain only the same n candidates. Then those candidates cannot be candidates for other cells in the same box, row or column

Rule 5: (a more general case of Rule 4)

If n cells in a box, row or column between them contain only the n different candidates, then those candidates cannot be candidates for the other cells in the same box, row or column.


I could have discarded Rules 2 and 4 altogether and just used rule 5. But its generality generally proves usefull only a handful of times in even fiendish puzzles. Since it is much more costly for the computer (and for a human) to search for, it is reserved for those occasions when no further progress has been made using the other rules.


Swordfish certainly seems on the face of it to be logically distinct from these rules, and I would like to...

A: Include it in my program for completeness

B: Find some puzzles which require it, to challenge myself further

C: Eventually compile some sudoku which require it.


I guess I might have to try importing some Japanese puzzle books.


I used to do books of cryptic crosswords, but when you've finished the book, you have to go out and get another one.

With sudoku, I'm sure that I could just start again from the beginning and do each puzzle many times before I rembered anything specific about any puzzle.

I was playing some different Japanese number puzzles on Friday, including Hitori. I didn't find any that looked like they would have the purity and staying power of sudoku, but they were certainly fun and challenging and I think that everyone should hunt some out and give them a try. They are published in the same kinds of books.

[simes]

Does it solve the puzzle from this thread? http://forum.enjoysudoku.com/viewtopic.php?t=75&postdays=0&postorder=asc&start=0

I believe this requires the "x-wing" technique to solve it.

[carbon14]

Nice puzzle, just what I was looking for.

I have tested it and my program did indeed stall. I have found 1 swordfish in it so far. I'll see if I can complete the puzzle by hand and then I'll add a new rule to my program.


Thank you.

[carbon14]

Just that one swordfish was all it took.

I'd have struggled for a long time to come up with that logic myself, it was a completely new technique to me two days ago.