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   

Brute force (DLX) timing vs solving by logic

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

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Sun Oct 26, 2008 1:40 am    Post subject: Brute force (DLX) timing vs solving by logic Reply with quote

Greetings,

I have been wondering about the speed of solving puzzles using a brute force method (Dancing Links) vs Calculations vs a combination of calculations and backtracking.

I have started some testing on this, and here is what I have:

First, I have not written a DLX program yet, so I used "SUDOKU FAST SOLVER v.9" by Ignacio Zelaya (http://www.setbb.com/sudoku/viewtopic.php?t=1586&mforum=sudoku). Since someone indicated it was relatively fast.

My solver can not solve all the top 50000 using just logic, so it is my test of a combination test.

I wanted apples to apples testing, so I compiled both on my laptop, visual C, WIN32 release configuration, 1,83 GHz processor. And I used the top 50000 for the test. Timings were done using NTimer.

The DLX solver took 5.078 seconds (101.56 usec per puzzle)
Combination solver took 2.187 seconds (43.74 usec per puzzle)

I can not test a pure logic method with no backtracking, so I have not times, nor can I claim my solver or the DLX solver are the fastest of the categories.

So, my real question is, are these similar to what other people are seeing? And, is the logic only method feasible, or does the computational time outweigh the backtracking time?

Thanks
brit
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Mon Oct 27, 2008 3:11 am    Post subject: Reply with quote

ok, I found a bug in my code. When I set the code to check for multiple solutions, it found some that were not valid. I missed a check for an invalid condition. So, I fixed it, and I can now find multiple solutions, or verify the uniqueness of a puzzle.

New timings (on 1.83 GHz processor) are :
logic / backtracking:
top 50000 - 1 solution : 2.421 second
top 50000 - verify uniqueness : 3.242 seconds

brute force (dlx):
top 50000 - 1 solution : 5.062 seconds
top 50000 - verify uniqueness : 6.062 seconds

So, unless I find a faster dlx version, it looks like logic and backtracking is the fastest. I tried adding in more logic, and the timings ended up being slower.

The next question would be, can I use the dlx algorithm to do the backtracking portion of the logic / backtracking code?

brit
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Mon Oct 27, 2008 10:54 pm    Post subject: Reply with quote

briturner wrote:
The next question would be, can I use the dlx algorithm to do the backtracking portion of the logic / backtracking code?


Yes, present the logic based solved cells along with the givens to your dlx code as if they were all givens.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Tue Oct 28, 2008 12:42 am    Post subject: Reply with quote

So, here is where my problems comes in.

First off, my sudoku solver is a bit based solver, 81 entry array for the grid, where each cell is initially set to 0x01FF meaning all nine numbers are possible. I then have 27 arrays of 9 indexes each giving the elements of each group.

This makes some things real easy,
Naked singles are any item with only 1 bit set
Hidden singles are found looping through each 9 cells (v), doing
t2 = t2 | (t1 & v); t1 = t1 | v; set t3 to already found singles
~(t2 | t3) & 0x01ff is all the hidden singles

I also have similar methods for locked candidates, and subsets (naked/hidden pairs/triples/quads) all based on array of indexes and bitwise operations.

Guessing and backtracking involves copying the entire 81 word grid and picking an item to guess. I then run the rules for anything new.

There is lots of sub-optimizations possible here (such as only look in groups that have changed for hidden singles, only preform the methods that save you time since sometimes guessing/backtracking is faster than calculations).

The key here is quick recalculations based on the guesses.


I do not see an easy way for the dlx to make a guess and then rerun the calculations based on this. It seems that once you hand it off to the dlx routines, you then rely on it to complete the solution. This may still be faster, but I am not sure.

well, guess I have some stuff to play with during my free time for the next few days.

brit

oh, a few more minor optimization (some involving picking items that the compiler optimizes better), down to 1.984 seconds for top 50000, 2.612 seconds when verifying uniqueness, but I don't see anything else I can do with this method.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Tue Oct 28, 2008 5:41 pm    Post subject: Reply with quote

Greetings,

I am going off to study DLX now for awhile, but if anyone wants to benchmark the current program, I have uploaded it to http://tttarabians.com/sudoku/BB_Sudoku.exe (yep, I also raise horses, as well as write software for airplanes).

It is Windows only, type BB_Sudoko -? for options. It is self timing, but if you want to use an external timer, use -t0 to turn off the 1 second delay used in the internal timer. It is also limited to a depth of 16 for backtracking. Fine for the top 50000 or top 1465, but some puzzles with multiple solutions will fail. I have only tested it with XP.

I use "BB_Sudoku < top50000.sdm" to test the timing.
"BB_Sudoku -d1 < top50000.sdm" will print out all 50000 solutions

I am curious as to how it rates with other peoples solver for raw speed. Once I get the code cleaned up some and commented, I should be posting either parts or the whole thing.

brit
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Oct 28, 2008 8:47 pm    Post subject: Reply with quote

briturner wrote:
I do not see an easy way for the dlx to make a guess and then rerun the calculations based on this. It seems that once you hand it off to the dlx routines, you then rely on it to complete the solution.


My guess, you will need multiple dlx sequences Rolling Eyes

Why ?

Well, there is a difference between logic and brute force. Logic normally will only make the right decisions, brute force don't. So, after a guess, logic solving can lead to empty cells or contradictions and you must be able to check on this.

In fact, there are five possibilities, when invoking more logic solving, after a guess:

1) The logic didn't solve more cells, but led to a contradiction
2) The logic didn't solve more cells, but didn't led to a contradiction
3) The logic solved more cells, but led to a contradiction
4) The logic solved more cells, but didn't led to a contradiction
5) The logic solved the sudoku

