The Ancient "Toughest Known Puzzle"

Advanced methods and approaches for solving Sudoku puzzles

The Ancient "Toughest Known Puzzle"

Postby Carcul » Tue Mar 28, 2006 7:30 pm

Since I have discovered a logical solution for the following puzzle, I thought that, as was done with the "Third Toughest Puzzle", it would be a good idea to capture in a single place all the available logical solutions for the puzzle. So, the purpose of this thread is to collect different solving approaches to what I consider a special puzzle, in order to make a comparision between them and, perhaps, try to learn something with them and make some progress. I invite the others users of this forum to post their solutions of this puzzle in this post. Thanks.
(For an explanation of the notation used in the following logical deductions, please consult this thread).
The puzzle that I am talking about is the following one:

Code: Select all
 *-----------------------*
 | . . . | . 7 . | 9 4 . |
 | . . . | . 9 . | . . 5 |
 | 3 . . | . . 5 | . 7 . |
 |-------+-------+-------|
 | . . 7 | 4 . . | 1 . . |
 | 4 6 3 | . . . | . . . |
 | . . . | . . 7 | . 8 . |
 |-------+-------+-------|
 | 8 . . | . . . | . . . |
 | 7 . . | . . . | . 2 8 |
 | . 5 . | 2 6 . | . . . |
 *-----------------------*

which was considered until recently (October 2005?) the toughest known puzzle.
After the basic logic have been applied we arrive at the following grid:

Code: Select all
 *------------------------------------------------------------*
 | 1256  12     1258  | 1368  7    1236  | 9      4    1236   |
 | 126   7      1248  | 1368  9    12346 | 2368   136  5      |
 | 3     1249   12489 | 168   1248 5     | 268    7    126    |
 |--------------------+------------------+--------------------|
 | 259   8      7     | 4     235  2369  | 1      3569 2369   |
 | 4     6      3     | 1589  1258 129   | 257    59   279    |
 | 1259  129    1259  | 3569  235  7     | 23456  8    23469  |
 |--------------------+------------------+--------------------|
 | 8     12349  12469 | 7     1345 1349  | 456    1569 1469   |
 | 7     1349   1469  | 1359  1345 1349  | 456    2    8      |
 | 19    5      149   | 2     6    8     | 347    139  13479  |
 *------------------------------------------------------------*


From here, the solution of this puzzle that I have worked out makes use of the following steps:

1. [r8c3]{=6=[r7c3]=2=[r7c2](-2-[r6c2])-2-[r1c2]-1-[r6c2]}-9-[r3c3]=9=[r3c2]-9-[r6c2],

which means that, if r8c3=9 then r6c2 would be an empty cell. So, r8c3<>9.

2. [r5c4]{-8-[r5c5]=8=[r3c5](-8-[r3c7]=8=[r2c7]-8-[r2c3])=4=[r2c6]-4-[r2c3]}(-8-[r1c4]=8=[r1c3]=5=[r6c3]-5-[r6c4])-8-[r123c4](-3,6-[r6c4]-9-[r6c2])-1,3,6-[r1c6]-2-[r1c2](-1-[r6c2])-1-[r2c3]-2-[r7c3]=2=[r7c2]-2-[r6c2],

which means that r5c4=8 would make r6c2 an empty cell. So, r5c4<>8.

3. [r8c5](-3-[r8c46|r7c6])(-3-[r8c2]=3=[r7c2]=2=[r7c3]=6=[r8c3]-6-[r8c7])-3-[r46c5]-2,5-[r5c46]=(Almost Unique Rectangle:r5c46/r8c467)=2,5|4,5=[r8c467]-4-[r8c2|r9c1]-1,9-[r9c3]-4-[r2c3]=4=[r2c6]-4-[r78c6]-1,9-[r5c6],

which means that r8c5=3 would make r5c6 an empty cell. So, r8c5<>3.

4. In this step, I have made use of a concept that I call "Almost Nice Loops" (this step, and the concept of Almost Nice Loops, are explained in detail in this thread):

