AIroot - universal solving technique

Advanced methods and approaches for solving Sudoku puzzles

AIroot - universal solving technique

Postby ArtoI » Fri Sep 22, 2006 1:34 pm

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

Postby ravel » Fri Sep 22, 2006 2:02 pm

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

Postby Mike Barker » Sat Sep 23, 2006 12:13 pm

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

Postby ArtoI » Fri Sep 29, 2006 5:02 pm

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

Postby tarek » Fri Sep 29, 2006 6:42 pm

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
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ravel » Fri Sep 29, 2006 7:10 pm

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

Postby ArtoI » Sat Oct 07, 2006 1:04 pm

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

Postby ravel » Sat Oct 07, 2006 1:15 pm

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

Postby tarek » Sat Oct 07, 2006 10:34 pm

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

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby gsf » Sun Oct 08, 2006 5:53 am

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

Postby tarek » Sun Oct 08, 2006 1:52 pm

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
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ArtoI » Tue Oct 24, 2006 1:33 pm

Here is one real example for the puzzle "AI Killer Application" and the elimination
order, when solving with AIroot and shortest links. First some comments
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
 ABCDEFGHI
A
B
C
D
E
F
G
H
Ix


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
link techniques and so on.

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

Postby ravel » Tue Oct 24, 2006 3:20 pm

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.

[Added:]The next step
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

Postby ravel » Wed Oct 25, 2006 10:25 am

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<>8
r1c5<>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<>2
r8c9<>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

Postby ArtoI » Wed Oct 25, 2006 10:32 am

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.

ravel wrote:[Added:]The next step
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?

Not with the same link. The notation means, that in the current situation there are three candidates, which can be eliminated by four link length AIroot techique.
ArtoI
 
Posts: 6
Joined: 19 September 2006

Next

Return to Advanced solving techniques