Yet another brute force sudoku solver

B

Ben Bacarisse

Nick Keighley said:
why not if you must use the word it's a reasonable usage.
If you mean "global" to ba an alias for "external linkage"
why not use the term?

I have no problem with people using the term, if they take care with
it. My remarks were about Just Plain Richard's suggestion that "file
scope is global". That is just plain wrong.

In addition, care is needed when talking to people who only know
languages where "global" is a scope. If we take the usual "global
variable = object with external linkage" meaning then C has the odd
property (odd as far as such people are concerned) that the name of a
"global variable" might be "in scope" only inside two tiny functions
out of a million lines of code.
 
U

user923005

Hello Dann,




Boon wrote:
I've been toying with a simple sudoku[1] solver. I meant for the code to
be short and easy to understand. I figured "brute force is simple" --
who needs finesse, when you've got muscle, right? :)
[1]http://en.wikipedia.org/wiki/Sudoku
Thus, the strategy is to test every legal "move" and to backtrack when
stuck. A recursive function seemed appropriate. I'd like to hear
comments and suggestions regarding the implementation.
[snip my implementation]
Compare your method with this:
/* Program resolution of sudoku grids by backtracking,
   with propagation of the constraints and variable
   selection the most constrained (mrv: minimum remaining value).
   The file is read from stdin.  Try for example with:
   53..7....
   6..195...
   .98....6.
   8...6...3
   4..8.3..1
   7...2...6
   .6....28.
   ...419..5
   ....8..79
   Bernard Helmstetter, 2006
   Translated to English by Dann Corbit
*/
[snip Bernard's implementation]

Thanks Dann. In my opinion, Bernard's method is more complex than mine,
but it is very likely faster. Were there specific differences you wanted
to highlight ?

It is many orders of magnitude faster. While it is a little more
complex, it is simple enough to understand.
AI problems are very interesting to me. I thought you might enjoy
looking at a highly efficient solution.
 
D

Default User

user923005 said:
It is many orders of magnitude faster. While it is a little more
complex, it is simple enough to understand.
AI problems are very interesting to me. I thought you might enjoy
looking at a highly efficient solution.

I've been working on a solver that uses no brute force (that is, no
test and backtrack) methods. I have it now as smart as I am in solving
them. I have to increase my own understanding of things like "X-wing"
and other more advanced methods so I can create the algorithms.




Brian
 
G

Giorgos Keramidas

Richard said:
Richard wrote:
Trent Josephsen wrote:
Boon wrote:
#include <stdio.h>

static int grid[9][9]; ...
And file scope IS global (as anyone without a rod up their arse knows

it) since anyone can declare an extern and then see it. ...
suggesting, such declarations have internal linkage, not external
linkage. As a result, declaring the same identifier with external
linkage in a different translation unit will not make this
definition visible in that translation unit. You need to understand
the distinction between scope and linkage.

I dont know where you got that impression of my meaning. I suppose its
that word "declare" again. I should have posted an example.

Perhaps you should. I don't know how to make a file scope identifier
with internal linkage (such as the array 'grid' defined above) visible
from another translation unit by "declar[ing] an extern", unless the
identifier with external linkage refers to something different from
what the identifier with internal linkage refers to. If you know how
to do this, could you give us an example?

You can define an object with internal linkage in one file, and a
function with external linkage that returns a pointer to that object.
Then other translation units can call the function to obtain the runtime
location of the object and use the pointer to access it.
 
G

Giorgos Keramidas

Giorgos Keramidas said:
Perhaps you should. I don't know how to make a file scope identifier
with internal linkage (such as the array 'grid' defined above) visible
from another translation unit by "declar[ing] an extern", unless the
identifier with external linkage refers to something different from
what the identifier with internal linkage refers to. If you know how
to do this, could you give us an example?

You can define an object with internal linkage in one file, and a
function with external linkage that returns a pointer to that object.
Then other translation units can call the function to obtain the
runtime location of the object and use the pointer to access it.