[r7c5](-3-[r7c6])(-3-[r7c2]=3=[r8c2])-3-[r46c5](-2,5-[r5c46]){-5-[r56c4]=5=[r8c4](-5-[r8c7])=9=[r8c6](-9-[r7c6])-9-[r5c6]-1-[r7c6]}-{Nice Loop: [r8c3]-4-[r8c5]=4=[r3c5]-4-[r2c6]=4=[r2c3]-4-[r8c3]}-4-[r8c3]-{Nice Loop: [r8c7]-4-[r8c5]=4=[r3c5]-4-[r2c6]=4=[r2c3]-4-[r9c3]=4=[r9c79]-4-[r8c7]}-4-[r8c7]-6-[r8c3]-1-[r8c5]-4-[r7c6],

which means that, if r7c5=3 then r7c6 would be an empty cell. So, r7c5<>3.

5. [r8c4]{-1-[r78c5]=(Almost Unique Rectangle: r78c5/r78c7)=1|6=[r78c7]-6-[r7c8]}(-1-[r5c4]=1=[r5c6]-1-[r12c6])-1-[r123c4](=1=[r3c5]-1-[r3c9])(-6-[r6c4]=6=[r4c6])-3,6-[r1c6]-2-[r1c2]-1-[r1c9]=1=[r2c8]=6=[r4c8]-6-[r4c6],

which means that, if r8c4=1 then r4c6 would be simultaneously "6" and not "6" - a contradiction. So, r8c4<>1.

6. [r78c6]{-1-[r78c5]=(Almost Unique Rectangle: r78c5/r78c7)=1|6=[r78c7]-6-[r7c8]}(-1-[r12c6])-1-[r5c6]=1=[r5c4]-1-[r123c4](-6-[r6c4]=6=[r4c6])(=1=[r3c5]-1-[r3c9])-3,6-[r1c6]-2-[r1c2]-1-[r1c9]=1=[r2c8]=6=[r4c8]-6-[r4c6],

and similarly we have r7c6/r8c6<>1.

7. [r8c5]=1=[r8c23](-1-[r9c3])-1-[r9c1]-9-[r9c3]-4-[r2c3]=4=[r2c6]-4-[r3c5]-2-[r46c5]-5-[r8c5], => r8c5<>5.

8. [r6c7]-5-[r8c7]=5=[r8c4]-5-[r5c4]=5=[r5c78]-5-[r6c7], => r6c7<>5.

9. [r5c7](-5-[r5c4|r4c8])-5-[r5c8](-9-[r9c8|r4c8])-9-[r5c4]-1-[r123c4]-6-[r6c4]=6=[r4c6]-6-[r4c8]-3-[r9c8]=3|4=[r9c3]-4-[r2c3]=4=[r2c6]-4-[r3c5]-2-[r46c5]-5-[r6c4]-9-[r6c123]=9=[r4c1]-9-[r9c1]-1-[r9c8],

from which we can conclude that r5c7=5 would make r9c8 an empty cell. So, r5c7<>5.

10. [r5c9](-9-[r5c46|r4c8])-9-[r5c8](-5-[r4c8])-5-[r5c4](-1-[r5c6]-2-[r1c6])-1-[r123c4](-3,6-[r1c6]-1-[r1c2]-2-[r6c2|r7c2])-6-[r6c4]=6=[r4c6]-6-[r4c8]-3-[r9c8]=3|4=[r9c3](-4-[r78c2])-4-[r2c3]=4=[r2c6]{-4-[r78c6]=(Almost Unique Rectangle: r78c2/r78c6)=4|1=[r78c2]-1-[r6c2]}-4-[r3c5]-2-[r46c5]-5-[r6c4]-9-[r6c2],

and r6c2=empty cell if r5c9=9, and so r5c9<>9.

11. [r45c6]-9-[r78c6]{(-4-[r7c5])-4-[r8c5]-1-[r7c5]-5-[r7c7]=5=[r8c7]=6=[r8c3]-6-[r7c3]}-4-[r2c6]=4=[r2c3](-4-[r7c3])-4-[r9c13](-1,9-[r7c3])-1,9-[r78c2]-(Unique Rectangle: r78c2/r78c6)-3,4-[r7c2]-2-[r7c3],

which means that if either of r4c6/r5c6 is "9" then r7c3 would be an empty cell. So, r4c6/r5c6<>9.

12. In this step I have used some Almost Locked Sets present in the grid:

[r2c3](-4-[r3c3|r3c2])(-4-[r9c13]-1,9-[r9c789]-4-[r78c7]-6-[r236c7])-4-[r2c6]=4=[r3c5]-4-[r78c5]-5-[r46c5]-2-[r4c6]-6-[r4c89]=6=[r6c9](-6-[r13c9]=6=[r2c8]-6-[r2c1|r1c2|r3c2]-1,2,9-[r3c3])=4=[r6c7]-4-[r9c7]-7-[r5c7]-2-[r3c7]-8-[r3c3],

