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   

How fast is your (non-brutal force) solver?

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

Joined: 27 Sep 2008
Posts: 4
:

Items
PostPosted: Mon Sep 29, 2008 4:27 am    Post subject: How fast is your (non-brutal force) solver? Reply with quote

I have seen some logic based solver taking longer than using brutal force. To me, that's defeats the purpose. If it takes longer for a computer to solve with logic than with guessing, certainly it would take longer for a human.

So, I am curious - how's your program's performance when using human logic, comparing to backtracking/brutal force?
Back to top
View user's profile Send private message
Lunatic

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

Items
PostPosted: Mon Sep 29, 2008 10:21 am    Post subject: Re: How fast is your (non-brutal force) solver? Reply with quote

johnqh wrote:
So, I am curious - how's your program's performance when using human logic, comparing to backtracking/brutal force?


In my program, MPQ Sudoku, brutal force is faster on difficult sudokus. The solving speed of brutal force increases with the number of givens. Therefore a combination of easy human techniques as a pre-solve in combination with brutal force is even faster.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Mon Sep 29, 2008 11:09 am    Post subject: Re: How fast is your (non-brutal force) solver? Reply with quote

johnqh wrote:
... that's defeats the purpose.

What purpose?

Regards,

Mike Metcalf
Back to top
View user's profile Send private message
johnqh

Joined: 27 Sep 2008
Posts: 4
:

Items
PostPosted: Wed Oct 01, 2008 9:36 pm    Post subject: Reply with quote

The purpose.....

Supposely, Sudoku should be solved by logic only. That's the purpose.

If brutal force is faster than logic, that defeats the purpose.

Let's be honest, some of the techniques are no more than brutal force until you find a consistent result. For example, forcing chain/net - you are trying different values in a cell, and see if they all result the same candidate (or elimination of the same candidate) in another cell.
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Thu Oct 02, 2008 7:02 am    Post subject: Reply with quote

johnqh wrote:
The purpose.....

Supposely, Sudoku should be solved by logic only. That's the purpose.

If brutal force is faster than logic, that defeats the purpose.


Supposedly? This begs the question as to whether Sudoku has any purpose. For most people who come into contact with the puzzle, it is simply a recreational pastime. For the young and the old, it might be claimed that it useful to develop/maintain the grey cells, but beyond that it can't be said to have a purpose.

Of course, here we're on the Programmers' Forum, so perhaps we can discuss the purpose in terms of understanding the underlying mathematical structure of sudoku, and of developing algorithms to set and solve puzzles. Almost all published puzzles can be solved by (not very hard) logic, and so a brute-force solver is required only as a back-up. It's useful too, in some circumstances, in developing difficult puzzles, but even there it has been shown that if processing speed is a requirement, a brute-force solver is faster if the puzzles are pre-processed by a simple logic solver. This has been discussed here.

In general, I would maintain that neither sudoku nor any aspect of it has any inherent purpose. Some aspects of it are useful as an exercise for the brain, as a subject of investigation in abstract mathematics, or as training in various aspects of programming. But, in general, it's something that simply keeps us from tilling the fields or pondering Witttgenstein.

Regards,

Mike Metcalf
Back to top
View user's profile Send private message
johnqh

Joined: 27 Sep 2008
Posts: 4
:

Items
PostPosted: Thu Oct 02, 2008 7:38 am    Post subject: Reply with quote

OK, let's talk about programming...

So how fast is your logic solver? Faster than brutal force?
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Thu Oct 02, 2008 8:06 am    Post subject: Reply with quote

johnqh wrote:
OK, let's talk about programming...

So how fast is your logic solver? Faster than brutal force?

As I tried to point out by referring you to the Need to test my solver thread, it depends. I can test my logic solver only on that subset of puzzles that it can solve, and I don't have such a subset readily available. Such puzzles aren't really very interesting as all the action is at the hard end, see, for example, the Patterns Game. That said, it probably takes some milliseconds for an average puzzle within its capabilities.

Regards,

Mike Metcalf
Back to top
View user's profile Send private message
johnqh

Joined: 27 Sep 2008
Posts: 4
:

Items
PostPosted: Thu Oct 02, 2008 5:24 pm    Post subject: Reply with quote

"Within its capacities" is a vague.

Looking for fish is way easier than looking for ALS or chains. Fish is a pattern, ALS/chain is limited brutal force.

So, if your solver supports ALS/color/chains, how fast is it when dealing with puzzles which require those?
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Thu Oct 02, 2008 6:47 pm    Post subject: Reply with quote

I don't really understand where you want to go with this. I don't believe it is possible to get a direct correlation between human style and brute force solving techniques. Consider the following puzzles:
Code:
...87..3.52.......4..........3.9..7......54...8.......2.....5.....3....9...1.....
W-Wing, UR Type 4, XY-Chain
Brute force: 1ms
Logic solver: 88ms

.1.....2....8..6.......3........43....2.1....8......9.4...7.5.3...2...........4..
W-Wing, UR Type 1, Nice Loop
Brute force: 92ms
logic solver: 109ms

The puzzles are more or less equally difficult, but the brute force times are 1:88. Plus you have to keep in mind, that the logic solver is not optimized at all (for example it always calculates all possible steps of one technique but uses only one - puzzle two gives 39 Nice loops for one step), since it is fast enough for my purposes.
Back to top
View user's profile Send private message
Sisophon2001

Joined: 05 Mar 2008
Posts: 32
:
Location: Cambodia

Items
PostPosted: Sun Oct 05, 2008 10:34 am    Post subject: Reply with quote

A mixture of brute force with some logic is the fastest way to solve sudoku. A pure logic solver will be slow, because it must sequentially test so many different conditions. Even with human solving techniques, I have found that methods involving systematic guessing (like 3D colouring combined X-Colouring) are faster and easier than pattern matching (based on the results from one test subject - me!). But I do agree that pattern matching is fun, while systematic guessing is not, once the challange of developing the techniques is over.

Garvan
Back to top
View user's profile Send private message Send e-mail 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