The New Sudoku Players' Forum

[Tony Williams]

Code: Select all

1  | 34|  9
74 |  9|   
3 9| 87|2
-----------
 9 |72 |153   
 3 |  5|9 7
517| 93| 2
-----------
9 3| 5 |  2
   |3  | 96
6  |97 |  5 


If anybody can analytically tell me the next move, I'd be very grateful!

-- Morex.

This doesn't use Milo's but gets the answer - more than one way of skinning these cats

Code: Select all

 - - - - - - - - - - - - - - -
Iteration Number  1
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Digit 6 occurs only in Column 3 - Square 4
Digit  6 not allowed Cell( 1, 3)
Digit  6 not allowed Cell( 2, 3)
Digit 1 occurs only in Column 8 - Square 9
Digit  1 not allowed Cell( 2, 8)
Digit  1 not allowed Cell( 3, 8)
 - - - - - - - - - - - - - - -
Iteration Number  2
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Testing for Pairs/Triplets [Rows]
Row  4 - Digit 4 is a Pair in the same Square ~ Columns =  1, 3
Digit  4 not allowed Cell( 5, 1)
Digit  4 not allowed Cell( 5, 3)
Testing for Pairs/Triplets [Columns]
Col  6 - Digit 1 is a Triplet in the same Square ~ Rows =  7, 8, 9
Digit  1 not allowed Cell( 7, 4)
Digit  1 not allowed Cell( 8, 5)
 - - - - - - - - - - - - - - -
Iteration Number  3
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 40 - Digit  4 only candidate for Cell( 8, 5)
Test all Digits for unique to Row/Col/Sq
 41 - Digit  4 Only position in Column( 1) is Cell( 4, 1)
 42 - Cell( 9, 3) = 4
 - - - - - - - - - - - - - - -
Iteration Number  4
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 43 - Cell( 8, 3) = 1
 44 - Cell( 8, 2) = 5
 45 - Cell( 7, 2) = 7
 46 - Digit  7 Only position in Row( 8) is Cell( 8, 7)
 - - - - - - - - - - - - - - -
Iteration Number  5
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 47 - Digit  6 only candidate for Cell( 3, 2)
 48 - Digit  4 only candidate for Cell( 3, 8)
 49 - Digit  1 only candidate for Cell( 3, 9)
 50 - Digit  8 only candidate for Cell( 2, 9)
 51 - Digit  5 only candidate for Cell( 3, 4)
 52 - Digit  4 only candidate for Cell( 6, 9)
Test all Digits for unique to Row/Col/Sq
 53 - Cell( 5, 4) = 4
 54 - Cell( 7, 7) = 4
All Digit =  4 allocated
 55 - Cell( 1, 8) = 7
All Digit =  7 allocated
 - - - - - - - - - - - - - - -
Iteration Number  6
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 56 - Digit  1 Only position in Column( 4) is Cell( 2, 4)
 57 - Cell( 5, 5) = 1
 58 - Cell( 1, 4) = 2
 59 - Digit  2 Only position in Row( 2) is Cell( 2, 3)
 60 - Cell( 1, 3) = 5
 61 - Digit  5 Only position in Row( 2) is Cell( 2, 7)
All Digit =  5 allocated
 62 - Digit  6 Only position in Row( 1) is Cell( 1, 7)
 63 - Cell( 2, 5) = 6
 64 - Cell( 1, 2) = 8
 - - - - - - - - - - - - - - -
Iteration Number  7
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 65 - Digit  3 only candidate for Cell( 2, 8)
 66 - Digit  8 only candidate for Cell( 6, 7)
 67 - Digit  2 only candidate for Cell( 9, 2)
 68 - Digit  3 only candidate for Cell( 9, 7)
