The New Sudoku Players' Forum

[jdm]

I've been playing with Simple Sudoku's Extreme level puzzles and have yet to find a puzzle which is not solvable with a combination of:

* the most basic techniques (naked and hidden singles and pairs, and what Simple Sudoku calles Locked Candidate Exclusion);

* swordfish;

* single-number multiple-chain coloring (especially creating a loop consisting of weakly connected (via exclusion) chains of even order, and at most one chain of odd order, where a chain consists of conjugate pairs).

I find the latter easier to spot even than naked triples (a fortiori hidden triples or quads) or xy-wing since it only requires consideration of one number at a time.

* Maybe an occasional naked triple (I'm not sure if this was required; I know that I've spotted it by accident at times and used it, don't remember if I backtracked and tried to do the puzzle without it.)

Can you masters of the databases pull up any puzzles which require any techniques other than the above-named one?

Thanks!
JDM

[Carcul]

Hi Jdm.

Welcome to this forum. Why don't you try the following one?

Code: Select all

 . 8 .| 1 . .| . . 2
 . . .| . . .| 4 . .
 . 7 .| 4 9 .| . . .
------+------+-------
 4 . 9| . . .| . . .
 . . .| 3 . 5| . . .
 . . .| . . .| 2 . 6
------+------+-------
 . . .| . 8 2| . 5 .
 . . 3| . . .| . . .
 1 . .| . . 6| . 7 .


Try also here for some good puzzles. On the other hand, a lot of much more easier puzzles can be found here.

Have fun.

Regards, Carcul

[jdm]

Thanks, Carcul, this looks like a tough one, maybe requiring trial & error? I realize that my original question was not precise enough. I should have said: are there puzzles which do not require T&E yet cannot be solved using the basic techniques and coloring? I don't yet know if yours falls into that category.

[Jeff]

this looks like a tough one, maybe requiring trial & error? I realize that my original question was not precise enough. I should have said: are there puzzles which do not require T&E yet cannot be solved using the basic techniques and coloring? I don't yet know if yours falls into that category.

Hi Jdm, welcome to the forum. Everyone has his/er own definition of T&E and I don't know what yours is. How about if you give us a list of techniques, apart from the basic ones, that you considered as non-T&E to start with?

[tso]

Here's one of many solutions:

Download the free program Sudoku Susser. It does not generate puzzles but it will automatically solve them and give you a report of what tactics it used. You can choose which heuristics for it to use or not use. For example, you might set it to use all tactics other than Nishio, Tabling and Bowman's Bingo. If it cannot finish the puzzle, discard it and try another.

Though Susser does not generate puzzles, it will fetch hard puzzles from other sites on the web -- or you can paste them from any other source. One option is to use Solo from Simon Tatham's Portable Puzzle Collection set on Extreme or Unreasonable.



Oh, and no puzzle *requires* trial and error. You can call it that if you wish -- but you can call a rose a skunk -- it smells just as sweet.

[jdm]

Thanks, I've been reading around in response to these posts. At Tso's suggestion I downloaded and tried Susser.

I understand better now that there is no consensus definition for t&e (though Tso's comment above seems at an extreme end of the spectrum of opinions). In brief, I was referring to puzzles that do not require deep backtracking (where the grid is copied or saved and restored), nor computer-only methods (tabling, Bowman). From what I've read of it, I would consider Nishio to be an acceptable (not deep) level of backtracking.

I solved Carcul's problem above manually with one backtrack. Susser was only able to solve it with Tabling (maybe also with Bowman but that was taking too long so I cancelled it). So this problem seems not to qualify. OTOH, I see in another thread that Carcul solves manually and uses some powerful loop methods which I have not tried, so maybe this puzzle would fall to these and qualify after all.

Bottom line, I guess, is that the answer to my original question is "no", coloring does not do it all! I'm still wondering how many other basic techniques it makes unnecessary. I'll keep on experimenting.

Thanks again,
jdm

[Carcul]

Hi Jdm.

I solved Carcul's problem above manually with one backtrack.

Could you define "backtrack" please? Also, could you show us what was that "backtrack" with which you solved the puzzle?

Regards, Carcul

[jdm]

Hi Carcul,

Using only basic techniques and coloring, I reached a position from which I could not progress. I observed a long conjugate chain on digit 8, starting with "58" in R4C7, but could not use this chain to exclude anything more. So I tried setting R4C7 to 5, reached a contradiction through basic operations, then BACKTRACKED (returned to this position again), deducing that this cell was actually "8". Then the puzzle was easily solved. I think any puzzle can be solved easily if one is willing to backtrack once or twice, but that takes away the challenge.

Later, thanks to hints from Susser, I realized that I could have used Unique Rectangle (which is new to me, nice!) and XYZ-Wing to progress a little further from this position, but eventually the same problem occurred at the following position:

*--------------------------------------------------------------------*
| 569 8 4 | 1 56 37 | 37 69 2 |
| 3569 13569 156 | 26 256 378 | 4 689 137 |
| 236 7 126 | 4 9 38 | 135 68 15 |
|----------------------+----------------------+----------------------|
| 4 26 9 | 26 7 1 | 58 3 58 |
| 268 126 1268 | 3 26 5 | 79 4 79 |
| 357 35 57 | 8 4 9 | 2 1 6 |
|----------------------+----------------------+----------------------|
| 679 4 67 | 79 8 2 | 13 5 13 |
| 5789 59 3 | 79 1 4 | 6 2 89 |
| 1 29 28 | 5 3 6 | 89 7 4 |
*--------------------------------------------------------------------*

Were you able to solve it using only loops, not backtracking? If so, do you have a hint from this position?

Thanks,
jdm

[castalia]

Oh, and no puzzle *requires* trial and error. You can call it that if you wish -- but you can call a rose a skunk -- it smells just as sweet.

Hi tso,

Admittedly, the whole discussion of "trial and error" is confusing: the term appears to have no clear and consistent definition. But appearances are deceiving.

Any sudoku technique that requires an exponential number of operations when extrapolated to the NxN case is a "trial and error" technique, whereas the conventional techniques (e.g. singles, pairs, x-wings, swordfish, cycles with conflicting endpoints, etc.) require only a polynomial number of operations.

One of the many intriguing questions out there is whether there exists a set of polynomial-time techniques that solves ALL sudokus for the 9x9 case. It has already been proved (ref. e.g. Eppstein) that the "single-digit sudoku decision problem" is NP-complete for the general NxN case.

Mark

[Carcul]

Hi Jdm.

The next step could be

[r3c1]=2=[r5c1]=8=[r5c3]-8-[r9c3]-2-[r3c3]=2=[r3c1]

which implies r3c1=2.

Regards, Carcul

[jdm]

That's very nice, Carcul. Is this just called a forcing chain or does it have some other loop name because of its particular characteristics?

Do you have any special technique for manually finding a short forcing chain in a reasonable amount of time? I think before I could locate such a short forcing chain, I could arbitrarily find a longer forcing chain, which I would have to call T&E (apologies to Tso). It is not as elegant, and therefore it's not as clear to prove to another person, but for me it is a quicker way to solve the puzzle.

So do you start by finding a long forcing chain and then work backwards to find a shorter equivalent forcing chain for your "published proof"?

BTW, shouldn't the "-8-" actually be "=8=", like this:?
[r3c1]=2=[r5c1]=8=[r5c3]=8=[r9c3]-2-[r3c3]=2=[r3c1]

jdm

[Carcul]

Hi Jdm.

Is this just called a forcing chain or does it have some other loop name because of its particular characteristics?

It is more exactly a double implication forcing chain, commonly named "nice loop".

Do you have any special technique for manually finding a short forcing chain in a reasonable amount of time?

The technique is called "Bilocation/Bivalue Plot" and it is described here. It follows from the description that, normally, a short forcing chain is much more easily spoted than a longer one.

It is not as elegant, and therefore it's not as clear to prove to another person, but for me it is a quicker way to solve the puzzle.

Don't forget that this is not a speed contest. If you want to solve quickly any puzzle, just use T&E or guessing, but remember: that is not the essence of a Sudoku puzzle (in my personal opinion).

So do you start by finding a long forcing chain and then work backwards to find a shorter equivalent forcing chain for your "published proof"?

From the above, obviously not.

BTW, shouldn't the "-8-" actually be "=8=", like this:?
[r3c1]=2=[r5c1]=8=[r5c3]=8=[r9c3]-2-[r3c3]=2=[r3c1]

This way, your loop have three discontinuities, and we can only have one. The link [r5c3]=8=[r9c3] is a strong one, but can be used as a weak link (-8-).

Regards, Carcul

[Jeff]

Any sudoku technique that requires an exponential number of operations when extrapolated to the NxN case is a "trial and error" technique, whereas the conventional techniques (e.g. singles, pairs, x-wings, swordfish, cycles with conflicting endpoints, etc.) require only a polynomial number of operations.

Hi Mark, I am very impressed. But, since I don’t do computer science, I have no idea what you are talking about unfortunately.

Using language that everyone can understand, could you explain "exponential number of operations when extrapolated to the NxN case" and "polynomial number of operations"? How can these numbers be calculated? Can you give a few simple examples? Can T&E be defined within the 9x9 case, which is what 99% of players are interested in this forum?

One of the many intriguing questions out there is whether there exists a set of polynomial-time techniques that solves ALL sudokus for the 9x9 case. It has already been proved (ref. e.g. Eppstein) that the "single-digit sudoku decision problem" is NP-complete for the general NxN case.

Using language that everyone can understand, could you explain "a set of polynomial-time techniques", "single-digit sudoku decision problem" and "NP-complete for the general NxN case"?

So, what is the bottom line? Which techniques are non-T&E according to the definition given in your first paragraph? How does your second paragraph relate to T&E in sudoku solving?

[Wolfgang]

NP-completeness means that the time (or steps) you need for solving a problem, grows exponentially with the "size" of the problem, which is 3 for normal sudokus (also latin squares are NP-complete, sudokus are harder, therefore also NP-complete). For 9x9 sudokus the NP-completeness normally is no problem - also the hardest can be solved with a program in reasonable time.
Im not sure about what techniques are NP-complete then (i.e. you would need e.g. more than 2^n steps when you use it in the general case). This would need some mathematical investigation for each one.

[jdm]

Hi Carcul,

Oh, nice loops - I read Jeff's post about them just yesterday, and didn't recognize one even in front of my nose: clearly more study and practice needed!

Thanks for the pointer to Jeff's superb post about BLBV plot - yesterday I drew something like his diagram, and also something very much like Max's arrow diagram, but will need more patience and theory to be able to use them properly.

I'm curious - you seem to have great insight into loops - so do you look for triples and quads before loops, since they are simpler forms and therefore might be considered more elegant, even if they take more time to find than simple loops?

Thanks for all your help. This is fascinating material. Now I'm going to have to be strong-willed and tear myself away from it for some days or weeks before I lose track of other responsibilities!!

jdm