Yes, and that would provide access to the object in question, but not
using the *identifier* in question.

Of course. I should have read more carefully what James wrote, thanks :)
 
B

Boon

user923005 said:
It is many orders of magnitude faster.

Many orders of magnitude ?
So, at least 100 times faster, perhaps even 1000 times faster ?
Can you see that just by looking at the source code (static analysis) or
did you run both programs ?
Efficiency was not my main concern, but I will try to optimize my
implementation ;-)

I've only input 7 grids so far, below is the "hardest" I've seen.

.....968..
...1....7.
..2......3
..3...8..6
...4.2.3..
6..5...8.
9......5.
..7....1..
...594....
While it is a little more complex, it is simple enough to understand.

I will print it out, and study it. Thanks again for sharing.
AI problems are very interesting to me. I thought you might enjoy
looking at a highly efficient solution.

How does one properly benchmark a program that runs in less than 50 ms ?

Regards.
 
J

James Kuyper

Boon wrote:
....
How does one properly benchmark a program that runs in less than 50 ms ?

By making many repeated calls to the function, and dividing the total
amount of time spent by the number of calls. Whenever you do this, you
have to be careful to avoid possible optimization, which might cause the
function to be called only once to produce a result that it returns many
times. For a function as complicated as yours, that's less likely to be
a problem.

For really fast algorithms, to get accurate results you should,
properly, subtract the time spent performing any empty loop the same
number of times, before doing the division. Unfortunately, that's not
easy to do, because it is extremely likely that your compiler will
optimize away an empty loop.
 
U

user923005

Many orders of magnitude ?
So, at least 100 times faster, perhaps even 1000 times faster ?
Can you see that just by looking at the source code (static analysis) or
did you run both programs ?
Efficiency was not my main concern, but I will try to optimize my
implementation ;-)

I've only input 7 grids so far, below is the "hardest" I've seen.

....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....


I will print it out, and study it. Thanks again for sharing.


How does one properly benchmark a program that runs in less than 50 ms ?

Count the nodes.

For instance, with this one:
...1.8.6.4
..376.....
5........
......5...
...6.1.8..
....4.....
.........3
......752.
8.2.9.7..

Your program takes 789,878 nodes and the fast program takes 11,187
nodes. That's 70x faster, so a less than a factor of 100.

I have an interest in AI, and so these sorts of things are interesting
to me.
 
U

user923005

Count the nodes.

For instance, with this one:
..1.8.6.4
.376.....
5........
.....5...
..6.1.8..
...4.....
........3
.....752.
8.2.9.7..

Your program takes 789,878 nodes and the fast program takes 11,187
nodes.  That's 70x faster, so a less than a factor of 100.

I have an interest in AI, and so these sorts of things are interesting
to me.


C:\tmp\sudoku>fast < sudoku7.txt
.....968..
...1....7.
..2......3
..3...8..6
...4.2.3..
6..5...8.
9......5.
..7....1..
...594....

453796821
861234975
729185463
132478596
584629317
697513284
948361752
376852149
215947638

2081 nodes searched

C:\tmp\sudoku>slow < sudoku7.txt
.....968..
...1....7.
..2......3
..3...8..6
...4.2.3..
6..5...8.
9......5.
..7....1..
...594....

453796821
861234975
729185463
132478596
584629317
697513284
948361752
376852149
215947638

80992 noeuds cherches

The ratio for your quoted problem (which is much easier than the one
that I quoted) is 39:1 slower

I guess that if we find a really hard one, the ratio will be even more
profound.
 
M

Moi

C:\tmp\sudoku>fast < sudoku7.txt
....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

453796821
861234975
729185463
132478596
584629317
697513284
948361752
376852149
215947638

2081 nodes searched

Haha, mine does 2082::

. . . . 9 6 8 . .
. . 1 . . . . 7 .
. 2 . . . . . . 3
. 3 . . . 8 . . 6
. . 4 . 2 . 3 . .
6 . . 5 . . . 8 .
9 . . . . . . 5 .
. 7 . . . . 1 . .
. . 5 9 4 . . . .