All Digit =  3 allocated
 69 - Digit  6 only candidate for Cell( 5, 8)
 70 - Digit  6 only candidate for Cell( 6, 4)
 71 - Digit  8 only candidate for Cell( 7, 4)
 72 - Digit  1 only candidate for Cell( 7, 8)
 73 - Digit  8 only candidate for Cell( 8, 1)
 74 - Digit  2 only candidate for Cell( 8, 6)
 75 - Digit  1 only candidate for Cell( 9, 6)
All Digit =  1 allocated
 76 - Digit  8 only candidate for Cell( 9, 8)
 77 - Digit  8 only candidate for Cell( 4, 6)
 78 - Digit  2 only candidate for Cell( 5, 1)
All Digit =  2 allocated
 79 - Digit  8 only candidate for Cell( 5, 3)
All Digit =  8 allocated
 80 - Digit  6 only candidate for Cell( 7, 6)
 81 - Digit  6 only candidate for Cell( 4, 3)
All Digit =  6 allocated
 ====================
  Puzzle Solved
 ====================



[Guest]

Ah, but you have used Milo's rules! All of your tests are examples of one of his three.

[Tony Williams]

Ah, but you have used Milo's rules! All of your tests are examples of one of his three.

What I meant was that I hadn't used the Rule that "N Cells contain N Digits"

[Guest]

Isn't that what your "Testing for Pairs/Triplets" does?

[Tony Williams]

Isn't that what your "Testing for Pairs/Triplets" does?

NO, better I define some of the rules I have used :-

Pairs/triplets in a Row/Col, same SQ tests that for a given Digit in a Row/Col that if all the candidates exist only in a single SQ, then we must use this Row/Col for the chosen Digit (since it is the only option for the row/col).

Hence, within tha SQ, we can eliminate the chosen Digit as a candidate from any other cells not in the chosen row/col. If you follow the log file through for the chosen puzzle it should become clear - the log only highlights this rule if it results in exclusions.

The rule "N cells contain N digits" refers to the pencil marks or candidates for a Row/Col/SQ.

Suppose in a row we have candidates (14) (147) (18) (237) (14)

Because (14) occurs twice only then we must use these two cells for Digits 1, and 4 - we don't know which way round but we know that is where they go.

If digit 1, or 4 were to be allocated to any other cell in the row then we do not have a solution. Hence, from this we must eliminate digits 1 and 4 as candidates from all other cells in the row which now becomes

(14) (7) (8) (237) (14) and nicely has now given us (7) and (8) as solutions.

This is a simple case were two digits occupied 2 cells.

The elegance of Milo's generic N-Cells contain N-Digits is that it also applies to :-

(12) (13) (23) ......or (123) (12) (13) or .....etc

Here we have 3 cells containing 3 Digits 1,2,3 and hence these can be eliminted as candidates from all other cells in the (Row/Col/SQ).

Not the easiest of algorithms to program, but extremly elegant and effective.

In the log I posted, then this 'MILO' Rule has not been used at all.

Tony

[Guest]

OK, so the bulk of the work is done by Milo's rule 1 - but this...

"Test all Digits for unique to Row/Col/Sq
41 - Digit 4 Only position in Column( 1) is Cell( 4, 1)
42 - Cell( 9, 3) = 4 "

is rule 3, where N=1 (or rule 2 where N=undecided-1).

Have you coded for more complex problems and it just wasn't necessary here, or do you find your rules sufficient to solve all puzzles?

I'm also interested that you use rule 1 first - It's a while ago now, but I concluded that this was the slowest way to a solution, and ended up coding my solver to use rule 2 until it runs out of things to do and then resort to rule 1 (and if all else fails, test for an x-wing), which always frees it up enough to go back to rule 2.

That said, my solver has lousy performance compaired to some - it's written in Excel VBA and takes up to 45 secs (on a 900Mhz PC) to solve a fiendish or Very Hard puzzle.

Always interested in tips to speed this up...

[Tony Williams]

Have you coded for more complex problems and it just wasn't necessary here, or do you find your rules sufficient to solve all puzzles?

