View previous topic :: View next topic |
Author |
Message |
| johnqh
| Joined: 27 Sep 2008 | Posts: 4 | : | | Items |
|
Posted: Mon Sep 29, 2008 4:27 am Post subject: How fast is your (non-brutal force) solver? |
|
|
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 |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Mon Sep 29, 2008 10:21 am Post subject: Re: How fast is your (non-brutal force) solver? |
|
|
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 |
|
|
| m_b_metcalf
| Joined: 13 Mar 2006 | Posts: 210 | : | Location: Berlin | Items |
|
Posted: Mon Sep 29, 2008 11:09 am Post subject: Re: How fast is your (non-brutal force) solver? |
|
|
johnqh wrote: | ... that's defeats the purpose. |
What purpose?
Regards,
Mike Metcalf |
|
Back to top |
|
|
| johnqh
| Joined: 27 Sep 2008 | Posts: 4 | : | | Items |
|
Posted: Wed Oct 01, 2008 9:36 pm Post subject: |
|
|
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 |
|
|
| m_b_metcalf
| Joined: 13 Mar 2006 | Posts: 210 | : | Location: Berlin | Items |
|
Posted: Thu Oct 02, 2008 7:02 am Post subject: |
|
|
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 |
|
|
| johnqh
| Joined: 27 Sep 2008 | Posts: 4 | : | | Items |
|
Posted: Thu Oct 02, 2008 7:38 am Post subject: |
|
|
OK, let's talk about programming...
So how fast is your logic solver? Faster than brutal force? |
|
Back to top |
|
|
| m_b_metcalf
| Joined: 13 Mar 2006 | Posts: 210 | : | Location: Berlin | Items |
|
Posted: Thu Oct 02, 2008 8:06 am Post subject: |
|
|
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 |
|
|
| johnqh
| Joined: 27 Sep 2008 | Posts: 4 | : | | Items |
|
Posted: Thu Oct 02, 2008 5:24 pm Post subject: |
|
|
"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 |
|
|
| hobiwan
| Joined: 11 Feb 2008 | Posts: 83 | : | | Items |
|
Posted: Thu Oct 02, 2008 6:47 pm Post subject: |
|
|
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 |
|
|
| Sisophon2001
| Joined: 05 Mar 2008 | Posts: 32 | : | Location: Cambodia | Items |
|
Posted: Sun Oct 05, 2008 10:34 am Post subject: |
|
|
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 |
|
|
|