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   

New solver using backtracking, still having trouble

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

Joined: 18 Oct 2005
Posts: 8
:

Items
PostPosted: Tue Nov 08, 2005 2:28 am    Post subject: New solver using backtracking, still having trouble Reply with quote

Ok, thanks to the fine advise from this forum i've changed my strategy around and went from logic solving to backtracking. Here is my method sofar:

1. scan for naked singles, hidden singles
2. pick a cell with the least possible candidates
3. create a thread with each option and try to solve via backtracking
4. thread updates constraints at every move, exits when solution is found, ends the current track when any one cell has no possible values due to constraints

The problem I am running into is that i recurse way to far for my stack, on both 32 and 64 bit machines. I segfault on a small subset of boards, here is one that i seg fault on:

Code:
-------------------------------
| _  4  _ | 7  _  _ | _  6  _ |
| _  _  3 | 9  _  _ | _  _  _ |
| _  _  _ | _  _  _ | _  5  7 |
-------------------------------
| _  _  _ | _  _  _ | _  3  _ |
| 2  _  _ | _  8  _ | _  _  _ |
| _  1  9 | _  _  _ | 5  7  _ |
-------------------------------
| 6  _  _ | _  4  _ | _  _  _ |
| _  5  _ | 1  _  _ | _  _  _ |
| _  2  _ | _  _  6 | _  8  4 |
-------------------------------


Here is what it looks like after one scan, including the constraints i've calculated:

Code:
-------------------------------
| _  4  _ | 7  _  _ | _  6  _ |
| _  _  3 | 9  _  _ | _  _  _ |
| _  _  _ | _  _  _ | _  5  7 |
-------------------------------
| _  _  _ | _  _  _ | _  3  _ |
| 2  _  _ | _  8  _ | _  _  _ |
| _  1  9 | _  _  _ | 5  7  _ |
-------------------------------
| 6  _  _ | _  4  _ | _  _  5 |
| _  5  _ | 1  _  _ | _  _  _ |
| _  2  _ | _  _  6 | _  8  4 |
-------------------------------
-------------------------------------------------------------------
|1589     4    1258   |  7    1235   12358  |12389    6    12389  |
|1578   678      3    |  9    1256   12458  |1248   124    128    |
|189    689    1268   |23468  1236   12348  |123489   5      7    |
-------------------------------------------------------------------
|4578   678    45678  |2456   125679 124579 |124689   3    12689  |
|  2    367    4567   |3456     8    134579 |1469   149    169    |
|348      1      9    |2346   236    234    |  5      7    268    |
-------------------------------------------------------------------
|  6    3789   178    |238      4    23789  |12379  129      5    |
|34789    5    478    |  1    2379   23789  |23679  29     2369   |
|1379     2    17     |35     3579     6    |1379     8      4    |
-------------------------------------------------------------------


As you can see not much different, and in fact there are still alot of options.

QUESTION: Other then naked single, hidden single, what are some really fast checks I can run to eliminate options? I'm going for speed here, not logic.

Thanks in advanced. You can check out code here: http://www.smackedassintosh.net/progs/source/sudoku/sudoku-smacked-2.0.tar.gz
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Nov 08, 2005 3:05 am    Post subject: Reply with quote

This puzzle is solved with:
- Line-Box interactions
- Subsets (both naked and hidden)
- Multi-Coloring
- 1 Forcing chain

Line-Box interactions are easy to implement and can be very fast
Subsets can be implemented very fast.

Multi-Coloring is already slower
Forcing chains are even slower

I'd suggest you start with the first 2 methods (or pick an easier puzzle)
There are methods of backtracking, like DLX, that allow you to abandon logic methods completely. Check the code samples posted on this forum.
Back to top
View user's profile Send private message Visit poster's website
xyzzy

Joined: 24 Aug 2005
Posts: 80
:

Items
PostPosted: Tue Nov 08, 2005 11:36 am    Post subject: Re: New solver using backtracking, still having trouble Reply with quote

JacKnife wrote:

3. create a thread with each option and try to solve via backtracking
4. thread updates constraints at every move, exits when solution is found, ends the current track when any one cell has no possible values due to constraints

So you use multi-threading? That's an interesting idea but it's not going to lead you to a very fast solution unless you have many processors.

A depth first search is going to be a lot faster than a breadth first search. Pick one option and go with it. If it doesn't work, you know it's false, so use that bit of information and then pick a new option.
Quote:

QUESTION: Other then naked single, hidden single, what are some really fast checks I can run to eliminate options? I'm going for speed here, not logic.

