AIroot - universal solving technique

Advanced methods and approaches for solving Sudoku puzzles

Postby RW » Wed Oct 25, 2006 1:47 pm

Terve Arto

Just read about your remarkable puzzle in my local newspaper. I don't want to post other peoples puzzles here, published or not, but I was hoping that maybe you want to share it with the sudoku community. It should give people something to think about for a while, at least Sudoku Explainer needs a little fix - there's a typo in the phrase "The Sudoku Emplainer failed to solve this Sudoku using logical rules only"...

I think I understand better now the point of your technique. A technique that finds the solution to all puzzles is nothing new, but if it can find the shortest solution, then it could be something quite revolutionary. At least I haven't seen anything like that before. I don't quite understand your terminology though. Around here the word 'link' is usually used for strong or weak links between 2 candidate cells. It seems you use the word link in a totally different meanig. Could you explain exactly what the links indicate, preferably with the help of a 4 or 5 link AIroot elimination, in such a way that everybody can understand what a n link elimination is?

Also, if you wish to share your methods for creating hard sudokus, I think many people here would appreciate that.

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

Postby ronk » Wed Oct 25, 2006 2:27 pm

ArtoI wrote:
ravel wrote:Where is this puzzle from ? It has ER 9.9, but i could not find it under the 9.9-puzzles in my list.

I have created it by myself.

ArtoI, very nice puzzle. One permuted version looks like:
Code: Select all
 . . 1 . . 2 . . 3
 . 4 . . 5 . . 2 .
 . . . 6 . . . . .
 . . 2 . . 7 . . 8
 . 5 . . 6 . . 7 .
 8 . . 9 . . 4 . .
 . . 5 . . 6 . . 1
 . . . . 7 . . 3 .
 6 . . 1 . . 8 . .

It is a variant of the diagonal of diagonal patterns -- which has a diagonal in every 3x3 box -- that Ocean postedhere andhere (and others elsewhere). Your variant has 3 missing clues, which I permuted to place in the corner boxes.

[edit: add link to puzzle source]
Last edited by ronk on Fri Feb 11, 2011 1:12 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Thu Oct 26, 2006 1:55 pm

ArtoI,

since you are not very loquacious, let me guess, what you are doing.
Given a grid, where the arsenal of implemented techniques dont help, test each candidate:

Set the cell to the candidate and apply all placements and eliminations that can be done now simultaneously as one "link" (batch move).

Doing this e.g. for 5 in r9c5 in the starting grid you can apply singles, locked candidates and x-wing in the first link, singles pair, locked candidates and coloring in the second. Then singles will be enough in the third to kill the last 9 in block 1 and column 1 in the third link.

For the solution make all eliminations/placements with the minimum number of "links".