which means that, if r2c3=4 then r3c3 would have no possible candidate. So, r2c3<>4.

13. Now we have a Type-1 Unique Rectangle in cells r78c2/r78c6 that enables us to deduce r7c2<>3,9.

14. [r7c3]{=2=[r7c2](-2-[r6c2])-2-[r1c2]-1-[r6c2]}-9-[r3c3]=9=[r3c2]-9-[r6c2],

and r6c2 would be an empty cell if r7c3=9. So, r7c3<>9.

15. [r7c23](-1-[r7c9])-1-[r7c5]-4-[r7c9]=(Almost Unique Rectangle: r4c89/r7c589)=1,4|3=[r4c9]-3-[r4c5]-5-[r4c1]-9-[r9c1]-1-[r7c23],

which implies r7c2/r7c3<>1.

16. [r3c4]=1=[r3c9]-1-[r7c9]=1=[r7c5]=4=[r8c5]-4-[r8c7]-6-[r3c7]-8-[r3c4],

which implies r3c4<>8 and that solves the puzzle.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby re'born » Wed Mar 29, 2006 10:45 pm

Eat your heart out Jana Tylova. I nominate Carcul as the first 'true' Sudoku World Champion.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby RW » Sat Apr 01, 2006 11:00 am

Hi Carcul

As I like a good challenge, I decided to test my skills against the toughest puzzle known (until recently), but now I have a big moral dilemma. I always solve on paper, without pencilmarks, only writing in certain numbers. I do not accept T&E as a valid technique. When basic logical reductions isn't enough I start reading ahead (explained here) to find contradictions and make exclusions. If the puzzle is "only" extremely difficult I usually don't allow myself to do any long trails, the shorter the trail, the more logical (and less T&E) it feels. When I work with superfiendish puzzles, my approach is slightly different. When I can assume that there isn't any short trails, I usually go on until I arrive at the contradiction.

In this puzzle I first entered the four singles, then started to look for a good place to start a trail. Usually this would mean some place with only two options, where both options give at least a few numbers. In a superfiendish I do this also a bit different and usually choose a starting point that seems to give me as many singles as possible, don't care about what the first reduction gives me. This is because a) I don't expect to solve the puzzle with only one trail anyway, and b) when doing a trail that affects cells all over the puzzle, I can learn a lot about the puzzle, memorize what you call strong and weak links and so on. In this sence the best place to start trailing seemed to be by placing 4 somewhere in r78c23, all options would give lots of singles. Then I saw that number four in r8c3 also would give some nice uniqueness reductions (those who have read my other posts know that I loove uniqueness reductions) so I went with that. The first part of my trail, including the uniqueness reductions went:

If r8c3=4 => (r9c13 & r7c89 = {1,9}) => r7c3=6 =>r8c7=6 => uniqueness: r7c7<>4 => r7c5=4 => r7c7=5 => uniqueness: r8c5<>5 => r8c4=5 ...

Then I just kept going memorizing all singles that came up and some 50 steps and 15-20 minutes later I realised that I had solved the puzzle. I rechecked my trail and when I saw that it was valid I started writing in the numbers cell by cell, starting from the upper left corner.

My problem is that I don't know if I should be satisfied with my solution. Usually a solution requires contradictions that remove all other options. In this case it wasn't a contradiction, but a satisfying solution that removed all other options. So now I don't know if I should declare myself "king of the world" because I solved the toughest puzzle known (until recently) in 20 minutes without even writing in the numbers, or if I should just declare myself a lucky bastard. Anyway, I can't go back anymore and try to find a solution by contradiction, it's quite a distraction that I happen to remember all correct numbers of all cells.

But from another point of view: "if r8c3=4 => the puzzle has a satisfying solution => r8c3=4" could be seen as a perfectly logical solution based on uniqueness. I've used this techique quite often when I've got stuck with only around 20 empty cells remaining (feels less T&E with a shorter trail).

So what do you think? Can I be satisfied with my solution, or should I try again in a month, when I've forgotten all about the puzzle?

regards, RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby Carcul » Sat Apr 01, 2006 12:30 pm