4 5 3 7 9 6 8 2 1
8 6 1 2 3 4 9 7 5
7 2 9 1 8 5 4 6 3
1 3 2 4 7 8 5 9 6
5 8 4 6 2 9 3 1 7
6 9 7 5 1 3 2 8 4
9 4 8 3 6 1 7 5 2
3 7 6 8 5 2 1 4 9
2 1 5 9 4 7 6 3 8

Aantal=1 (calls=2082)


Method := recursive descent with bitmasks (narrowest first)
Maybe I counted the final+1 recursive call and you did not ?

Cheers,
AvK
 
U

user923005

Haha, mine does 2082::

 . . . . 9 6 8 . .
 . . 1 . . . . 7 .
 . 2 . . . . . . 3
 . 3 . . . 8 . . 6
 . . 4 . 2 . 3 . .
 6 . . 5 . . . 8 .
 9 . . . . . . 5 .
 . 7 . . . . 1 . .
 . . 5 9 4 . . . .

 4 5 3 7 9 6 8 2 1
 8 6 1 2 3 4 9 7 5
 7 2 9 1 8 5 4 6 3
 1 3 2 4 7 8 5 9 6
 5 8 4 6 2 9 3 1 7
 6 9 7 5 1 3 2 8 4
 9 4 8 3 6 1 7 5 2
 3 7 6 8 5 2 1 4 9
 2 1 5 9 4 7 6 3 8

Aantal=1 (calls=2082)

Method := recursive descent with bitmasks (narrowest first)
Maybe I counted the final+1 recursive call and you did not ?

How does it do with this one:

1........
..2.......
...3......
....4.....
..........
......4...
.......3..
........1.
.........1
 
P

Peter Nilsson

Boon said:
I've only input 7 grids so far, below is the "hardest"
I've seen.

....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

Try one designed to tax naive brute force solvers...
<http://en.wikipedia.org/wiki/
Image:Sudoku_puzzle_hard_for_brute_force.jpg>

How does one properly benchmark a program that runs
in less than 50 ms ?

Check how well it scales to larger grids, e.g. 16x16,
or 25x25. The thing about exponential algorithms is
that it's usually not very hard to find a larger puzzle
that brings it to a stand still.
 
M

Moi

How does it do with this one:

1........
.2.......
..3......
...4.....
.........
.....4...
......3..
.......1.
........1

Well, it fails (caused by the two '4's in the center box, off course)
I needed to set the time-out to 60 seconds before finding out myself :)

AvK
 
U

user923005

Try one designed to tax naive brute force solvers...
  <http://en.wikipedia.org/wiki/
Image:Sudoku_puzzle_hard_for_brute_force.jpg>

<snip>

C:\tmp\sudoku>fast < sudoku9.txt
..........
......3.85
...1.2....
....5.7...
...4...1..
..9.......
5......73
...2.1....
.....4...9

987654321
246173985
351928746
128537694
634892157
795461832
519286473
472319568
863745219

73482 nodes searched
fast time = 0.11793593878551603

C:\tmp\sudoku>slow < sudoku9.txt
..........
......3.85
...1.2....
....5.7...
...4...1..
..9.......
5......73
...2.1....
.....4...9

987654321
246173985
351928746
128537694
634892157
795461832
519286473
472319568
863745219

69207226 noeuds cherches
slow time = 21.393947415104435

181 times faster wall time, 941 times faster in terms of nodes.

Check how well it scales to larger grids, e.g. 16x16,
or 25x25. The thing about exponential algorithms is
that it's usually not very hard to find a larger puzzle
that brings it to a stand still.

I found a very nice open source solver called yasss-0.4.8 that also
quickly diagnoses errant problems like the one I posed earlier:

1........
..2.......
...3......
....4.....
..........
......4...
.......3..
........1.
.........1

Yasss does require all the rows on a single line, but I may make a
version that allows either format, since it comes with source.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top