I'm also interested that you use rule 1 first - It's a while ago now, but I concluded that this was the slowest way to a solution, and ended up coding my solver to use rule 2 until it runs out of things to do and then resort to rule 1 (and if all else fails, test for an x-wing), which always frees it up enough to go back to rule 2.

Some of the simpler puzzles are solved purely by rule 1 alone, and as you can see it is always the end-game. BUT that said, I have played around with the order since the rules are organised as a cascade - Placement rules, followed by exclusion rules.

There are more rules than evident here, but if we look at the Puzzle below, then it gets more complex - the pair/triplet in SQ rule seems very effective and hence is fairly high in the cascade.

Below is the log for the Times V Hard example puzzle

Code: Select all


- 4 3 * - 8 - * 2 5 -
6 - - * - - - * - - -
- - - * - - 1 * - 9 4

9 - - * - - 4 * - 7 -
- - - * 6 - 8 * - - -
- 1 - * 2 - - * - - 3

8 2 - * 5 - - * - - -
- - - * - - - * - - 5
- 3 4 * - 9 - * 7 1 -


Code: Select all

 - - - - - - - - - - - - - - -
Iteration Number  1
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 27 - Digit  5 only candidate for Cell( 9, 1)
 28 - Digit  8 only candidate for Cell( 9, 4)
Test all Digits for unique to Row/Col/Sq
 29 - Cell( 5, 1) = 3
 30 - Cell( 6, 1) = 4
 31 - Cell( 6, 6) = 9
 - - - - - - - - - - - - - - -
Iteration Number  2
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 32 - Digit  2 Only position in Column( 1) is Cell( 3, 1)
 33 - Digit  5 Only position in Column( 6) is Cell( 2, 6)
 34 - Digit  9 Only position in Row( 1) is Cell( 1, 4)
 - - - - - - - - - - - - - - -
Iteration Number  3
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 35 - Cell( 2, 5) = 2
 36 - Cell( 2, 4) = 4
 - - - - - - - - - - - - - - -
Iteration Number  4
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Digit 3 occurs only in Row 3 - Square 2
Digit  3 not allowed Cell( 3, 7)
Digit 7 occurs only in Column 5 - Square 5
Digit  7 not allowed Cell( 3, 5)
Digit  7 not allowed Cell( 7, 5)
Digit  7 not allowed Cell( 8, 5)
 - - - - - - - - - - - - - - -
Iteration Number  5
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Testing for Pairs/Triplets [Rows]
Testing for Pairs/Triplets [Columns]
Col  6 - Digit 3 is a Pair in the same Square ~ Rows =  7, 8
Digit  3 not allowed Cell( 8, 4)
Digit  3 not allowed Cell( 7, 5)
Digit  3 not allowed Cell( 8, 5)
 - - - - - - - - - - - - - - -
Iteration Number  6
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Testing for Pairs/Triplets [Rows]
Testing for Pairs/Triplets [Columns]
Testing for x,y Pairs of Digits [Rows]
Testing for x,y Pairs of Digits [Columns]
Testing N-Cell Candidates [Rows]
N-Cell Rule - Candidates = 17 in  row 8, Columns =14
Digit  7 not allowed Cell( 8, 2)
Digit  1 not allowed Cell( 8, 3)
Digit  7 not allowed Cell( 8, 3)
Digit  1 not allowed Cell( 8, 5)
Digit  7 not allowed Cell( 8, 6)
 - - - - - - - - - - - - - - -
Iteration Number  7
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Testing for Pairs/Triplets [Rows]
Testing for Pairs/Triplets [Columns]
Testing for x,y Pairs of Digits [Rows]
Testing for x,y Pairs of Digits [Columns]
Testing N-Cell Candidates [Rows]
Testing for X_Wings [Rows]
X_Wing Rule - Digit   6 at Rows  1 & 9 are a Pairs into Columns =  69
Digit  6 not allowed Cell( 4, 9)
Digit  6 not allowed Cell( 7, 6)
Digit  6 not allowed Cell( 7, 9)
Digit  6 not allowed Cell( 8, 6)
Testing for X_Wings [Columns]
 - - - - - - - - - - - - - - -