Hi RW.

First, if you feel good with your solution, then that's ok. But I have some comments:

RW wrote:I always solve on paper, without pencilmarks,


Don't you think that is a "little" strange to try to solve such an hard puzzle without pencilmarks?

RW wrote:Usually this would mean some place with only two options, where both options give at least a few numbers. In a superfiendish I do this also a bit different and usually choose a starting point that seems to give me as many singles as possible, don't care about what the first reduction gives me.


In my opinion, this looks pure and simple Trial and Error.

RW wrote:In this sence the best place to start trailing seemed to be by placing 4 somewhere in r78c23, all options would give lots of singles.


This looks again T&E. At least when I look for a puzzle I try to relate a cell with some kind of pattern that I have spoted in the grid (ALSs, AURs, a b/b plot, grouped links).

RW wrote:Then I just kept going memorizing all singles that came up and some 50 steps and 15-20 minutes later I realised that I had solved the puzzle.(...) My problem is that I don't know if I should be satisfied with my solution.


That's the risk that you (or others) take by using such a strange and T&E based solving method (in my opinion). Don't you think that is strange to solve a puzzle by showing that a given cell "A" with a certain candidate "x" solves the puzzle, but without showing why we cannot have A<>x?

RW wrote:Anyway, I can't go back anymore and try to find a solution by contradiction, it's quite a distraction that I happen to remember all correct numbers of all cells.


With all respect, I think that is the price to be paid by trying to solve a puzzle (in this case a special puzzle) without pencilmarks. RW, there is a good reason for the people in this forum try to find pattern based techniques that can be applied in a grid filled with pencilmarks.

RW wrote:But from another point of view: "if r8c3=4 => the puzzle has a satisfying solution => r8c3=4" could be seen as a perfectly logical solution based on uniqueness.


Oh yes, it is logical, but so is T&E. Although some may disagree with me, in my opinion your solution is based in a lucky guess.

RW wrote:So what do you think? Can I be satisfied with my solution, or should I try again in a month, when I've forgotten all about the puzzle?


Again, if you feel happy with your solution, then ok. But I think that you should seriously consider to read some of the techniques described is this forum and try to apply them, instead of just keeping training your memory, with all respect. RW, by applying your method we could all solve any puzzle with more or less effort. So, regarding my request above for others users to post their solutions, I certainly do not consider your "solution" as corresponding to my request. In fact, and again with all respect, I don't even know why you have posted such a reasoning for such a puzzle.

I have three more comments:

1. Trying to solve easy/medium/hard puzzles without pencilmarks seems completely ok and looks like a good challenge. Trying to do the same with the toughest puzzles seems to me more like a memory challenge and less a logical challenge, with the risk of finding a solution based on a guess.

2. You keep showing us that you have a good memory. Well, I agree on that: you certainly have a very good memorizing power. But in that case I can say that I also have a good memory: I have also solved some (hard) puzzles completely in my head (which means more that 50 cells with their correct candidates and locations memorized), but I have done that only after one or more logical deductions. For example, when I try to solve a puzzle in a single step, after a deduction I "see" the effect of it in my head and in some cases it completely solve the puzzle. But I don't try to use my memory randomly in a grid: as I have described somewhere else, I always make a simplified b/b plot, and take some notes about the ALSs, AURs, etc, present in a grid, which I think is different from selecting a cell based on the number of singles it gives with a certain candidate.

3. RW, I don't think you will ever "forget all about the puzzle". That's why I don't even try to deduce based in a "feeling" or a guess based in a non-pattern reason, because I know perfectly that I would taking the risk of solve the puzzle with lucky and then I would remember the correct candidates of the cells and that would affect my posterior solving, which is precisely what I don't want.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby RW » Sat Apr 01, 2006 2:21 pm

Thank you for your opinion, I can see that we both feel the same way about a solution like this, I do not think it's a good way to solve a puzzle either.

First I wish to correct an error in my trail, forgot to add the two steps "if r8c3=4 => r3c2=4 => r2c6=4", which of course would imply that r7c5=4, without any uniqueness reduction (laughed a bit at myself when I just realised it). But that tells a lot about the difference in human and computer solving. I go with the first logical technique I see, dont follow any certain order. Actually I often notice that I solve already obvious singles through uniqueness reductions.

