## AIroot - universal solving technique

Advanced methods and approaches for solving Sudoku puzzles

### AIroot - universal solving technique

Hello,

I have just invented universal technique AIroot, which solves all puzzles (at least have solved so far). It is based on the fact that, there can arrive three types on conflicts, when solving.

1. basic conflicts - there are only N-1 different candidates in N cell in the area
2. fish conflicts - when eliminating number from N rows/columns, it will disappear also from N+1 columns/rows.
3. unique conflicts - this pattern means multiple solutions

When all candidates, which cause conflict immediately, have been eliminated (AIroot link 1), it is time to start linking. Linking take into account all candidates, which cause any type of conflict immediately in the new situation. If any of the conflicts appear in second link, the number can be eliminated by some AIroot link 2 technique. So, the AIroot method is some kind of enlargement of the Trebor's Tabling, because it takes into account all conflict types.

All other techniques can be also be converted to the AIroot. For example: single = AIroot link 1 technique. In normal single all candidates, which can be seen by single cell, can be eliminated. In the AIroot the way of thinking is opposite, illegal candidate cause basic conflict (empty cell), so it can be eliminated. Respectively all fish like and UR techniques are AIroot link 1 techniques.

XY-wings and Bowman Bingo are AIroot link 2 techniques and so on.

It is also quite easy to invent new solving techniques by using simple principles of AIroot. For example:

Code: Select all
`Double UR, AIroot link 2:-----------------------------------------------------------------|  128   348    x    |    x    x    x    |    x   348    128    ||  127   347    y    |    y    y    y    |    y   347    127    |`

number 8 can be eliminated from cells x and number 7 from cells y

Code: Select all
`Unique-fin-fish, AIroot link 2:------------------------------------------------|   1   1   x   |   x   1   x   |   x   x   1   ||   .   .   .   |   .   .   .   |   .   .   .   ||  187 187  .   |   .   .   .   |   .   .   .   | -----------------------------------------------|   y   .   .   |   .   .   .   |   .   .   .   ||   y   1   1   |   x   1   x   |   x   x   1   ||   y   .   .   |   .   .   .   |   .   .   .   | -----------------------------------------------|  187  187 .   |   .   .   .   |   .   .   .   ||   .    .  .   |   .   .   .   |   .   .   .   ||   1    1  x   |   x   1   x   |   x   x   1   |-------------------------------------------------`

1 = candidate 1 exist in these cells
187 = only these candidates exist
x = candidate 1 doesn't exist
y = candidate 1 can be eliminated

Code: Select all
`subset-fish AIroot link 2:------------------------------------------------|   x   1y  x   |   x   1   x   |   x   x   1   ||   .    y  .   |   .   .   .   |   .   .   .   ||   .    y  .   |   .   .   .   |   .   .   .   | -----------------------------------------------|   y  132  y   |   .   .   .   |   .   .   .   ||   1y  1y  1y  |   x   1   x   |   x   x   1   ||   y  132  y   |   .   .   .   |   .   .   .   | -----------------------------------------------|   .    y  .   |   .   .   .   |   .   .   .   ||   .    y  .   |   .   .   .   |   .   .   .   ||   x   1y  x   |   x   1   x   |   x   x   1   |-------------------------------------------------`

1 = candidate 1 exist in these cells
132 = only these candidates exist
x = candidate 1 doesn't exist
y = candidate 2 can be eliminated

Maybe some of these examples have been already invented.

Regards,
Arto I
Last edited by ArtoI on Sat Oct 07, 2006 8:41 am, edited 1 time in total.
ArtoI

Posts: 6
Joined: 19 September 2006

Hi ArtoI,

Please put the samples in Code-sections to keep the format (mark the - reformatted- text and press the "Code"-button, see also here) like this:
Code: Select all
`-------------------------------------| 1   1   x | x   1   x | x   x   1 || .   .   . | .   .   . | .   .   . || 187 187 . | .   .   . | .   .   . |-------------------------------------| y   .   . | .   .   . | .   .   . || y   1   1 | x   1   x | x   x   1 || y   .   . | .   .   . | .   .   . |-------------------------------------| 187 187 . | .   .   . | .   .   . || .   .   . | .   .   . | .   .   . || 1   1   x | x   1   x | x   x   1 |-------------------------------------`

Nice samples, did you find them in a "real" puzzle?
ArtoI wrote:...AIroot, which solves all puzzles (at least have solved so far)...
Have you tried one from the hardest sudokus list?
ravel

Posts: 998
Joined: 21 February 2006