It's obvious that in case 1 or 3 the guess was invalid so you must return to the dlx that was last handling that guess, so the next guess must be made for the same cell.

Case 2 also must return to the dlx that was last handling that guess, but in this case the first guess for the next cell must be made.

Case 4 must start a new dlx sequence.

For any dlx sequence (with subsequent logic / dlx / and so on...) that didn't lead to the solution, you must return to the previous dlx sequence. If there are no previous dlx sequences and the sudoku wasn't solved than there was no solution.

My advice for logic handling:
Naked singles
Hidden singles
Locked candidates (pointing pair/box line reduction)
Naked subsets
Hidden subsets

Other possibilities:
X-Wing
Swordfish
Empty Rectangle
Two-string kite
Skyscraper

Good luck.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
garthd

Joined: 29 Apr 2006
Posts: 32
:

Items
PostPosted: Wed Nov 05, 2008 6:26 am    Post subject: DLX vs logic Reply with quote

Comparing DLX and logic based methods are a bit like comparing riding a bike and driving a car. You may still get from A to B...but both the experience and purpose are quite different.

While it is certainly possible to code a fast logic based solver, I believe a well coded backtracking algorithm will almost always be faster than a logic based solver (at least for harder puzzles. For simple puzzles requiring very basic methods, there is probably less difference).

Firstly, a backtracking solver generally will require quite a compact amount of code, while a logic based solver will require a number of different coding approaches to deal with different techniques (so it is that much harder to optimise a logic based solver).

Secondly, a logic based solver usually involves applying techniques (typically from easiest to more advanced), and looping back to the start of the techniques whenever a technique enables the puzzle to be advanced (this loop typically terminates once the puzzle is solved or no more progress can be made by any technique). However, many advanced techniques rely on relatively rare patterns to occur, and may only result in eliminating a small number of candidates. This means you incur an overhead of repeatedly running code looking for various techniques (e.g if a logic based solver contains code to find the swordfish pattern, you may end up running your swordfish code multiple times, but without that code ever contributing to the solving path of the puzzle).

Thirdly, and in contrast to point two above, a backtracking solver is always making some kind of progress. As Lunatic points out, guesses made by a backtracking solver can result in a contradiction which require the solver to backtrack. However this is still 'progress' of a sort because it closes off a potential solving path and hence reduces the search space.

I use Lunatic's brute force solver (this is a DLX alternative brute force solver) in combination with logic based solving. First I run the brute force to validate a single unique solution and store this, then run through a loop of logic based solving methods. Once the logic solver cannot proceed further, it takes a known value taken from the solution and inputs this, and then re-runs the logic based solver. It keeps doing this until the puzzle is solved. This seems quite an efficient way of combining the two approaches.
Back to top
View user's profile Send private message
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