I've found that for very hard 9x9 sudokus, box-line intersections and subsets can be faster. For most 9x9s, no checks besides singles are useful from a speed perspective.
Back to top
View user's profile Send private message Visit poster's website
JacKnife

Joined: 18 Oct 2005
Posts: 8
:

Items
PostPosted: Tue Nov 08, 2005 3:13 pm    Post subject: Re: New solver using backtracking, still having trouble Reply with quote

xyzzy wrote:
So you use multi-threading? That's an interesting idea but it's not going to lead you to a very fast solution unless you have many processors.


I was writing for a 2 or more proc system, yes. But even on a single proc, by threading I know that one of my threads is starting down the correct path, and the others are not. The thread that is correct should get to the solution much faster then the other threads exaust all options. Thus reducing the total number of necessary steps. This should be true even when contending for a CPU. Oh, and I like threading, its fun.

Quote:

A depth first search is going to be a lot faster than a breadth first search. Pick one option and go with it. If it doesn't work, you know it's false, so use that bit of information and then pick a new option.


The code is actually depth first, save for the very first cell chosen. I only pick a cell to start with in order to split the solution up into threads.

Quote:

I've found that for very hard 9x9 sudokus, box-line intersections and subsets can be faster. For most 9x9s, no checks besides singles are useful from a speed perspective.


I only seem to have trouble with a few very hard 9x9's in fact. And this is exactly what I thinik I was looking for. I'll play around with box-lines and subsets and see what I can come up with.

The other thing I want to do is come up with a more complete check of wether or not a current board is solvable or not. Right now I check for constrained cells that have no option, but I may also check for box-lines that cant have all the numbers.

Once I can solve all the very hard boards without seg-faulting I can tweak with Top91 and Top95.

thanks much for everyones help.
Back to top
View user's profile Send private message Visit poster's website
JacKnife

Joined: 18 Oct 2005
Posts: 8
:

Items
PostPosted: Wed Nov 09, 2005 2:31 am    Post subject: Reply with quote

Ok, this is by far not the fastest out there, but I suppose without using DLX its never going to be: http://www.smackedassintosh.net/progs/source/sudoku/sudoku-smacked-2.1.tar.gz

My problem all along was in checking for unsolvable boards. I had a bug in the code that let some constraints slip by my checks. A re-write there and some added checks and it solves every board I ran up against.

It took out Top95 in 6.518 seconds, and Top91 at 5.286 seconds on an Athlon XP @1.4Ghz. Probably could improve greatly by tweaking much of the code, but I'd say mission accomplished as far as I'm concerned.

I hope some new programmers get some use out of this code. I found most of the existing stuff difficult to follow at times, and impossible at others. I'm not knocking any of it, i'd say the end results show who is more efficient, I'm just saying it was tough for a newbie to dig into algorithims coded buy some of the more advanced members of this forum.

At any rate, thaks to all for your help. I'd say there is more information on this board then there is on the rest of the internet. Thanks again.

JK
Back to top
View user's profile Send private message Visit poster's website
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Wed Nov 09, 2005 3:19 am    Post subject: Reply with quote

JacKnife wrote:
I found most of the existing stuff difficult to follow at times, and impossible at others.

You're not alone.

My perception of the majority of code posted in these forums is that the coding styles and lack of accompanying documentation makes it unintelligible. Perhaps that's deliberate, but I can't really see the point of posting code here that is unintelligible to others.
Back to top
View user's profile Send private message Visit poster's website
xyzzy

Joined: 24 Aug 2005
Posts: 80
:

Items
PostPosted: Fri Nov 11, 2005 2:55 am    Post subject: Re: New solver using backtracking, still having trouble Reply with quote

JacKnife wrote:

I was writing for a 2 or more proc system, yes. But even on a single proc, by threading I know that one of my threads is starting down the correct path, and the others are not. The thread that is correct should get to the solution much faster then the other threads exaust all options. Thus reducing the total number of necessary steps. This should be true even when contending for a CPU. Oh, and I like threading, its fun.

Have you tried to verify your assumption? I've found that an incorrect guess will end in a contradiction faster than a correct guess with end in a solution. Or to put it another way, if you use a depth first search with a decent heuristic, the correct path will be the longest path you searched.

Quote:

The other thing I want to do is come up with a more complete check of wether or not a current board is solvable or not. Right now I check for constrained cells that have no option, but I may also check for box-lines that cant have all the numbers.

That sounds like you are only using naked singles? Hidden singles are much faster than box-line intersections and locked subsets.
Back to top
View user's profile Send private message Visit poster's website
JacKnife

Joined: 18 Oct 2005
Posts: 8
:

Items
PostPosted: Fri Nov 11, 2005 1:31 pm    Post subject: Re: New solver using backtracking, still having trouble Reply with quote