Carcul wrote:
RW wrote:Usually this would mean some place with only two options, where both options give at least a few numbers. In a superfiendish I do this also a bit different and usually choose a starting point that seems to give me as many singles as possible, don't care about what the first reduction gives me.


In my opinion, this looks pure and simple Trial and Error.


To explain this approach to a superfiendish once more: I regard this equivalent to the phase where you enter pencilmarks and locate strong links, weak links, AURs or whatever. By scanning my way through the grid in this way, I probably do quite the same observations that you do in your pencilmarkgrid. My understanding of a superfiendish puzzle has so far been that it shouldn't have a back door (=entering a single number would make it easy), which eliminates the risk of ending up with a solution. In this case there happened to be a back door, r8c3=4 + one uniqueness reduction and the rest can be solved by singles, so I totally agree that the solution also was based on a lucky guess.

Carcul wrote:
RW wrote:In this sence the best place to start trailing seemed to be by placing 4 somewhere in r78c23, all options would give lots of singles.


This looks again T&E. At least when I look for a puzzle I try to relate a cell with some kind of pattern that I have spoted in the grid (ALSs, AURs, a b/b plot, grouped links)... ...which I think is different from selecting a cell based on the number of singles it gives with a certain candidate.


Well, at the point when I chose the cell I had related it with two AURs and more than ten different strong/weak links (=give lots of singles) that I had spotted in the grid. I never choose a random cell.

Carcul wrote:But I think that you should seriously consider to read some of the techniques described is this forum and try to apply them


Yes, I have read a lot of the techniques on this forum lately and found that I already apply them. The nice loops and related techniques you are describing a lot are always very beautiful solutions and it seems to me that we work in a very similar way. I usually solve through patterns like that also, only I look for them in a non-pencilmark grid.

Carcul wrote:RW, there is a good reason for the people in this forum try to find pattern based techniques that can be applied in a grid filled with pencilmarks.


Yes, but they can also be applied in a grid not filled with pencilmarks.

The T&E question here is indeed very diffuse. I could also ask you how many nice loops you tried to form that didn't give you result when you solved this puzzle. I suppose, correct me if I'm wrong, that when you look for your monsterloops you start from one cell (chosen with care as you described above), make somekind of notes of strong/weak links, AURs etc. as you go and hope that you will end up with a logical reduction. In fact this is exactly the way I work, but I don't use PMs or any fancy notes of the steps I take. Does the lack of pencilmarks make it less logical?

regards RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby Carcul » Mon Apr 03, 2006 11:59 am

Hi RW.

RW wrote:Well, at the point when I chose the cell I had related it with two AURs and more than ten different strong/weak links (=give lots of singles) that I had spotted in the grid. I never choose a random cell.


Ahh, but you didn't mention that in your first post. Ok now: so you have related a cell with some patterns in the grid - good job.

RW wrote:...and it seems to me that we work in a very similar way. I usually solve through patterns like that also, only I look for them in a non-pencilmark grid.


Yes, I can see that we work in a very similar way. Funny, isn't it?

RW wrote:I could also ask you how many nice loops you tried to form that didn't give you result when you solved this puzzle.


Honestly, I don't remember any. Perhaps one, at most.

RW wrote:Does the lack of pencilmarks make it less logical?


No, of course not, but I didn't say that not using PM is not logical: I only say it was strange (for me), specially in extremely hard puzzles. I can also say that, when constructing simple nice loops in a grid with pencilmarks we can make a deduction without even know what are the "real" candidates of the cells used in the loop, which, as far as I can see, don't happen in a grid without PMs where I think we have to know what are the candidates in each cell (correct me if I am wrong, but from the way you have posted your "deduction" above it looks that this is true). Well, I do know that there are some people out there that have "moral" problems with deductions that involve "fill in numbers" in the cells used in the deduction. Personally, I wouldn't have any problem with that, as long as a deduction don't involve a guess (and so it is logical) and have used some pattern recognition (and so it is not Trial and Error).

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby RW » Mon Apr 03, 2006 3:49 pm

Hi Carcul

Carcul wrote:I can also say that, when constructing simple nice loops in a grid with pencilmarks we can make a deduction without even know what are the "real" candidates of the cells used in the loop, which, as far as I can see, don't happen in a grid without PMs where I think we have to know what are the candidates in each cell


I cannot quite agree with that. I never consider what candidates can be in each cell, only what candidates cannot go in cells. I guess everybody who sometimes solves without pms has noticed that hidden singles, pairs and triplets are easier to find than naked, because they don't rely on possible placements but impossible.

