Phil's Sudoku Solver

Programs which generate, solve, and analyze Sudoku puzzles

Phil's Sudoku Solver

Postby pjb » Fri Feb 10, 2017 4:36 am

My sudoku solver (philsfolly.net.au) has undergone a major overhaul. Among other things, the number of example puzzles has been greatly expanded. I invite you to check it out and any feedback is welcome.

Phil
pjb
2014 Supporter
 
Posts: 1505
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby pjb » Sat Feb 11, 2017 10:27 pm

Apologies for the missing images in the help files (due to an issue on the hosting we site). This is now resolved.
Phil
pjb
2014 Supporter
 
Posts: 1505
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby Leren » Sun Feb 12, 2017 11:53 pm

Hi Phil, just for fun, tried the following puzzle in your solver ...658.....4......12............96.7...3..5....2.8...3..19..8..3.6.....4....473..

Going through basics, when I get to naked triplets I get the following messages :

Naked triplets of 379 at r1c123
Naked triplets of 568 at r2c129

ie the solver doesn't tell you what the eliminations are, which it does for other moves. The elimination cells are highlighted though.

Later on I get the following message about a UR deletion.

Uniqueness type 1b of 79 at r23c57, allowing 79 to be deleted from r3c55. The column number appears twice.

I also noticed that the solver applies all available naked and hidden singles automatically, and for hidden singles it doesn't say which for row, column or box it is the only remaining candidate.

Leren
Leren
 
Posts: 2578
Joined: 03 June 2012

Re: Phil's Sudoku Solver

Postby Leren » Mon Feb 13, 2017 2:34 am

More on this same puzzle :