xyzzy wrote:

Have you tried to verify your assumption? I've found that an incorrect guess will end in a contradiction faster than a correct guess with end in a solution. Or to put it another way, if you use a depth first search with a decent heuristic, the correct path will be the longest path you searched.


Ok, your right, I went back and on average there are more guesses for correct paths then incorrect paths. And, at least on my tests, threading is slower then nonthreading, even when an incorrect path is chosen first. So I added threading as an option, default being to not thread.

I must still have a bug somewhere, because this board crashes non-threading everytime:

Code:
-------------------------------
| 8  _  _ | 7  _  _ | _  _  4 |
| _  5  _ | _  _  _ | 6  _  _ |
| _  _  _ | _  _  _ | _  _  _ |
-------------------------------
| _  3  _ | 9  7  _ | _  _  8 |
| _  _  _ | _  4  3 | _  _  5 |
| _  _  _ | _  2  _ | 9  _  _ |
-------------------------------
| _  _  6 | _  _  _ | _  _  _ |
| 2  _  _ | _  6  _ | _  _  7 |
| _  7  1 | _  _  8 | 3  _  2 |
-------------------------------


Quote:

That sounds like you are only using naked singles? Hidden singles are much faster than box-line intersections and locked subsets.


I went back and added line-box intersections, and subsets, as I already checked for hidden singles. With the latest code here is the method (without threads):

scan board function:
- reduce naked singles and hidden singles
- reduce line box intersections
- reduce subsets
- fill in all cells that have only one option
- repeat

function constraintPropagation pseudo code:

start with valid move "thisMove", passed to function
find next available move "nextMove"

if "thisMove" and "nextMove" are for the same cell
copy board and constraints
call constraintPropagation with board + constraint copies starting at "nextMove"

make move "thisMove"
scanBoard
if solved
print success and exit

update constraints
if constraintsError (any cell has no options available, or any box-line cannot have all values)
return

"nextMove" = first move in most constrained cell
if no moves left
return

call constraintPropagation with board + constraint starting at "nextMove"
return