Iteration Number  8
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 37 - Digit  9 only candidate for Cell( 7, 9)
Test all Digits for unique to Row/Col/Sq
 38 - Cell( 5, 7) = 9
 - - - - - - - - - - - - - - -
Iteration Number  9
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 39 - Cell( 5, 8) = 4
 - - - - - - - - - - - - - - -
Iteration Number  10
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 40 - Digit  2 Only position in Column( 8) is Cell( 8, 8)
 41 - Cell( 8, 7) = 8
 - - - - - - - - - - - - - - -
Iteration Number  11
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 42 - Digit  6 only candidate for Cell( 3, 7)
 43 - Digit  5 only candidate for Cell( 6, 7)
 44 - Digit  3 only candidate for Cell( 8, 6)
 45 - Digit  6 only candidate for Cell( 9, 9)
 46 - Digit  3 only candidate for Cell( 3, 5)
 47 - Digit  1 only candidate for Cell( 4, 7)
 48 - Digit  2 only candidate for Cell( 5, 9)
 49 - Digit  7 only candidate for Cell( 6, 5)
 50 - Digit  7 only candidate for Cell( 7, 6)
 51 - Digit  3 only candidate for Cell( 7, 8)
 52 - Digit  1 only candidate for Cell( 8, 4)
 53 - Digit  2 only candidate for Cell( 9, 6)
 54 - Digit  6 only candidate for Cell( 1, 6)
 55 - Digit  3 only candidate for Cell( 2, 7)
 56 - Digit  8 only candidate for Cell( 2, 8)
 57 - Digit  7 only candidate for Cell( 3, 4)
 58 - Digit  3 only candidate for Cell( 4, 4)
All Digit =  3 allocated
 59 - Digit  5 only candidate for Cell( 4, 5)
 60 - Digit  8 only candidate for Cell( 4, 9)
 61 - Digit  1 only candidate for Cell( 5, 5)
 62 - Digit  6 only candidate for Cell( 6, 8)
 63 - Digit  4 only candidate for Cell( 7, 7)
 64 - Digit  7 only candidate for Cell( 8, 1)
 65 - Digit  1 only candidate for Cell( 1, 1)
 66 - Digit  7 only candidate for Cell( 1, 9)
 67 - Digit  1 only candidate for Cell( 2, 9)
 68 - Digit  6 only candidate for Cell( 4, 2)
 69 - Digit  2 only candidate for Cell( 4, 3)
All Digit =  2 allocated
 70 - Digit  8 only candidate for Cell( 6, 3)
 71 - Digit  6 only candidate for Cell( 7, 5)
 72 - Digit  9 only candidate for Cell( 8, 2)
 73 - Digit  6 only candidate for Cell( 8, 3)
All Digit =  6 allocated
 74 - Digit  4 only candidate for Cell( 8, 5)
All Digit =  4 allocated
 75 - Digit  7 only candidate for Cell( 2, 2)
 76 - Digit  9 only candidate for Cell( 2, 3)
All Digit =  9 allocated
 77 - Digit  5 only candidate for Cell( 3, 3)
 78 - Digit  5 only candidate for Cell( 5, 2)
All Digit =  5 allocated
 79 - Digit  7 only candidate for Cell( 5, 3)
All Digit =  7 allocated
 80 - Digit  1 only candidate for Cell( 7, 3)
All Digit =  1 allocated
 81 - Digit  8 only candidate for Cell( 3, 2)
All Digit =  8 allocated
 ====================
  Puzzle Solved
 ====================



The Unique rule starts off immediately with 2 placements, and is always the end-game. I have been changing the Cascade order mainly to test the rules, rather than to omptimise performance - does it really matter that it takes 45 secs ?