Hi, ArtoI and welcome to the forum. I've been working on a very similar concept which I called the Sudoku Unification Model. Although I'm not ready to make quite the claims you have the approaches appear to be very useful. You may find this post helpful.
Mike Barker

Posts: 458
Joined: 22 January 2006

ravel wrote:Hi ArtoI,

Please put the samples in Code-sections to keep the format (mark the - reformatted- text and press the "Code"-button, see also here) like this:
Code: Select all
`-------------------------------------| 1   1   x | x   1   x | x   x   1 || .   .   . | .   .   . | .   .   . || 187 187 . | .   .   . | .   .   . |-------------------------------------| y   .   . | .   .   . | .   .   . || y   1   1 | x   1   x | x   x   1 || y   .   . | .   .   . | .   .   . |-------------------------------------| 187 187 . | .   .   . | .   .   . || .   .   . | .   .   . | .   .   . || 1   1   x | x   1   x | x   x   1 |-------------------------------------`

Nice samples, did you find them in a "real" puzzle?
ArtoI wrote:...AIroot, which solves all puzzles (at least have solved so far)...
Have you tried one from the hardest sudokus list?

Yes I have and it is obvious, that AIroot can solve these hardest sudokus, because the monster chain you have used, is subset of AIroot.

You have used singles, tuples and box interactions from basic conflicts, while AIroot includes also other subsets
You have used x-wings from fish-like conflicts, while AIroot includes also swordfish, jellyfish, squirmbag anf every method with fins.
You have used UR type 1 from unique conflicts while AIroot includes also other UR types and also 6,8,10 etc..cells unique conflicts.

It is also obvious that AIroot solves all puzzles lesser or same amount of needed steps for example Ocean #1/M21/D21 (17 steps) and top1465 #77 (toughest) (10) needed six steps.
ArtoI

Posts: 6
Joined: 19 September 2006

So you've grouped the solving techniques into 3 groups.........

But is there anything new?

could you provide an example of this & how is it different from what we use here

tarek

tarek

Posts: 2647
Joined: 05 January 2006

ArtoI wrote:It is also obvious that AIroot solves all puzzles lesser or same amount of needed steps for example Ocean #1/M21/D21 (17 steps) and top1465 #77 (toughest) (10) needed six steps.
Very interesting. Can you show us the steps for one of the puzzles please?
ravel

Posts: 998
Joined: 21 February 2006

tarek wrote:But is there anything new?

The new thing in the AIroot is, that it decribes all solving techniques by three types of conflicts and simple linking principle. Before all solving techniques are decribed by huge sets of basic, medium and advanced soving techniques. Of cource, there is not much new, if you already know these techniques.

AIroot is also, if not only, at least the easiest way to find out the minimum number of links, which are needed to solve a puzzle. Unfortunately, I don't have any example of needed links (or steps) yet, because method is not like chain, which have single steps from beginnig to the end. Root method has forks and most of these forks are irrelevant for the solution. I haven't find out good way to eliminate irrelevant forks yet.
ArtoI

Posts: 6
Joined: 19 September 2006

How could you say then, that you "needed six steps" for the 2 toughies ? Did you mean 6 guesses (the known maximum needed is 2) ?
ravel

Posts: 998
Joined: 21 February 2006

A universal solving technique with no true examples for the community to evaluate unfortunately holds no merit

tarek

tarek

Posts: 2647
Joined: 05 January 2006

tarek wrote:A universal solving technique with no true examples for the community to evaluate unfortunately holds no merit

airoot description and my comment on the programmer's forum here
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gsf wrote:
tarek wrote:A universal solving technique with no true examples for the community to evaluate unfortunately holds no merit

airoot description and my comment on the programmer's forum here

Intersting.........

tarek

tarek

Posts: 2647
Joined: 05 January 2006

Here is one real example for the puzzle "AI Killer Application" and the elimination
about the notations. At the beginning all empty cell contains all
possible candidates (1-9). The co-ordinates of the puzzle are marked
with the alphabets A-I, so that the first letter presents column and
second row.

Code: Select all
` ABCDEFGHIABCDEFGHIx`

The bottom left cell marked by x presents cell AI and the notation AI56,
means that candidates 5 and 6 can be eliminated from the cell AI. The
first number, before elimination list, tells how many links are needed
before eliminations are possible. Zero means, that elimination can be
made by basic techniques or immediate fish/unique conflict. 1 meas
eliminations by AIroot 1 link techniques, 2 meas eliminations by AIroot 2

There will be needed seven links in the most difficult situations. If
somebody can solve this puzzle with lesser links, please let me know.

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