Of the Top95 boards (except #70, that crashes without threads), the most guesses any board had to make was 284 (not counting the scan board fillins). The average was 22 guesses. The most dead ends reached were 138, the average was 9.

Not sure if thats good or not, but thats what I got.
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Nov 11, 2005 3:14 pm    Post subject: Reply with quote

The board you're testing:
Code:
8 . .|7 . .|. . 4
. 5 .|. . .|6 . .
. . .|. . .|. . .
-----+-----+-----
. 3 .|9 7 .|. . 8
. . .|. 4 3|. . 5
. . .|. 2 .|9 . .
-----+-----+-----
. . 6|. . .|. . .
2 . .|. 6 .|. . 7
. 7 1|. . 8|3 . 2

I've had it analyzed by Sudo Cue, and this is what you can expect:

47 Hidden singles
11 Naked singles
6 Line-Box interactions
1 Naked pair
1 Naked triple
1 Hidden pair
2 Multicoloring hits
2 Template eliminations (can also be found by T&E)
4 Tabling hits

In the log, the program wrote:
R1C1 Digit 8 given
R1C4 Digit 7 given
R1C9 Digit 4 given
R2C2 Digit 5 given
R2C7 Digit 6 given
R4C2 Digit 3 given
R4C4 Digit 9 given
R4C5 Digit 7 given
R4C9 Digit 8 given
R5C5 Digit 4 given
R5C6 Digit 3 given
R5C9 Digit 5 given
R6C5 Digit 2 given
R6C7 Digit 9 given
R7C3 Digit 6 given
R8C1 Digit 2 given
R8C5 Digit 6 given
R8C9 Digit 7 given
R9C2 Digit 7 given
Row 7 Digit 7 must be placed in R7C6
R9C3 Digit 1 given
R9C6 Digit 8 given
R9C7 Digit 3 given
R9C9 Digit 2 given
Row 9 Digit 6 must be placed in R9C8
Column 9 Digit 6 must be placed in R6C9
Box 8 Digit 2 must be placed in R7C4
Row 6 Digit 3 must be placed in R6C8
Row 6 only has candidates for Digit 4 in Box 4
Row 6 only has candidates for Digit 7 in Box 4
Column 5 only has candidates for Digit 8 in Box 2
Coloring Digit 3 found an inconsistent color chain
Row 7 Digit 3 must be placed in R7C1
Box 8 Digit 3 must be placed in R8C4
Coloring value 6 found a connected pair
Column 1 only has candidates for Digit 6 in Box 4
Placing Digit 5 in R7C5 forces 2 different Digits in R7C5
Row 7 only has candidates for Digit 5 in Box 9
Row 7 found a Naked Pair with Digits {1,9}
1 candidates for Digit 5 eliminated by a template check
Placing Digit 1 in R3C5 forces 2 different cells to Digit 1 in Column 5
Placing Digit 1 in R1C5 forces 2 different cells to Digit 1 in Column 5
1 candidates for Digit 1 eliminated by a template check
Placing Digit 1 in R8C6 forces 2 different Digits in R8C6
Box 8 Digit 1 must be placed in R7C5
Row 7 Digit 9 must be placed in R7C9
Column 9 only has candidates for Digit 1 in Box 3
Row 1 found a Hidden Pair with Digits {1,6}
Column 6 found a Naked Triple with Digits {1,5,6}
Row 8 Digit 5 must be placed in R8C3
R4C3 has Digit 2 as the only remaining candidate
Box 1 Digit 2 must be placed in R3C2
Row 3 Digit 6 must be placed in R3C4
Column 2 Digit 6 must be placed in R1C2
Column 6 Digit 2 must be placed in R2C6
Column 6 Digit 6 must be placed in R4C6
R1C6 has Digit 1 as the only remaining candidate
Row 5 Digit 6 must be placed in R5C1
Row 4 Digit 5 must be placed in R4C1
Column 6 Digit 5 must be placed in R6C6
R2C4 has Digit 4 as the only remaining candidate
Column 4 Digit 5 must be placed in R9C4
Column 6 Digit 4 must be placed in R8C6
R3C6 has Digit 9 as the only remaining candidate
Row 9 Digit 4 must be placed in R9C1
R9C5 has Digit 9 as the only remaining candidate
Row 8 Digit 9 must be placed in R8C2
Column 2 Digit 4 must be placed in R6C2
Column 1 Digit 9 must be placed in R2C1
Column 3 Digit 9 must be placed in R5C3
Row 1 Digit 9 must be placed in R1C8
Row 3 Digit 4 must be placed in R3C3
R7C2 has Digit 8 as the only remaining candidate
R5C2 has Digit 1 as the only remaining candidate
Row 6 Digit 1 must be placed in R6C4
Row 6 Digit 8 must be placed in R6C3
Row 2 Digit 1 must be placed in R2C9
Column 1 Digit 1 must be placed in R3C1
Column 1 Digit 7 must be placed in R6C1
Box 1 Digit 7 must be placed in R2C3
R1C3 has Digit 3 as the only remaining candidate
R2C8 has Digit 8 as the only remaining candidate
Row 5 Digit 8 must be placed in R5C4
Row 1 Digit 2 must be placed in R1C7
Column 8 Digit 2 must be placed in R5C8
Row 1 Digit 5 must be placed in R1C5
Column 7 Digit 8 must be placed in R8C7
Column 7 Digit 1 must be placed in R4C7
R5C7 has Digit 7 as the only remaining candidate
Column 8 Digit 1 must be placed in R8C8
Row 2 Digit 3 must be placed in R2C5
Column 9 Digit 3 must be placed in R3C9
Column 8 Digit 7 must be placed in R3C8
Column 5 Digit 8 must be placed in R3C5
R3C7 has Digit 5 as the only remaining candidate
Row 4 Digit 4 must be placed in R4C8
Column 7 Digit 4 must be placed in R7C7
Column 8 Digit 5 must be placed in R7C8
All Cells Solved


Testing for contradictions is the best you can do. I've got code for contradictions preceding the code for "verities", but it always finds a contradiction in the implication trees. I only use the basic constraints for these trees, no line-box interactions or anything fancier. So far, it can solve all the puzzles I've encountered.

Ruud.
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Sat Nov 12, 2005 11:33 am    Post subject: Reply with quote

Ruud wrote:
In the log, the program wrote:
...
Placing Digit 5 in R7C5 forces 2 different Digits in R7C5
...
What technique is logging "Placing digit 5 ..."? I'm guessing "forcing chains" ... which I've yet to learn.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Nov 12, 2005 2:31 pm    Post subject: Reply with quote

rkral wrote:
What technique is logging "Placing digit 5 ..."?

It's logged by Tabling, which subsumes Forcing Chains, but in itself belongs to the group "Try this and see what happens".

Forcing Chains is limited to following implications where only 2 candidates are involved, either within a unit (row,col,box) or a cell, whereas tabling is more tree-like. It can recognize that, for example, 2 of 3 candidates in a cell are forced to false in different branches, which causes the 3rd candidate to be true.

Check this topic, if you want to learrn more: http://www.setbb.com/phpbb/viewtopic.php?t=364&mforum=sudoku

Ruud.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming 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