Assuming this, i wondered, how much "links" my first step in the first solution would take: r7c8<>8 needs 5 "links" with common advanced techniques (then i have two 4's in column 8 - but i saw now, you need 6 links for HG8 ??).

This method would not reflect better than others, how human solvers would try to solve a hard puzzle, but it would provide another rating, namely the sum of links needed for the solution (and it can be calculated a lot faster than the RMS).

Since i cannot calculate it with my program, i still wonder, what the sum of needed "links" would be for the 3 solutions i got from my program for your puzzle.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ArtoI » Fri Nov 03, 2006 4:07 pm

RW wrote:
Just read about your remarkable puzzle in my local newspaper. I don't want to post other peoples puzzles here, published or not, but I was hoping that maybe you want to share it with the sudoku community. It should give people something to think about for a while, at least Sudoku Explainer needs a little fix - there's a typo in the phrase "The Sudoku Emplainer failed to solve this Sudoku using logical rules only"...

Sure, this puzzle must be:

Code: Select all
AI Escargot

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


RW wrote:I think I understand better now the point of your technique. A technique that finds the solution to all puzzles is nothing new, but if it can find the shortest solution, then it could be something quite revolutionary. At least I haven't seen anything like that before. I don't quite understand your terminology though. Around here the word 'link' is usually used for strong or weak links between 2 candidate cells. It seems you use the word link in a totally different meanig. Could you explain exactly what the links indicate, preferably with the help of a 4 or 5 link AIroot elimination, in such a way that everybody can understand what a n link elimination is?


The elimination link might be more accurate term for my links, sometimes these lead conflicts and then number can be eliminates. Anyway the links are one way interactions. For example in the following subpuzzle:

Code: Select all
      A     B    C         D    E    F        G     H    I
    +-------------------+-------------------+-------------------+
A   |  167   67    .    |    .    .    .    |    .    .    .    |
B   |  189  289    .    |    .    .    .    |    .    .    .    |
C   |    .    .    .    |    .    .    .    |    .    .    .    |
    +-------------------+-------------------+-------------------+
D   |  167  367    .    |    .    .    .    |    .    .    .    |
E   |  189    .    .    |    .    .    .    |    .    .  589    |
F   |    .  389    .    |    .    .    .    |    .    .  589    |
    +-------------------+-------------------+-------------------+
G   |    .   45   57    |    .    .    .    |   52  569    .    |
H   |    .   36    .    |    .    .    .    | 2346    . 2456    |
I   |   15    .    .    |    .    .    .    |   56    . 1235    |
    +-------------------+-------------------+-------------------+


AI5 again mean, that this number can be eliminates from bottom left corner and AI=1, that number is one. Lets look at it.

Initial:
AI=1 -> AA1,AB1,AD1,AE1,II1

First link.
AIroot link one BD8,BD9,BD=3 (unique rectangle), GG5,GG=2,HG5, (block interaction)

Second link:
BF3,BH3,BH=6
GH2,IH2

Third link:
GH6,IH6

Fourth link:
GI5 (triples 3,4,5 at GH,IH,II)

Fifth link;
IE5,IF5 (block iteraction)

Sixth link:
BB8,BB9,BB=2 (six cell unique conflict)

So at the next step or links all possible eliminations will be made and if this lead to conflict somewhere in the puzzle the number can be eliminated.

I don't know, if this clarify anything, but atleast it is other example, how links continues.
ArtoI
 
Posts: 6
Joined: 19 September 2006

Postby ravel » Fri Nov 03, 2006 5:23 pm

Thanks, Arto,

your explantion seems to confirm, what i expected, what you mean with a (elimination) link.

Since i saw, that you have an own rating system and mine is overstrained by the super hard puzzles posted in the hardest thread in the last days (after i showed yours there, the first one, my program could not solve), i would be very interested, how you would rate them.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby RW » Tue Nov 07, 2006 8:57 am

ArtoI wrote:So at the next step or links all possible eliminations will be made and if this lead to conflict somewhere in the puzzle the number can be eliminated.

I don't know, if this clarify anything, but atleast it is other example, how links continues.

Yes, it did clarify it, I now believe I understand how the links are counted. This way you sure can find the shortest way to a solution, using the implemented techniques, from a very analytical POV. As for rating difficulty, I'm not sure how well this reflects the difficulty experienced by a human solver.

A little analogy: Say the sudoku puzzle is a giant maze and you are trapped in the middle of it. There is only one way out. In a hard puzzle, there's only walls and no openings. Some walls are made of paper, some of wood, some brick walls and some are reinforced concrete. AIroot finds the shortest way out using an army of bulldozers that easily can smash through all walls but the reinforced concrete walls. If you were a lonely human being, you'd probably first try to find your way out through the paper walls, then if it doesn't work, you'd get some tools to take down the wooden walls and so on. Personally, I like the way gsf's program do this by first trying all propositions with singles, then adds more and more techniques to the propositions to find out what tools are really needed to get through the maze.

Looking at the top 10 list of your website, your rating system has rated tarek's fluid drive #1 and your escargot a lot harder than all other puzzles. But the difference between them is very small (fluid drive: 2038, escargot: 2043). For a human solver your escargot would be a lot harder than the fluid drive, because it doesn't solve with only basic techniques in the propositions. Puzzles that solves with propositions that require only singles and locked candidates can be done "quite easily" by analysing strong links and grouped strong links, or just by imagining the number there and reading ahead for a contradiction. Add naked or hidden subsets to the proposition constraints and it get's a lot harder to find for both techniques. If coloring, multi coloring or other nishiopatterns are required within the propositions, I guess almost any human solver will have to use pure T&E to find the contradictions. In your terminology: an elimination using 8 links with only singles should be rated lower than an elimination that uses 3 links with a fish conflict.

Despite this little critiscism, I do think that there's some bonuses that comes with your rating system, namely that it batches the eliminations according to how long the elimination chains would be. If this would be combined with a gradual increase of techniques used in the links, I think it would be a very reliable rating system. Only thing that remains then would be to backtrack through the solution to see how many of the chains where really neccessary...

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

Postby gsf » Tue Nov 07, 2006 2:39 pm

RW wrote:Despite this little critiscism, I do think that there's some bonuses that comes with your rating system, namely that it batches the eliminations according to how long the elimination chains would be. If this would be combined with a gradual increase of techniques used in the links, I think it would be a very reliable rating system. Only thing that remains then would be to backtrack through the solution to see how many of the chains where really neccessary...

I called this girth (not gurth) in the proposition formulation
girth can be limited to g by Pg(C)

if you look at --man for -qhardest you'll see that I (arbitrarily) set the easiest
proposition to
Code: Select all
FNP4(FN)E(P<=9)V(2)

which limits the girth to 4 and via E(P<=9) limits the number of propositions to 9
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Previous

Return to Advanced solving techniques