Carcul wrote:Well, I do know that there are some people out there that have "moral" problems with deductions that involve "fill in numbers" in the cells used in the deduction. Personally, I wouldn't have any problem with that, as long as a deduction don't involve a guess (and so it is logical) and have used some pattern recognition (and so it is not Trial and Error).


Actually every technique that removes candidates is derived from "fill in numbers" in some way. The most common patterns (pairs, triplets, x-wing...) have been standardised and are never looked upon from this point of view, but the actual reason you make a reduction is still "if cell A=x => contradiction somewhere else => A<>x". XY-wing is a very good example of "if cell A=x => cell B is empty, A<>x" and I don't think anybody has a moral problem with that. I completely agree with you that if pattern recognition is involved there is no problem, but it doesn't neccessarily have to be a "standardised" pattern. Personally I like to keep the patterns small, if there's more than 10 steps between the assumption and the contradiction I'm not quite satisfied with my solution.

As for my "deduction" above, I didn't intend to find a solution that way, the trail was so easy to follow that I was sure it would have to end with a contradiction. The reputation of the puzzle had me make a false assumption that there would be no backdoor. And as I said, I had started with a number, which reduction wouldn't have helped me at all. So this trail wasn't even intended to be a part of my solution, it was simply my way of finding out relationships between cells. Actually it was an unlucky guess, because I won't get the pleasure of finding a good solution. But I would be very happy if someone could permutate the puzzle into an unrecognisable form (swap around the boxes, the rows/columns within the boxes, and change places between different numbers, I guess you know how to do it) and post it here, so I could give it another try.:)

Regards RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby Ruud » Mon Apr 03, 2006 4:07 pm

RW wrote:But I would be very happy if someone could permutate the puzzle into an unrecognisable form (swap around the boxes, the rows/columns within the boxes, and change places between different numbers, I guess you know how to do it) and post it here, so I could give it another try.

Hi RW,

I recently added a scramble function to SudoCue, so here is your new challenge:

Code: Select all
. . .|8 . 5|. . .
. . 5|. . 3|8 6 .
. . .|. . 9|. . 1
-----+-----+-----
. . 1|. 8 .|. . .
4 8 .|. . .|. . 9
. . .|3 . .|. . 7
-----+-----+-----
. 4 .|2 . .|. . .
1 . .|. . .|6 . .
. 3 8|. 6 .|7 . .


Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby RW » Mon Apr 03, 2006 4:32 pm

Thanks Ruud, I'll have a look at it as soon as I can find some spare time within these limited 24 hour days.

-RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby RW » Tue Apr 11, 2006 2:32 pm

Ok, time to submit a solution to the “scrambled” puzzle:

Code: Select all
 
*-----------*
 |...|8.5|...|
 |..5|..3|86.|
 |...|..9|..1|
 |---+---+---|
 |..1|.8.|...|
 |48.|...|..9|
 |...|3..|..7|
 |---+---+---|
 |.4.|2..|...|
 |1..|...|6..|
 |.38|.6.|7..|
 *-----------*


First the singles:

r3c1=8
r3c4=6
r4c9=6
r5c8=8

To avoid making the same mistake as I did with the first version, I decided not to make any trails longer than 15 steps (to me 1 step = 1 solved number). As I work entirely without pm:s I’ve developed some techniques that makes memorizing easier in puzzles like these, where multiple trailingreductions has to be done. One is the use of what could be called a help-trail or help-pattern. I first find a pattern where multiple startingpoints lead to the same reductions. I think this is best illustrated with the real example:

If 3 in box 1 is in row 1 => r78c9=(38) => r9c9=5 => r12c9=(24) => r1c7=9 => r1c8=7 => r3c78=(35) => r89c8=(24) => r7c8=9 => r7c7=1 => r5c8=1

This means that a 3 in r1c1 or r1c3 pretty much solves or divides into pairs all of boxes 3 and 9, and it also leaves me with a nice UR in r34c78. I could of course make the uniqueness-reduction and go on solving more singles, but that would only make things harder. The trail, as it is now, is about as much as I can handle in one thought. I memorize this trail (or actually the situation it causes in boxes 3, 6 and 9) really well, so that whenever I get a 3 in one of the cells, I can apply all of it in one step.

