Soduku

[Jonathan Gardner]

Here at my job, Python gets no respect.

A programmer here wanted to see which language among Python, Perl, and
Java was better. So he wrote a Python, perl, and Java version. Except
the Python version was 20x slower than the perl and Java versions.

Well, luckily he asked around in our little Python group about what he
did wrong. He simply misindented a block of code, making it run 10x as
often as it needed to. With that one fix, it was running faster than
the Java and perl versions, about 2x as fast. A few other minor tweaks
made it run even faster.

And we've been playing with different algorithms for soduku solutions.
I had it down to 27 ms to solve the puzzle.

So, one more story on why Python is really good. I think, at least with
2.4, we should start bragging about Python's speed. I mean, it beats
Java AND perl!

[Felipe Almeida Lessa]

Re: Soduku

Em Ter, 2006-02-14 às 17:32 -0800, Jonathan Gardner escreveu:[color=blue]
> So, one more story on why Python is really good. I think, at least with
> 2.4, we should start bragging about Python's speed. I mean, it beats
> Java AND perl![/color]

Maybe the other implementations also have errors? Well, I'm not saying
Python is worse than them, I'm just trying to be fair. Besides, puzzles
can't say if one is better than the other, they're completely out of the
reality of most programs.

Just my two cents,
Felipe.

--
"Quem excele em empregar a força militar subjulga os exércitos dos
outros povos sem travar batalha, toma cidades fortificadas dos outros
povos sem as atacar e destrói os estados dos outros povos sem lutas
prolongadas. Deve lutar sob o Céu com o propósito primordial da
'preservação' . Desse modo suas armas não se embotarão, e os ganhos
poderão ser preservados. Essa é a estratégia para planejar ofensivas."

-- Sun Tzu, em "A arte da guerra"

[Jack Diederich]

Re: Soduku

On Tue, Feb 14, 2006 at 05:32:48PM -0800, Jonathan Gardner wrote:[color=blue]
> Here at my job, Python gets no respect.
>
> A programmer here wanted to see which language among Python, Perl, and
> Java was better. So he wrote a Python, perl, and Java version. Except
> the Python version was 20x slower than the perl and Java versions.
>
> Well, luckily he asked around in our little Python group about what he
> did wrong. He simply misindented a block of code, making it run 10x as
> often as it needed to. With that one fix, it was running faster than
> the Java and perl versions, about 2x as fast. A few other minor tweaks
> made it run even faster.
>
> And we've been playing with different algorithms for soduku solutions.
> I had it down to 27 ms to solve the puzzle.
>[/color]
A nice story to hear, did you measure how long each of the solutions
took you to write (even if it was just a wrote translation of the same
strategy)?

Is my math off or does 27ms mean 0.027 seconds? On my laptop (1.3GHz)
an empty python program takes 10ms to run (0.010 secs). I ask out of
vanity, my own solver takes .15 seconds to run (20 seconds for a 16x16 grid).

-jackdied

[Jonathan Gardner]

Re: Soduku

27ms == 0.027s

How do you have a 16x16 grid for soduku? Are you using 16 digits? 0-F?

The one I am using has 9 digits, 9 squares of 9 cells each, or 9x9
cells.

The least efficient part of the algorithm is that part to calculate
what to put in a hole (as anyone might've guessed.) My algorithm
calculates this by using a set of possible values. Then I visit each
cell in the same row, column, and square, removing values from the set.
What's left is the possible values. If there is only one possible
value, then I've found what belongs there. The soduku puzzle I was
using for a test can be solved without making any guesses in this way.

The guy's algorithm was visiting each empty square and then trying out
numbers from 1-9. If they didn't violate the rules (by examining each
cell in the row, column, and square for each guess), then he would move
to the next empty cell and try again, until he got the solution. There
was a lot of backtracking and it would even try to find all possible
answers.

[Atanas Banov]

Re: Soduku

you dont measure single run, you measure multiple runs using the
"timeit" module (for me 1000 repeats was about right).

here are some results which i recorded when i was implementing Sudoku
solver (on AMD Athlon 1.25GHz, using the sample shown on www.sudoku.com
front page):

brute: 1000 for 83 sec
smart: 1000 for 21 sec
brute, bitset: 1000 for 29 sec
smart, bitset: 1000 for 7.0 sec
smart, bit+que: 1000 for 5.3 sec

so you see the algorithm makes big difference... and so does the data
structure used. i got 15x speed-up that way. i guess i can claim that
my solver runs the sample for 5.3s/1000 = 5.3 ms!

a friend was also implementing sudoku - this time in C - and his
program solves the sample 10000 times for 3.4sec (i.e. for 0.34ms) on
slightly faster machine - so let's say his **highly optimized** C code
is about 10x faster than mine.

- Nas

[Mikael Olofsson]

Re: Soduku

