techniques priority

Advanced methods and approaches for solving Sudoku puzzles

techniques priority

Postby gabriele46 » Tue Jul 03, 2007 11:39 am

Hello,
I am a rookie programmer and I need your help to define the technique's priority in my program.
My dilemma is:
do I have to give priority to the "quality" of the technique or to the length of the chain?

In the following puzzle:


Code: Select all
*--------------------------------------------------------------------*
 | 278    69     369    | 68     12     123    | 4      5      789    |
 | 4      5      369    | 68     7      23     | 289    289    1      |
 | 278    17     178    | 9      5      4      | 278    3      6      |
 |----------------------+----------------------+----------------------|
 | 1      67     2      | 3      68     9      | 678    4      5      |
 | 79     4      679    | 2      168    5      | 13678  1678   378    |
 | 3      8      5      | 7      4      16     | 169    169    2      |
 |----------------------+----------------------+----------------------|
 | 5      2      4      | 1      69     8      | 3679   679    379    |
 | 6      179    1789   | 5      3      27     | 1289   1289   4      |
 | 789    3      1789   | 4      269    267    | 5      12689  89     |
 *--------------------------------------------------------------------*

there is a forcing chain of 5 nodes bringing to a contradiction : if r1c9=8 then r1c9<>8
a forcing chain of 31 nodes: if r3c1=7 then r3c1<>7
and two nishio chains of 2 & 4 nodes: if r8c7 = 9 then r1c2=9 & r1c2<>9 (or if r8c7 = 9 then r1c2=9 & r1c9=9)
In other words: between a forcing chain of 31 nodes and a nishio of 6 nodes, which I should consider first.
Another question: may I post the url of my site where you can play online sudoku, killer sudoku and sudokuX and downoload the free programs for solving and generating?
Thank you for your help,
Gabriele
User avatar
gabriele46
 
Posts: 3
Joined: 01 July 2007
Location: Mantova , Italy

Re: techniques priority

Postby re'born » Tue Jul 03, 2007 12:54 pm

gabriele46 wrote:Hello,

Welcome to the form, Gabriele.:D
gabriele46 wrote:In other words: between a forcing chain of 31 nodes and a nishio of 6 nodes, which I should consider first.


I'm not a programmer, but I would think a chain with 31 nodes should probably be down the list pretty far, especially if the solver is meant to somehow emulate expert human sudoku players. In this case, the matter is even easier for me since your "nishio" deduction can also be seen as a pattern based deduction, namely a Sashimi X-wing.
Code: Select all
*--------------------------------------------------------------------*
 | 278    69*    369    | 68     12     123    | 4      5      789*   |
 | 4      5      369    | 68     7      23     | 289    289    1      |
 | 278    17     178    | 9      5      4      | 278    3      6      |
 |----------------------+----------------------+----------------------|
 | 1      67     2      | 3      68     9      | 678    4      5      |
 | 79     4      679    | 2      168    5      | 13678  1678   378    |
 | 3      8      5      | 7      4      16     | 169    169    2      |
 |----------------------+----------------------+----------------------|
 | 5      2      4      | 1      69     8      | 3679   679    379*   |
 | 6      179*   1789   | 5      3      27     | 1289-  1289-  4      |
 | 789    3      1789   | 4      269    267    | 5      12689  89*    |
 *--------------------------------------------------------------------*

What is better is that when viewed in this way, you can eliminate 9 from both r8c7 and r8c8 with the same move.
re'born
 
Posts: 551
Joined: 31 May 2007

which method to prefer

Postby claudiarabia » Sat Jul 07, 2007 4:41 pm

Hi Gabriele,

I would prefer the Nishio-chain too. Of course you could program, that the solver uses always the method easiest in structure. But I would give the choice to the player that he may choose between a brute-step-solving way, so that he can in the first way solve the puzzle in the shortest way regardless of the difficulty of the methods (mountain climbing). The second way would be that the solver chooses always the easiest method and advances step by step (easy but long serpentine) but I would confine the simple forcing chain to 10 nodes. Life is to short to stumble through the grid in a forcing chain of 30 nodes.

Do you also include the BUG-Lite-method (more then 2 numbers)
in your solver? That would be pretty new.

With best wishes

Claudia
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby gabriele46 » Wed Jul 11, 2007 8:59 pm

Thanks for you replies,
I will, of course, follow your advice.
I have a lot of work to do, but, as I am retired, I have a lot of time.
I'm introducing cycles in my program. Before I was using, as advanced tecniques, only forcing chains (whatever is the value of a bivalue cell,the content of another cell will not change) and a sort of personale trial and error.
The next will be :BUG and Unique rectangles and the possibility to give to the players the choice of tecniques to be used.
Here is the point: the introduction of the tecnique for finding chains and loop, seems, to me, to bring to a complication of the solution.
As usual an example to explain better the dilemma:
This puzzle :
Code: Select all
*--------------------------------------------------------------------*
 | 3479   5      37     | 2367   27     1      | 3467   8      469    |
 | 379    1      8      | 3567   4      567    | 367    2      369    |
 | 347    2      6      | 378    9      78     | 1      5      34     |
 |----------------------+----------------------+----------------------|
 | 2      7      9      | 1      6      3      | 5      4      8      |
 | 8      6      4      | 257    257    257    | 9      3      1      |
 | 5      3      1      | 9      8      4      | 2      6      7      |
 |----------------------+----------------------+----------------------|
 | 367    4      2      | 567    1      567    | 8      9      356    |
 | 67     9      57     | 245678 3      25678  | 46     1      2456   |
 | 1      8      35     | 2456   25     9      | 346    7      23456  |
 *--------------------------------------------------------------------*

is solved by Sudoku Explainer 1.2:
1 x X-Wing
1 x Hidden Pair
1 x XYZ-Wing
3 x XY-Wing
1 x Bidirectional Y-Cycle
1 x Turbot Fish
2 x Bidirectional Cycle
3 x Forcing Chain (here the definition of forcing chain is different from mine)

the new program I developed solves the puzzle with 3 loops:
LOOP, contradiction found, If r5c5=2 then r9c5 = 5, r9c3 = 3,r1c3 = 7,r1c5 = 2
IMPOSSIBLE, 2 is already in r5c5
LOOP, contradiction found, If r5c6=7 then r8c6 = 2, r9c5 = 5,* r5c5 = 7
IMPOSSIBLE, 7 is already in r5c6
LOOP, contradiction found, If r9c5=5 then r7c9 = 5, r7c1 = 3, r9c3 = 5
IMPOSSIBLE, 5 is already in r9c5
I use the name "LOOP" because I don't know the right term to use (somebody can help me to find the correct definition?)

My old program was solving everything in one single step:
if r1c5= 2 then r5c5 = 7, r9c5 = 5,r9c3 = 9 , r8c3 = 5, r7c9 = 5,
r7c1 = 3 - IMPOSSIBLE, also r9c3 = 3, (or,if you prefere, 3 no more possible in row 7)
then r1c5 = 7
The doubt that I have is: can my trial & error be considered logic?
What is the best name of the tecnique I used?
Thank you
Gabriele
User avatar
gabriele46
 
Posts: 3
Joined: 01 July 2007
Location: Mantova , Italy


Return to Advanced solving techniques

cron