I used this "one step pattern" in my first 5 trails. I shall refer to this reduction as Pattern A.

1. If r4c1=5 => r5c3=3 => r1c1=3 => r8c2=5 => r7c5=5 => r8c5=3 => r4c2=7 => r4c4=9 (=> Pattern A) => r9c1=9 => nowhere to place 9 in row 8 => r4c1<>5

2. If r6c5=5 => r5c45=(17) => r4c2=5 => r4c1=7 => r5c3=3 => r1c1=3 (=> Pattern A => r5c8=1) => nowhere to place 1 in box 5 => r6c5<>5

3. If r6c7=5 => r6c56=(14) => r5c45=(57) => r4c4=9 => r4c2=5 => r4c1=7 => r5c3=3 => r1c1=3 => Pattern A => r9c1=9 => r2c1=2 => r6c1=6 => r3c2=7 => r3c3=4 => r1c3=6 => nowhere to place 6 in box 7 => r6c7<>5

=> r6c1 or r6c2=5 => r4c2<>5

4. If r5c3=3 => r1c1=3 => Pattern A => r5c45=(57) => r4c78=(35) => Double solution => r5c3<>3

=> r4c1=3

5. If r1c3=3 => r3c3=4 => Pattern A => r5c45=(57) => r4c2=7 => r2c1=7 => r3c2=2 => r1c1=6 => r1c2=1 => r2c2=9 => r8c2=5 => no number can go in r7c1 => r1c3<>3

=> r3c3=3
=> r1c3=4

6. If r5c3=6 => r6c6=6 => r6c57=(14) => r4c2=7 => r3c2=2 => r1c2=6 => r2c2=1 => r1c5=1 => r2c5=2 => r2c9=4 => r2c4=7 => r3c5=4 => no number can go in r6c5 => r5c3<>6

=> r5c6=6

7. If r5c3=2 => r4c2=7 => r4c3=9 => r3c2=2 => r9c1=2 => r9c8=9 => r7c78 =(13) => UR:r6c7=1 => r7c7=3 => r5c7=5 => nowhere to place 5 in row 4 => r5c3<>2

=> r5c3=7
=> r5c78=23 => r6c7=1
=> r4c78=(45) => r34c7=(45) => UR:r3c8<>(45)
=> Fill in the remaining singles => Puzzle solved

Just as a curiosity I then decided to try if I could replace the first 5 trails with one trail by continuing “pattern A”:

If r1c1 or r1c3=3 => r78c9=(38) => r9c9=5 => r12c9=(24) => r1c7=9 => r3c78=(35) => r7c7=1 => r7c8=9 => r5c8=1 (=> UR: r4c7<>35) => r5c45=(57) => r4c67=(24) => r4c4=9 => r8c5=9 => r7c5=3 => r8c4=5 => r7c1=5 => r2c2=9 => r1c2=1 => r6c2=6 => r6c1=2 => r2c1=7 => r4c1=3 => no number can go in r5c3 => r1c13<>3

That trail is 2 steps longer than the 15 steps I allowed myself to do in my first solution, but it replaces all of the first 5 trails. Counting logical steps as a whole, this provides a much faster solution than my first one as it only requires 3 trails.

Then a question to all you “nice guys” out there: Could you express the reductions I made in your “nice” language – could you thus solve the puzzle with only 3 nice loops or SINs or whatever you call them?

regards
RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby Carcul » Tue Apr 11, 2006 3:21 pm

Hi RW.

Just to remind you that this thread was originally intended to be dedicated only to the "Ancient Toughest Puzzle", not other one. I think the things are going a little off topic here.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby RW » Tue Apr 11, 2006 8:10 pm

carcul wrote:this thread was originally intended to be dedicated only to the "Ancient Toughest Puzzle", not other one.


This is the same puzzle but in a different form. If it helps I can translate it to fit the original "ancient toughest".

Code: Select all
*-----------------------*
 | . . . | . 7 . | 9 4 . |
 | . . . | . 9 . | . . 5 |
 | 3 . . | . . 5 | . 7 . |
 |-------+-------+-------|
 | . . 7 | 4 . . | 1 . . |
 | 4 6 3 | . . . | . . . |
 | . . . | . . 7 | . 8 . |
 |-------+-------+-------|
 | 8 . . | . . . | . . . |
 | 7 . . | . . . | . 2 8 |
 | . 5 . | 2 6 . | . . . |
 *-----------------------*