0: AA3678,AB134678,AC234678,AE24789,AF24789,AG2678,AH12789,
BA23467,BC2346,BD234568,BE246789,BH124679,BI24678,
CA2367,CB12346,CD23458,CF23489,CG2367,CH12379,CI23678,
DA1479,DB1469,DD134589,DF13489,DG1246789,DI146789,
EA14678,EC123468,ED135689,EE1236789,EH1689,EI1678,
FA13478,FB13468,FC12348,FE23789,FF3489,FG123678,FH13689,
GA2479,GB124679,GD235789,GF245789,GG2679,GI26789,
HB124567,HC234567,HE25679,HF456789,HG25679,HH15679,
IA2479,IC23479,ID345789,IE24579,IH14679,II46789,

3: EI5,
4: DB2,GG4,HB8,
6: AB9,CB9,HG8,IA8,
5: EH5,
6: EA5,
7: AA2,CH4,IE1,
0: AB5,FB2,
5: BC9,FF6,
7: DF5,
5: FF7,FG5,
5: DA5,
6: CD6,CG4,DB5,EH4,FH5,
4: CH8,DA6,DF2,FE6,
0: BA8,
2: BC15,
4: AE1,CF6,CG5,CH5,EI2,HE1,
0: AH6,
3: CA9,
4: AE5,CA1,DD2,ED7,FE5,GG5,
0: DB7,
0: EH2,
3: CA8,FB9,
0: CB5,HB3,HC9,
2: CG9,DA3,DG3,DI5,GI3,
0: AG5,
0: FA9,
1: CD1,
2: AG3,HG1,
0: HH3,IH3,II3,
2: AF1,GD1,HF3,IA15,
2: AE3,BD9,CD7,CF1,DA2,DB8,EA3,FC7,GA3,GB3,GF1,IC1,ID6,IE6,
0: AF6,AG1,BA1,BI1,CI9,DI3,FF5,FH2,GA68,IA6,IE3,II2,
0: BE5,BI5,EA9,EC5,EE4,EI4,FA25,FC6,GG3,HE8,HG4,IC58,IH8,
0: AC9,AF3,ED2,FE4,FF1,GD4,GF6,GI15,HE3,HF2,HH4,
0: AA15,AC5,AH45,BD7,BE1,BH3,BI3,CF5,CI4,DD6,DF7,EH3,HC1,HH8,ID1,IH2,
0: AA4,AG9,BA9,BC8,BH5,CA5,CB7,CG8,CI1,EC7,EI9,FB5,FC9,FG4,FH7,GA5,GB8,GG1,II5,
ArtoI

Posts: 6
Joined: 19 September 2006

PLease can you explain more detailed, what
3: EI5
means - elimination of 5 in r9c5 with 3 links ?

SE uses a contradiction forcing chain over about 24 cells (with multiple inferences) for this elimination (and i would say at least 14 chaining links).
[edited - first thought r8c5]

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

4: DB2,GG4,HB8,
Does it mean. that you can eliminate 2 from r2c4, 4 from r7c7 and 8 from r2c8 with the same links (cannot see any connection). What is a link?
ravel

Posts: 998
Joined: 21 February 2006

ArtoI wrote:There will be needed seven links in the most difficult situations. If somebody can solve this puzzle with lesser links, please let me know.
How many links are required for each of the following solutions taking 19 RMS (so this puzzle will become the second hardest in my list) ? Steps with singles, locked candidates, subsets and maybe x-wing or UR1 are left out.
Code: Select all
`r7c8<>8, r1c9<>8, r2c8<>8, r9c5<>2, r9c5<>5, r3c2<>9, r7c7<>4, r1c5<>5, r8c9<>8, r2c3<>9, r8c5<>5, r1c7<>8, r2c7<>8, r1c7<>3, r5c9<>3, r9c9<>2, r1c5<>3, r5c8<>8, r1c3<>8r1c5<>5, r1c9<>8, r7c3<>9, r8c5<>5, r3c2<>9, r5c9<>1, r2c4<>2, r8c9<>8, r1c6<>9, r5c9<>3, r7c7<>3, r6c4<>5, r2c4<>7, r9c9<>2, r9c5<>2, r5c8<>8, r7c3<>8, r2c4<>8, r1c6<>2r8c9<>8, r2c3<>9, r7c8<>8, r1c5<>5, r2c7<>8, r7c7<>3, r7c7<>5, r1c7<>8, r3c2<>8, r9c5<>5, r7c3<>9, r1c4<>6, r8c1<>6, r1c1<>2, r5c2<>5, r9c2<>3, r9c5<>9, r2c7<>3, r1c1<>4`
ravel

Posts: 998
Joined: 21 February 2006

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.