Jonathan Gardner wrote:[color=blue]
> How do you have a 16x16 grid for soduku? Are you using 16 digits? 0-F?
>
> The one I am using has 9 digits, 9 squares of 9 cells each, or 9x9
> cells.[/color]

What alphabet you use is irrelevant. Sudokus has really nothing to do
with numbers. You can use numbers, as well as letters, fruits, or car
models. Numbers just happen to be nice to use as alphabet for fairly
small sudokus. The hobby electronics magazine elektor at

http://www.elektor-electronics.co.uk/

uses 0-F for their 16x16 sudokus.

You can make sudokus of more or less any size. In the kids department at

http://www.dailysudoku.co.uk

you can find 4x4 and 6x6 grids. Apart from those and the standard 9x9, I
have also seen 12x12, 16x16 and 25x25. You could make them 8x8 or 99x99
if you wish. Those numbers should be non-primes, though, since the
pattern of sub-blocks breaks if the numbers are primes.

Perhaps I should mention the three-dimensional one (9x9x9) that someone
showed me at work. That particular one was a bore, since it contained
too much patterns. Or the two orthogonal ones, where you have two 9x9
sudokus in one with interrelations. ..

Finally, dailysudoku also has what they call squiggly sudokus, e.g.

http://www.dailysudoku.co.uk/sudoku/squiggly/archive.shtml?year=2006&month=02&day=15

By the way, if I'm not completely mistaken, there are only two
non-equivalent solutions to the 4x4 grid. The equivalence relations
taken into account are then the following:

Permutations of the alphabet.
Interchanging interchangeable rows or columns.
Transpose - as in matrix transpose - of the whole grid.

Enough off-topic for now
/MiO

[Raymond Hettinger]

Re: Soduku

[Jack Diederich][color=blue]
> Is my math off or does 27ms mean 0.027 seconds? On my laptop (1.3GHz)
> an empty python program takes 10ms to run (0.010 secs). I ask out of
> vanity, my own solver takes .15 seconds to run (20 seconds for a 16x16 grid).[/color]

Comparisons for individual puzzles are likely to be meaningless. Any
algorithm is at some point forced to try out assumptions from many
possiblities. A lucky or unlucky string of guesses would throw-off the
comparisons. Ideally, they should run hundreds of sample puzzles and
include a good many that involve making mulitple levels of assumptions.
Some of the easy puzzles solve readily without a depth-first search
(so a good chuck of the code may go unexercised). Another comparison
issue is the choice of data structures for input, working data, and
output -- the accessing differing structures may cloud the comparison
of difference algorithms.

FWIW, my version is listed on ASPN:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/473893

Raymond

[Jack Diederich]

Re: Soduku

On Wed, Feb 15, 2006 at 06:56:56PM -0800, Raymond Hettinger wrote:[color=blue]
> [Jack Diederich][color=green]
> > Is my math off or does 27ms mean 0.027 seconds? On my laptop (1.3GHz)
> > an empty python program takes 10ms to run (0.010 secs). I ask out of
> > vanity, my own solver takes .15 seconds to run (20 seconds for a 16x16 grid).[/color]
>
> Comparisons for individual puzzles are likely to be meaningless. Any
> algorithm is at some point forced to try out assumptions from many
> possiblities. A lucky or unlucky string of guesses would throw-off the
> comparisons. Ideally, they should run hundreds of sample puzzles and
> include a good many that involve making mulitple levels of assumptions.
> Some of the easy puzzles solve readily without a depth-first search
> (so a good chuck of the code may go unexercised). Another comparison
> issue is the choice of data structures for input, working data, and
> output -- the accessing differing structures may cloud the comparison
> of difference algorithms.[/color]

True, especially for 9x9 grids. I can make my solver go 'faster' by
eliminating the more complicated heuristics. There is extra overhead in
setting them up but the puzzle doesn't have to resort to them. For 16x16
boards the extra bookkeeping reduces the search space dramatically.
[color=blue]
> FWIW, my version is listed on ASPN:
> http://aspn.activestate.com/ASPN/Coo.../Recipe/473893[/color]

Short and concise but .. what, no sets?!
I used sets initially (each cell is a set object of int values) and
was pleasantly surprised how fast it was. Not leaving well enough alone
I wrote a C based set-alike that uses bit vectors to represent small
int sets (each bit is 0,1,2 .. sizeof(unsigned long)*7 - 1).
Despite the fact that or/and/sub are simple bit operations it is
only 1/3rd faster than regular sets. It doesn't cache and reuse objects
like sets; I'd like to think that is why it isn't faster still.

To compare different implementations (regular set vs bitset) of the same
strategy you have to record and playback any random-ish parts like taking
the first value of list(set-thing)[0].

I've been meaning to do a writeup. I'll try harder to find the time.

-Jack