## AIroot - universal solving technique

Advanced methods and approaches for solving Sudoku puzzles
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: 1000
Joined: 16 March 2006

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.

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

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

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:

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

BF3,BH3,BH=6
GH2,IH2

GH6,IH6

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

IE5,IF5 (block iteraction)

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

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

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.

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: 1000
Joined: 16 March 2006

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