You can see that N-Cell, and X-wing both get used here - but rememember the log only highlights those instances that result in exclusion orders taking effect so the hit rate is far higher than appears, especially for X,Y digit pairs - many identified, but sufficiently late that no further exclusions took place.

[Guest]

does it really matter that it takes 45 secs ?

Well, no, but it does bug me that other people are solving them in less than a second. I know VBA isn't exactly an efficient programming environment, but it still seems way out.

Do you have any tricks to decide which rules to apply, or which units to test? The one really effective thing I did speeded things up by a factor of 5-10 (yes I was taking up to 10 minutes before!), was to keep a trail of affected units, and follow that trail.

So, I start with a list of units 1-27, and test each one in turn, if any cell is changed, then that cell's 3 units (1 row, 1 col & 1 box) are put on the end of the list (if they don't appear elsewhere).

This means that rather than looping round all 27 units every time, I'm only ever testing units that might bear fruit because something has changed since they were last tested.

[Tony Williams]

does it really matter that it takes 45 secs ?

This means that rather than looping round all 27 units every time, I'm only ever testing units that might bear fruit because something has changed since they were last tested.

Sounds good, but my solver already complicated enough, and I still haven't got the full rule set for Generic N-Digits in N-Cells, and swordfish (see other dialogues on this one).

One thing I might try, but it will cause complete chaos, even if only in the logs, is that whenever a candiate list for a cell is reduced to 1 by an exclusion rule, to immediately call (recursively) the Unique Placement subroutine, which will then plce that digit, and eliminate as candidates in row/col/SQ, and if any more single candidates call recursively etc,...etc,....etc..... but, I wil need to ensure that routines involved are set correctly in VBA for recursion....could be interesting, but what effect it will have on solution times and/or the log files, I have no idea.

[Guest]

Yes, I thought of that, but it didn't make much difference (less than a second).

Somehow, I feel like it ought to be possible to aim at the units most likely to help, which are probably the ones with the most known values, but I think it would take as much time to decide what to do as you save by doing it! Any thoughts?

[Tony Williams]

Yes, I thought of that, but it didn't make much difference (less than a second).

Somehow, I feel like it ought to be possible to aim at the units most likely to help, which are probably the ones with the most known values, but I think it would take as much time to decide what to do as you save by doing it! Any thoughts?

If you send me a private mail - with your name + e-mail address (I think admin has already suggested that you register yourself as it makes comms easier) , I could share my EXCEL file with you and you could make of it what you will. you may find that I have invested in more data structures which reduces computation, although the code may appear more lengthy and complex.

[gnatzkopp]

Always interested in tips to speed this up...

Hi, I've written my solver in Java. It can handle puzzles up to the complexity of X-Wing. It comes to an end in less than 100ms.

My trick for performance is to not just maintain a board with pencilmarks (possibles) but also additional Cell and Number Objects. Whenever pencilmarks are removed I also update the corresponding Cell and Number Objects. This at first is a slight overhead, but pays off because these objects will 'shout out loud' when they are completed. So I never have to search if for a Cell there is only one possible left or if for a number there is only one place left within a row/column/box.

Does that make sense?

[Guest]

There must be a third algrothim. Any ideas?

This is where it gets complicated, and where my own program (also in Delphi) starts "guessing". You have to look for what other information you can glean about number placement - somtimes you can determine which row or column a number must be in without being able to identify the exact cell. This in turn can eliminate cells in other blocks leaving only a single possibility. For an example see the thread http://forum.enjoysudoku.com/viewtopic.php?t=36 and see how the position of the 5 in block 1 is determined.

Simes

[Guest]

Not sure what the fuss is in writing a solver program. I've written one in VB which is about a page long and solves any puzzle instantly. It's simple. With the same code I can create problems and return the number of solutions to a particular combination if there are more than one. It'll also tell me if there are no solutions.

[Animator]

The 'fuss' is about writing a program which solves it using only logic, no guessing at all.

And which can handle the more difficult puzzles aswell. Very hard puzzles and beyond that (although there is no easy way to generate them)