Just after all basics were exhausted I clicked on the Fish button and your solver came back with the following (my PM is as close as I can make it with your solver's position) :

Code: Select all
*--------------------------------------------------------------------------------*
|*79      379    *379      | 6       5       8        | 124     124     12       |
| 568     568     4        | 12      79      12       | 79      3       58       |
| 1       2       58       | 47      379     34       | 79      568     568      |
|--------------------------+--------------------------+--------------------------|
| 458     13458   358      | 45      12      9        | 6       1248    7        |
|*46789   146789 *789      | 3       67      1246     | 5       12489  *1289     |
|f45679   14567-9 2        | 457     8       146      | 14      149     3        |
|--------------------------+--------------------------+--------------------------|
| 2457    457     1        | 9       36      36       | 8       257     25       |
| 3       79      6        | 8       12      5        | 12      79      4        |
|*2589    589    *589      | 12      4       7        | 3       1569   *12569    |
*--------------------------------------------------------------------------------*

Your solver's message is : Sashimi swordfish of 9s at r1c1, r1c3, r5c1, r5c3, r5c9, r6c1, r9c1, r9c3, r9c9 eliminating 9 from r5c2

The elimination is correct but I can't see this Swordfish as being described as Sashimi, because the pattern does not become degenerate if the fin (r6c1) is false.

Also, there was a simpler fish in 9's to be seen for the same elimination (from my solver) :

Code: Select all
*--------------------------------------------------------------------------------*
| 79      379     379      | 6       5       8        | 124     124     12       |
| 568     568     4        | 12      79      12       | 79      3       58       |
| 1       2       58       | 47      379     34       | 79      568     568      |
|--------------------------+--------------------------+--------------------------|
| 458     13458   358      | 45      12      9        | 6       1248    7        |
| 46789   14678-9 789      | 3       67      1246     | 5       12489   1289     |
|f45679  *145679  2        | 457     8       146      | 14     *149     3        |
|--------------------------+--------------------------+--------------------------|
| 2457    457     1        | 9       36      36       | 8       257     25       |
| 3      *79      6        | 8       12      5        | 12     *79      4        |
| 2589    589     589      | 12      4       7        | 3       12569   12569    |
*--------------------------------------------------------------------------------*

Finned XWing in 9's r68 c28 with a fin Cell r6c1 => - 9 r5c2

I would have thought that you would have looked for XWings before Swordfishes.

Leren
Leren
 
Posts: 2578
Joined: 03 June 2012

Re: Phil's Sudoku Solver

Postby pjb » Tue Feb 14, 2017 4:08 am

Thank's Leren

Firstly, let me make it clear that this is amateur attempt to produce a puzzle solver that is very easy to operate but still able to attack difficult puzzles. As such there are probably a large number of errors in programming, logic and design, so I apologize for this. Regarding your comments:

1. I thought it would be tedious to provide more details on naked and hidden singles as it would greatly slow down proceedings to stop at each one.
2. I agree I should output the eliminations for naked sets, this is on the to-do list
3. That error in the output for URs is on the to-do list also.
4. With fish I currently put the franken SFs first as they often produce many eliminations. Finned and sahimi X wings & SFs usually only produce a single elimination so I put them last. What I might do is put simple X wings and SFs first, then franken, and leave the finned and sashimi X wings & SFs last
5. That SF is clearly a finned one, so I have a coding error to add to my to-do list.

I appreciate the feedback
Phil
pjb
2014 Supporter
 
Posts: 1505
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby Leren » Tue Feb 14, 2017 8:14 am

Hi Phil, with regard to the singles I was thinking that it would be a good idea to have a Skip all Singles button, that way you have the best of both alternatives.

A lot of the inquiries we get are from people who have simply missed a single and just can't see it. Hodoku has this feature, called All Easy Steps.

Leren
Leren
 
Posts: 2578
Joined: 03 June 2012

Re: Phil's Sudoku Solver

Postby pjb » Thu Feb 23, 2017 7:29 am

Thanks to those of you who pointed out problems both here and by pm. I have attended to all of these I hope. In the process I have also greatly expanded the examples, particularly for fish and uniqueness.
Cheers, Phil
pjb
2014 Supporter
 
Posts: 1505
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby Leren » Thu Feb 23, 2017 9:48 am

Hi Phil, me again. I tried the same puzzle and get a bit further until I come across this move.

r2c12 = 568 568

r5c12 = 468 1458

r9c12 = 258 58

Your solver says : BUG-lite (type 5) at r2c12, r5c12, r9c12 eliminating 8 from r5c1

Maybe I'm a bit thick but I just don't get this, Leren
Leren
 
Posts: 2578
Joined: 03 June 2012

Re: Phil's Sudoku Solver

Postby pjb » Thu Feb 23, 2017 12:10 pm

Good point, I should explain. Having laboured over various strategies to deal with bug-lites and mugs with two or three extra digits without success, I hit upon a simple technique which is to assign the mug digit to one of the cells with extra digits, and then apply naked and hidden singles. If it collapses to a deadly pattern, then that number can be eliminated. In this case, if you assign 8 to r5c1 (put 851 in assign box), it collapses to a bad solution with a deadly pattern in the 6 cells. I could be accused of T&E here, but it will have to do until i find a better approach.

Phil
pjb
2014 Supporter
 
Posts: 1505
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby Leren » Thu Feb 23, 2017 8:03 pm

Hi Phil. I must be really thick. I tried assigning 8 in r5c1 but I can't reduce the 6 cells to a DP via singles.

You don't say what the base digits of the DP are, which you do for a prior Type 1 UR. In fact I get r9c1 = 2 via a naked pair 58 in r9c23 but this is the only 2 in the 6 cells, so I'm still lost.

I think this is the PM for your move (I had to produce this via hand from my solver, so I hope there are no mistakes).

Code: Select all
*-----------------------------------------------------------------------*
| 9      3      7       | 6      5      8       | 124    124    12      |
|*568   *568    4       | 12     9      12      | 7      3      58      |
| 1      2      58      | 7      3      4       | 9      568    568     |
|-----------------------+-----------------------+-----------------------|
| 458    1458   3       | 45     12     9       | 6      1248   7       |
|*468   *1468   89      | 3      7      126     | 5      1248   1289    |
| 4567   145679 2       | 45     8      16      | 14     149    3       |
|-----------------------+-----------------------+-----------------------|
| 2457   457    1       | 9      6      3       | 8      257    25      |
| 3      79     6       | 8      12     5       | 12     79     4       |
|*258   *58     589     | 12     4      7       | 3      1256   12569   |
*-----------------------------------------------------------------------*

Also, my solver sees two 4 cell hidden URs that you do not see.

The first one is 47 in r67c12, which eliminates 4 in r6c1 using Strong links on 4 and 7. The other one is 56 in r38c89 which eliminates 5 in r9c9 via Strong links on 5 and 6.

Leren
Leren
 
Posts: 2578
Joined: 03 June 2012

Re: Phil's Sudoku Solver

Postby pjb » Thu Feb 23, 2017 10:06 pm

Thanks again Leren
My solver doesn't find the (truly) hidden URs you mention because I only look for URs with at least one cell without extras. Perhaps I should look further. With regard to the MUG, I've added the 3 digits to the output. You can follow how singles lead to DP by entering 851 into "Assign" box, with the checkbox for showing singles on. You can then see how singles leads to the answer (in this case rather long winded), and return to puzzle with "Go Back".
Phil
pjb
2014 Supporter
 
Posts: 1505
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby Leren » Fri Feb 24, 2017 4:20 am

Hi Phil,

Adding the 3 DP digits to the output was a good improvement. Using the assign method you outlined "solves" the whole puzzle, with several contradictions, but no indication that the "solution" was invalid.

Interestingly, carefully following the singles allocations list in order, the DP in the 6 cells was not the first contradiction, it was assigning both r2c2 and r3c3 to the same value.

The way I saw it, 8 in r5c1 => 9 in r5c3, 58 in both r9c23 and 2 in r9c1, so although a contradiction would have eventually turned up, it wouldn't have involved 568 in the 6 DP cells.

Also, using the Go back button doesn't remove the invalid sequence of entries in the move list box, which can be very confusing.

So at this stage, the best thing I can do is suggest that you indicate that a "solution" is invalid somehow, and reinstate the entries in the move list box to what they were before you hit the Assign button.

BTW I used to do software testing for a living when I was younger, so all this stuff is very enjoyable for me.

Leren
Leren
 
Posts: 2578
Joined: 03 June 2012

Re: Phil's Sudoku Solver

Postby pjb » Fri Feb 24, 2017 6:42 am

Thank you again
Interestingly it doesn't give you the 2 in r9c1 because it is applying singles only, not line-box or pairs. I agree it should declare the puzzle to be invalid when this is the outcome. I agree also that once the assign box has been used to test a placement, it's output should be removed on returning to the puzzle with the Go Back button.
Cheers, Phil
pjb
2014 Supporter
 
Posts: 1505
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby Leren » Fri Feb 24, 2017 9:21 am

Hi Phil,

The more I think about this method of yours the less I like it.

If you follow your singles placements you get to the following sequence.
...
Naked single: r3c3 must be 5
Naked single: r2c2 must be 5
...

Naked single: r5c2 must be 6
...

Having placed 5 in r3c3 how can you place 5 in r2c2 ? This can only be because, when placing 5 in r3c3, you have failed to mark off the 5's in all cells that r3c3 can see. This, to me, is an incorrect (because incomplete) placement of a naked single. The correct thing to do is to mark off all the 5's that r3c3 can see, recognize that there are no candidates left in r2c2, and conclude that r5c1 can't be 8 via a contradiction in r2c2. This contradiction occurs before your, "placement" of 6 in r5c2 which to me is meaningless, because it comes after a contradiction has already been established.

To me all this move proves is that r5c1 <> 8 via T & E.

In general, even if you were allowed these incomplete cell assignments, and eventually get your required cell DP assignments, this example shows that the singles sequence can be so long and convoluted that in many cases the move is incomprehensible to a human even when it is pointed out to them.

Compare this with complex moves like Exocets and Multi-Fish. IMO it's almost impossible for a human to spot them (at least I can't), but when the computer finds them and all the relevant cells are correctly marked, at least I can then see and understand the patterns.

Leren
Leren
 
Posts: 2578
Joined: 03 June 2012

Re: Phil's Sudoku Solver

Postby pjb » Sun Feb 26, 2017 11:38 am

Leren,
You are quite right in your reservations regarding this BUG-lite type 4 approach which on reflection I have withdrawn from the solver and replaced with a much more limited method which only utilises internal strong links. There is still a lot of improvement possible down the line. For those interested in uniqueness examples, the list in the help file is growing.
Phil
pjb
2014 Supporter
 
Posts: 1505
Joined: 11 September 2011
Location: Sydney, Australia


Return to Software