Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

NEWS:
AIroot - universal solving technique

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
ArtoI

Joined: 20 Sep 2006
Posts: 3
:

Items
PostPosted: Fri Sep 22, 2006 1:34 pm    Post subject: AIroot - universal solving technique Reply with quote

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.

Regards,
ArtoI
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Sep 22, 2006 3:59 pm    Post subject: Reply with quote

It is not clear from your description how this works.

Can you explain it with an example?

Ruud
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
ArtoI

Joined: 20 Sep 2006
Posts: 3
:

Items
PostPosted: Thu Oct 05, 2006 1:34 pm    Post subject: Reply with quote

Procedure of using AIroot is quite simple.

1. put candidate to its' cell
2. check if any of the conflict appear
3. eliminate all candidates, which cause conflict in the new situation
4. repeat 2 and 3 until conflict appear of eliminations are not possible
5. if you want to find out the minimum number of links needed to solve puzzle, eliminate only these candidates, which can be eliminated with the minimum steps in each situation
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 484
:
Location: NJ USA

Items
PostPosted: Thu Oct 05, 2006 4:51 pm    Post subject: Reply with quote

ArtoI wrote:
Procedure of using AIroot is quite simple.

1. put candidate to its' cell
2. check if any of the conflict appear
3. eliminate all candidates, which cause conflict in the new situation
4. repeat 2 and 3 until conflict appear of eliminations are not possible

... until conflict appear ...
and then either give up or backtrack
an ArtoI solver is a backtrack solver
nothing new unless you have insights into selecting the best cells and candidate values to guess on
Back to top
View user's profile Send private message Visit poster's website
ArtoI

Joined: 20 Sep 2006
Posts: 3
:

Items
PostPosted: Wed Oct 11, 2006 1:38 pm    Post subject: Reply with quote

Correct conclusion. The benefit of my sover is, that it finds out the shortest number of links needed to make next elimination. This feature is useful, when comparing the hardest sudokus, because it is possible to make scoring, which is independent from the subjective scoring of different solving techniques and also independent from application order of the different solving techniques.

All backtrack solvers I have seen before use only limited set of conflicts. AIroot method includes them all.

So, improvements are small but usefull.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron
FREE FORUM HOSTING by AtFreeForum. Terms of Service - Privacy Policy
FASHION ACCESSORIES - BLING BLING - LADIES WATCHES - KOREAN CHILDREN CLOTHING - ONLINE BARGAIN STORE - FASHION JEWELLERIES