First the singles:
r2c2=7
r4c2=8
r9c6=8
r7c4=7

The trail I called "Pattern A":
If 4 is in column 3 of box 1=> r9c79=(47) => r9c8=3 => r9c13=(19) => r8c3=6 => r7c3=2 => r78c2=(34) => r7c89=(19) => r7c7=6 => r8c7=5 => r7c5=5

1. If r2c6=3 => r3c5=4 => r2c3=4 (=> Pattern A) => r1c9=3 => r6c7=3 => r6c9=4 => r1c6 =2 => r4c6=6 => nowhere to place 6 in box 6 => r2c6<>3

2. If r6c4=3 => r46c5=(25) => r1c6=3 => r2c6=2 => r3c5=4 => r2c3=4 (=> Pattern A => r7c5=5) => nowhere to place 5 in box 5 => r6c4<>3

3. if r8c4=3 => r56c4=(59) => r46c5=(23) => r4c6=6 => r1c6=3 => r2c6=2 => r3c5=4 => r2c3=4 => Pattern A => r2c8=6 => r2c1=1 => r2c4=8 => r1c2=2 => r3c2=9 => r3c3=8 => nowhere to place 8 in box 3 => r8c4<>3

=> r1c4 or r2c4=3 => r1c6<>3

4. If r3c5=4 => r2c3=4 => Pattern A => r46c5=(23) => r78c6=(34) => Double Solution => r3c5<>4

=> r2c6=4

5. If r3c3=4 => r3c2=9 => Pattern A => r46c5=(23) => r1c6=2 => r2c1=2 => r1c2=1 => r2c3=8 => r1c3=5 => r1c1=6 => r1c9=3 => no number can go in r2c7 => r3c3<>4

=> r3c2=4
=> r3c3=9


6. If r3c5=8 => r5c4=8 => r68c4=(59) => r1c4=2 => r1c2=1 => r1c3=8 => r1c1=5 => r5c3=5 => r6c1=1 => r9c1=9 => r3c1=2 => r6c2=9 => no number can go in r6c4 => r3c5<>8

=> r5c5=8

7. If r3c5=1 => r1c6=2 => r4c6=6 => r1c2=1 => r2c8=1 => r7c8=6=> r78c7=(45) => UR: r8c4=5 => r8c7=4 => r8c5=3 => nowhere to place 3 in column 6 => r3c5<>1

=> r3c5=2
=> r78c5=(14) => r8c4=5
=>r78c6=(39) => r8c26=(39) => UR:r7c2<>(39)
=> Puzzle solved

I hope I haven't let too many typos slip in there. As for the three step solution, I'm sorry I don't have time to translate that now, but I'm sure you can figure it out yourselves if you are interested.

regards
RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby Carcul » Wed Apr 12, 2006 11:20 am

RW wrote:If it helps I can translate it to fit the original "ancient toughest".


Interesting and shorter solution RW. Congratulations.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Myth Jellies » Thu Apr 13, 2006 5:56 am

Carcul wrote:Since I have discovered a logical solution for the following puzzle...


Only true if you catagorize brute force methods as logical.

Algorithmic Information Theory is a relatively new branch of mathematics which actually quantifies theory versus brute force. Specifically, it states that for a theory to be a theory, it must be simpler than the data it describes. In our sudoku problem, that usually means that the number of candidates you use in your "theory" to eliminate a specific candidate or set of candidates needs to be able to be less than the number of "data" candidates you use to "crash the puzzle" if you just assumed that the candidate you eliminated was true. In the case of Carcul's SIN and RW's trailing method, the number of candidates in the "theory" is always identical to the number of candidates in the "data", therefore there is no theory. Methods are either theoretical or brute force, and so, unfortunately, Carcul and RW's solutions are just as brute force as Ariadne's Thread. So keep on plugging.

For more on Algorithmic Information Theory, you might check out these links:
http://plus.maths.org/issue37/features/omega/
http://www.umcs.maine.edu/~chaitin/
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Thu Apr 13, 2006 10:09 am

Myth Jellies wrote:In the case of Carcul's SIN and RW's trailing method, the number of candidates in the "theory" is always identical to the number of candidates in the "data", therefore there is no theory.

Would you please illustrate with a simple example ... preferably from Carcul's or RW's posts ... of what and how you are "counting?"

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques