subject:"Sudoku solver"


On 29/03/2015 13:01, BartC wrote:

On 29/03/2015 11:35, Steven D'Aprano wrote:



Anyway, we don't really know where the confusion lies. Perhaps the
description is misleading, or I'm just confused, or Bart's idea of brute
force is not the same as my idea of brute force, or perhaps he really
is a
super-genius who has casually relegated C to the dust bin of historic
languages...


My solver definitely works, as the solutions produced by the two
algorithms are identical.

I'm not clever enough to produce a properly analytical solver, but
perhaps it is not quite as brute force as the Python one.

I've looked at my code and I don't really understand it (it's from a
long time ago), and it would take quite a while to convert it to Python
and post it. (Most of it seems to be preoccupied with multiple ways of
indexing the board or grid.)

(If it's of any interest, this non-Python code is here:

http://pastebin.com/5cXd2Pef )


I've managed to create a Python version of my 'brute force' sudoku solver:

http://pastebin.com/CKmHmBKm

It was hard going as I don't normally write Python. But it worked 
practically first time, after building it bottom-up and then putting the 
solvepuzzle() routine in place.


The data for the 'hard' puzzle is hard-coded into it, so you just run it.

Python 3.1 (normal CPython) took 13 or 14 seconds to solve (previously 
1700 seconds with the OP's code).


PyPy took 1.3 seconds (previously 93 seconds). (Annoyingly, faster than 
the 1.7 seconds of my language...)


(The original code in my language that I posted has been simplified - 
which also made it faster, and the Python code was based on that 
version. The Pastebin code has been updated.)


I won't bother to test a C version of this, as it's a bit more awkward 
to translate (making use of strings and deep copies of arrays).


--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 29/03/2015 11:35, Steven D'Aprano wrote:


That's why I can't help but feel that, *given the description we've seen*,
perhaps Bart's brute force code doesn't actually solve the problem, and
that's why it is so fast. I'm reminded of the recent thread where somebody
claimed to have a significant speed-up over Timsort by using a binary
search instead of linear search. Tim Peters investigated, and noticed that
the code wasn't actually sorting. It's easy to beat the performance of any
sort algorithm if you don't actually sort...

Anyway, we don't really know where the confusion lies. Perhaps the
description is misleading, or I'm just confused, or Bart's idea of brute
force is not the same as my idea of brute force, or perhaps he really is a
super-genius who has casually relegated C to the dust bin of historic
languages...


My solver definitely works, as the solutions produced by the two 
algorithms are identical.


I'm not clever enough to produce a properly analytical solver, but 
perhaps it is not quite as brute force as the Python one.


I've looked at my code and I don't really understand it (it's from a 
long time ago), and it would take quite a while to convert it to Python 
and post it. (Most of it seems to be preoccupied with multiple ways of 
indexing the board or grid.)


(If it's of any interest, this non-Python code is here:

http://pastebin.com/5cXd2Pef )

--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-29 Thread Marko Rauhamaa

Mark Lawrence breamore...@yahoo.co.uk:

 One thing I have come to rely on over the years is never, ever trust
 your gut instincts about Python performance, you're almost inevitably
 wrong. When I first came across the Norvig solver I made a change,
 purely for fun, to replace two calls to len() with a single call and
 save the result. The run time to solve each puzzle dropped by around
 5%. I believe this meets your conceptually insignificant.

Yes. It's kinda sad when you have to resort to such low-brow
optimizations. Mostly you don't have to, though. You mainly want to keep
the expression elegant.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-29 Thread Marko Rauhamaa

BartC b...@freeuk.com:

 As Chris mentioned, when I say 'faster than C', I mean X running my
 algorithm was faster then C running Marko's algoritim (on Ian's data).
 This was just an illustration of algorithm being more important than
 language.

Be careful with the benchmark comparisons. Ian's example can be solved
with the identical algorithm in eight different ways (four corners, left
or right). I ran the example with my recent Python solver and got these
times in the eight cases:

884   s
  2.5 s
 13   s
499   s
  5.9 s
128   s
   1360   s
 36   s

(That suggests a slight modification to the original strategy: solve it
in each of the eight ways in parallel and the worst case should be
significantly alleviated.)

I'm actually fascinated by the Python modifications that were
conceptually insignificant but dramatically speeded up the execution
(7880 seconds to 884 seconds). That's something I'll have to keep in
mind in the future.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-29 Thread Mark Lawrence


On 29/03/2015 19:03, Marko Rauhamaa wrote:

BartC b...@freeuk.com:


As Chris mentioned, when I say 'faster than C', I mean X running my
algorithm was faster then C running Marko's algoritim (on Ian's data).
This was just an illustration of algorithm being more important than
language.


Be careful with the benchmark comparisons. Ian's example can be solved
with the identical algorithm in eight different ways (four corners, left
or right). I ran the example with my recent Python solver and got these
times in the eight cases:

 884   s
   2.5 s
  13   s
 499   s
   5.9 s
 128   s
1360   s
  36   s

(That suggests a slight modification to the original strategy: solve it
in each of the eight ways in parallel and the worst case should be
significantly alleviated.)

I'm actually fascinated by the Python modifications that were
conceptually insignificant but dramatically speeded up the execution
(7880 seconds to 884 seconds). That's something I'll have to keep in
mind in the future.


Marko



One thing I have come to rely on over the years is never, ever trust 
your gut instincts about Python performance, you're almost inevitably 
wrong.  When I first came across the Norvig solver I made a change, 
purely for fun, to replace two calls to len() with a single call and 
save the result.  The run time to solve each puzzle dropped by around 
5%.  I believe this meets your conceptually insignificant.


--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-29 Thread Christian Gollwitzer


Am 29.03.15 um 05:06 schrieb Steven D'Aprano:

I'm not one of those people who think that C is by definition the fastest
language conceivable. (People who believe this sometimes make an exception
for hand-crafted assembly, which is ironic since these days the best C
optimizing compilers can generate faster, tighter code than human assembly
programmers.) I know that program speed depends on the implementation of
the language, not necessarily the language itself. I know that Fortran can
beat C for numeric work, and that with a tiny fraction of the work put into
optimization that C has seen, modern languages like Scala, Eiffel, Haskell
and D can get to a factor of 2-6 times as slow as C. And I know that PyPy
has managed to beat C in some (quite restrictive, but not completely
unrealistic) benchmarks:

http://morepypy.blogspot.com.au/2011/02/pypy-faster-than-c-on-carefully-crafted.html
http://morepypy.blogspot.com.au/2011/08/pypy-is-faster-than-c-again-string.html


So beating C is not impossible.


Beating C is not impossible, but it is really hard. The compilation is 
usually excluded from such benchmarks. Then any langugage could in 
principle compile to the same instructions as the equivalent C program, 
and hence achieve the same speed. The reason that C is such a tough 
competitor is


1) the tools have been optimized over 40 years - just compare the 
sourcecode of gcc with a minimalistic compiler such as tcc, and then 
compare the execution speed of the programs compiled by it


2) the langugage is very easy to compile, since the programmer is forced 
to annotate the sourcecode with data types that usually map 1:1 into 
registers


If you can do type deduction for your variables that lead to the same 
result as the C program, then you can also compile to the same efficient 
code. In most cases the hand-crafted C program is more restricted, 
because the programmer does not make a promise to the compiler that 
things will never overflow (e.g., int is restricted to 32 bits instead 
of arbitrary integers).


Defeating a C compiler is possible in (rare) cases, I wouldn't really 
count the examples you've posted, since they don't actually compute 
anything useful. However, for instance the Intel C compiler is able to 
replace a loop like this:


for (int i=0; iN; i++) {
for (int j=0; jN; j++) {
for (int k=0; kN; k++) {
z[i][k]+=x[i][j]*y[j][k];
}
}
}

with a call to an optimized BLAS matrix multiplication in some 
(=impractical) cases. This can easily speed up the code by a factor of 
100. It would be much easier for a compiled numpy-language to do this 
for z=x*y and also correctly treat slices etc. Still practical compilers 
that do that and achieve *on average* faster programs than hand-crafted 
C do not exist.


Just look at the contrived PyPy benchmarks, for a very tuned selected 
sample you can be almost twice as fast as C - for a random algorithm 
like the Sudoku solver, not specifically tuned, C is 30x faster. It 
still boils down to the classic rules: static unboxed types and static 
or preallocated memory makes your code fast. In many cases, though, 
programming in Python can free programmer time, which can lead in turn 
to better algorithms that outperform the wisdom of the C compiler.




But, when you tell me that your very own personal interpreted language,
which I assume nobody else has worked on, is 40% faster than optimized C,
my first reaction is to expect that you've probably made a mistake


I agree with Chris that this was a misunderstanding.


Christian
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-29 Thread Chris Angelico

On Sun, Mar 29, 2015 at 9:35 PM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
 Anyway, we don't really know where the confusion lies. Perhaps the
 description is misleading, or I'm just confused, or Bart's idea of brute
 force is not the same as my idea of brute force, or perhaps he really is a
 super-genius who has casually relegated C to the dust bin of historic
 languages...

Ah, I see what you mean.

I tend to describe an algorithm as brute force even if it has a few
simplifications and early cut-offs. A brute-force primality test, for
instance, might divide the target number by every counting number
since 1, looking for a remainder; does it cease to be brute-force if
you check only 2 and odd numbers? only those up to its square root?
Either of those tiny optimizations will give a dramatic speed
improvement, without representing a flaw; and I would still consider
them brute force. The purest form is a barbarian trying to lift a
gate; the slightly-optimized is a wizard trying to lift the same gate;
but neither algorithm is using a Knock spell to open it by magic. And
if you've seen The Gamers, you'll know that brute force is as fickle
as a roll of the dice.

Point is, brute force isn't a pure absolute from which there can be
no variation.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 29/03/2015 04:06, Steven D'Aprano wrote:

On Sun, 29 Mar 2015 10:50 am, BartC wrote:



But using X *and* my own brute-force algorithm, the same puzzle took 2
seconds to solve - faster than C!



But, when you tell me that your very own personal interpreted language,
which I assume nobody else has worked on, is 40% faster than optimized C,
my first reaction is to expect that you've probably made a mistake
somewhere. I would have the same reaction if somebody casually dropped into
a conversation that they happened to beat Usain Bolt's 100m personal best
of 9.58 seconds by almost four seconds. While carrying a 20kg backpack.


As Chris mentioned, when I say 'faster than C', I mean X running my 
algorithm was faster then C running Marko's algoritim (on Ian's data). 
This was just an illustration of algorithm being more important than 
language.


(As it happens, C using gcc was particularly good at this benchmark. 
Looking only at optimised code, Clang took 4.5 seconds, while a trio of 
lesser C compilers took from 14 to 22 seconds.


This is why I also showed the unoptimised figure, which indicates what 
raw native code could do, without taking account of the 
super-optimisations that gcc is capable of applying.


Because after all such optimisations could also be applied to the Python 
code, such as unrolling those nested loops in good().


And theoretically, a clever enough C compiler could have solved it in 0 
seconds since I'd hard-coded the board values within the source!


See: http://pastebin.com/RZE67TLy )

--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 29/03/2015 00:12, Chris Angelico wrote:

On Sun, Mar 29, 2015 at 10:50 AM, BartC b...@freeuk.com wrote:

Using the OP's algorithm, and testing with the 'hard' puzzle posted by Ian
Kelly, I got these approximate results:

Python 3.1: 1700 seconds (normal Python interpreter)
PyPy:   93 seconds
C unoptimised:  17 seconds   (gcc -O0 32-bit)
C optimised:3.3 seconds  (gcc -O3 32-bit)
(X: 170 seconds)


Nice stats. Any chance you can add CPython 3.4 or 3.5 to that? That's
a pretty old CPython you're using.


I've tried 3.4.3 and it's nearer 1900 seconds!

Which wasn't too surprising as you don't expect new releases to be 
faster, they tend to be slower.


--
Bartc

--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 29/03/2015 19:03, Marko Rauhamaa wrote:

BartC b...@freeuk.com:


As Chris mentioned, when I say 'faster than C', I mean X running my
algorithm was faster then C running Marko's algoritim (on Ian's data).
This was just an illustration of algorithm being more important than
language.


Be careful with the benchmark comparisons. Ian's example can be solved
with the identical algorithm in eight different ways (four corners, left
or right). I ran the example with my recent Python solver and got these
times in the eight cases:

 884   s
   2.5 s
  13   s
 499   s
   5.9 s
 128   s
1360   s
  36   s

(That suggests a slight modification to the original strategy: solve it
in each of the eight ways in parallel and the worst case should be
significantly alleviated.)


Well, in this case all the benchmarks ran the same algorithm on the same 
data, which makes them a better test of the implementations than of the 
algorithm.


I've mentioned a (possibly) significantly faster algorithm which I 
believe to be still brute-force (now in Python here: 
http://pastebin.com/CKmHmBKm).


But I realise it could just be luck in approaching the solution from a 
literally different angle and encountering the answer sooner. (I think 
both stop as soon as they find any valid solution.)


What I've done is try it on 3 rotations as well as the original (+90, 
+180, +270 degrees, but haven't bothered with flips and reflections).


While the original took 13 seconds (using my algorithm in Python), the 
rotations took 18, 49 and 87 seconds respectively.


Since the original time in PyPy took 90-odd seconds, I was about to 
acknowledge that mine might not be that much faster after all. Then I 
realised I was using Python 3.1 not PyPy! Python 3.1 took 28 minutes on 
original hard puzzle using your code, and 13-87 seconds with mine.


So I think this other algorithm is still much faster. I've no idea why, 
especially since it messes about concatenating strings and converting 
them to and from integers.


--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-29 Thread Mark Lawrence


On 29/03/2015 21:59, BartC wrote:

On 29/03/2015 00:12, Chris Angelico wrote:

On Sun, Mar 29, 2015 at 10:50 AM, BartC b...@freeuk.com wrote:

Using the OP's algorithm, and testing with the 'hard' puzzle posted
by Ian
Kelly, I got these approximate results:

Python 3.1: 1700 seconds (normal Python interpreter)
PyPy:   93 seconds
C unoptimised:  17 seconds   (gcc -O0 32-bit)
C optimised:3.3 seconds  (gcc -O3 32-bit)
(X: 170 seconds)


Nice stats. Any chance you can add CPython 3.4 or 3.5 to that? That's
a pretty old CPython you're using.


I've tried 3.4.3 and it's nearer 1900 seconds!

Which wasn't too surprising as you don't expect new releases to be
faster, they tend to be slower.



I simply do not believe those figures, that's roughly 12% slower.  If 
that happened in the real world you'd be able to hear the screams of 
anguish around the world.


--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-29 Thread Mark Lawrence


On 28/03/2015 23:50, BartC wrote:

On 28/03/2015 03:39, Sayth wrote:

Good test for pypy to see where it's speed sits between C and Python.


I've spent the last hour or so doing such tests.

Using the OP's algorithm, and testing with the 'hard' puzzle posted by
Ian Kelly, I got these approximate results:

Python 3.1: 1700 seconds (normal Python interpreter)
PyPy:   93 seconds
C unoptimised:  17 seconds   (gcc -O0 32-bit)
C optimised:3.3 seconds  (gcc -O3 32-bit)
(X: 170 seconds)

All running on Windows on x64.

(X is my own interpreted language, which is where my interest in this
is. This had been generally faster than Python until PyPy came along. It
does however use a pure byte-code interpreter, so the result is not too
bad.

But using X *and* my own brute-force algorithm, the same puzzle took 2
seconds to solve - faster than C!

However it doesn't matter that the OP's algorithm is not great, as it
makes an interesting new benchmark.)



https://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/

--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 29/03/2015 22:19, Mark Lawrence wrote:

On 29/03/2015 21:59, BartC wrote:

On 29/03/2015 00:12, Chris Angelico wrote:

On Sun, Mar 29, 2015 at 10:50 AM, BartC b...@freeuk.com wrote:

Using the OP's algorithm, and testing with the 'hard' puzzle posted
by Ian
Kelly, I got these approximate results:

Python 3.1: 1700 seconds (normal Python interpreter)
PyPy:   93 seconds
C unoptimised:  17 seconds   (gcc -O0 32-bit)
C optimised:3.3 seconds  (gcc -O3 32-bit)
(X: 170 seconds)


Nice stats. Any chance you can add CPython 3.4 or 3.5 to that? That's
a pretty old CPython you're using.


I've tried 3.4.3 and it's nearer 1900 seconds!

Which wasn't too surprising as you don't expect new releases to be
faster, they tend to be slower.



I simply do not believe those figures, that's roughly 12% slower.  If
that happened in the real world you'd be able to hear the screams of
anguish around the world.


You're right, it's wasn't 12% slower. It was 16%!

I didn't have time to run this very long benchmark so ran a different 
algorithm using 3.1, averaging 14.1 seconds for 3 runs. And ran the same 
code with 3.4.3, average 16.4 seconds.


Maybe most people don't run intensively computational benchmarks like these.

--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On 29/03/2015 22:21, Mark Lawrence wrote:

On 28/03/2015 23:50, BartC wrote:

On 28/03/2015 03:39, Sayth wrote:

Good test for pypy to see where it's speed sits between C and Python.

Python 3.1: 1700 seconds (normal Python interpreter)
PyPy: 93 seconds
C unoptimised: 17 seconds (gcc -O0 32-bit)
C optimised:3.3 seconds (gcc -O3 32-bit)

https://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/

The fastest Sudoku solver can solve even the hardest Sudoku in about 1
millisecond and solve most others in 0.1 millisecond.

Blimey, we might as well pack up and go home then!

Actually I didn't realise people took these things so seriously. I came
into the thread when I thought it was being suggested that brute-force
approaches to this problem were not viable.

I think to be useful, it needs to work in a reasonable amount of time,
and a few seconds would be more than reasonable; it doesn't need to be
100 microseconds. Unless somehow somebody's got millions of the things
to get through.

But I guess people aren't interested in actually solving the daily
sudoku in the paper** (that would be very dull); maybe there is more
sport in finding a faster machine solution than anyone else.

(I'm more interested now in getting my own dynamic language to compete
with PyPy, and in getting own static language to compete with C/gcc, as
the timing for this benchmark was pretty bad.)

(** Although I did come across a prize 16x16 sudoku in the paper a few
years back. I adapted my code to 16x16 in 10 minutes or so, which took a
further couple of minutes to solve the given puzzle, and sent it in. But
I didn't win...)

--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-29 Thread mr . smittye

On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:
 A lot of discussion was generated by the good, old fibonacci sequence. I
 have yet to find practical use for fibonacci numbers. However, the
 technique behind a sudoku solver come up every now and again in
 practical situations.
 
 I post below a sudoku solver. I eagerly await neater implementations (as
 well as bug reports).
 
 Usage:
 
 ./sudoku.py sudoku.dat
 
 
 sudoku.dat:
 
 7 . . . . . 6 . .
 . 2 . 8 . 6 . 7 .
 . . . 4 3 . . 9 .
 5 1 . . . . 4 . 3
 . . 9 . . . . 1 .
 . . . . 4 2 . . 5
 . . . 9 . . . . 8
 . . 6 . . . . 5 .
 . . . . . . . 6 .
 
 
 output:
 
 7 8 4 2 9 5 6 3 1
 9 2 3 8 1 6 5 7 4
 6 5 1 4 3 7 8 9 2
 5 1 8 6 7 9 4 2 3
 2 4 9 3 5 8 7 1 6
 3 6 7 1 4 2 9 8 5
 1 7 5 9 6 3 2 4 8
 8 3 6 7 2 4 1 5 9
 4 9 2 5 8 1 3 6 7
 
 
 
 sudoku.py:
 
 #!/usr/bin/env python3
 
 import sys
 
 M = 3
 N = M * M
 Q = N * N
 
 candidates = list(range(1, N + 1))
 
 def main():
 board = []
 for n in sys.stdin.read().split():
 try:
 board.append(int(n))
 except ValueError:
 board.append(None)
 solve(board)
 
 def solve(board, slot=0):
 if slot == Q:
 report(board)
 elif board[slot] is None:
 for candidate in candidates:
 if good(board, slot, candidate):
 board[slot] = candidate
 solve(board, slot + 1)
 board[slot] = None
 else:
 solve(board, slot + 1)
 
 def good(board, slot, candidate):
 (shelf, row), (stack, col) = (divmod(x, M) for x in divmod(slot, N))
 for i in range(M):
 for j in range(M):
 if candidate in (board[(i * M + j) * N + stack * M + col],
  board[(shelf * M + row) * N + i * M + j],
  board[(shelf * M + i) * N + stack * M + j]):
 return False
 return True
 
 def report(board):
 print(\n.join(
  .join(str(board[row * N + col])
  for col in range(N))
 for row in range(N)))
 print()
 
 if __name__ == '__main__':
 main()
 
 
 
 Marko

You say neater implementation
I'll send you to the code-golf site: 
http://codegolf.stackexchange.com/a/446/38632 this is brute force. There are 
some really good implementations in other languages that arent brute force. 
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-28 Thread Chris Angelico

On Sun, Mar 29, 2015 at 10:50 AM, BartC b...@freeuk.com wrote:
 Using the OP's algorithm, and testing with the 'hard' puzzle posted by Ian
 Kelly, I got these approximate results:

 Python 3.1: 1700 seconds (normal Python interpreter)
 PyPy:   93 seconds
 C unoptimised:  17 seconds   (gcc -O0 32-bit)
 C optimised:3.3 seconds  (gcc -O3 32-bit)
 (X: 170 seconds)

Nice stats. Any chance you can add CPython 3.4 or 3.5 to that? That's
a pretty old CPython you're using.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-28 Thread Virgil Stokes


On 27-Mar-2015 15:09, Dave Angel wrote:

On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:

Frank Millman fr...@chagford.com:


So what I am talking about is called a satisfactory puzzle, which is
a subset of a proper puzzle.


That is impossible to define, though, because some people are mental
acrobats and can do a lot of deep analysis in their heads. What's
satisfactory to you may not be satisfactory to me.

Besides, looking for satisfactory patterns can involve a truckload of
trial and error.



I know, let's use regular expressions  g


If you are interested, I have written a python (wxPython GUI) for solving Sudoku 
problems. It even has a hint mode that can be used to lead you to a solution. 
I have tested it on the world's hardest Sudoku (published by a Finish 
mathematician)  and it solves it very fast. I have also written another version 
that finds ALL the solutions to any Sudoku problem (that has a solution) using 
an LP approach --- this is non-trivial. However, I have not been able to give a 
strict mathematical proof that it does indeed find all solutions.


If you wish to really understand the mathematics behind Sudoku then I suggest 
the book Taking Sudoku Seriously by Jason Rosenhouse and Laura Taalman (Oxford 
University Press, 2011). Unfortunately, they do not consider the LP approach in 
this book (an oversight IMHO).


--V. Stokes

--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-28 Thread BartC


On 28/03/2015 03:39, Sayth wrote:

Good test for pypy to see where it's speed sits between C and Python.


I've spent the last hour or so doing such tests.

Using the OP's algorithm, and testing with the 'hard' puzzle posted by 
Ian Kelly, I got these approximate results:


Python 3.1: 1700 seconds (normal Python interpreter)
PyPy:   93 seconds
C unoptimised:  17 seconds   (gcc -O0 32-bit)
C optimised:3.3 seconds  (gcc -O3 32-bit)
(X: 170 seconds)

All running on Windows on x64.

(X is my own interpreted language, which is where my interest in this 
is. This had been generally faster than Python until PyPy came along. It 
does however use a pure byte-code interpreter, so the result is not too bad.


But using X *and* my own brute-force algorithm, the same puzzle took 2 
seconds to solve - faster than C!


However it doesn't matter that the OP's algorithm is not great, as it 
makes an interesting new benchmark.)


--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-28 Thread Steven D'Aprano

On Sun, 29 Mar 2015 10:50 am, BartC wrote:


 (X is my own interpreted language, which is where my interest in this
 is. This had been generally faster than Python until PyPy came along. It
 does however use a pure byte-code interpreter, so the result is not too
 bad.
 
 But using X *and* my own brute-force algorithm, the same puzzle took 2
 seconds to solve - faster than C!


I'm not one of those people who think that C is by definition the fastest
language conceivable. (People who believe this sometimes make an exception
for hand-crafted assembly, which is ironic since these days the best C
optimizing compilers can generate faster, tighter code than human assembly
programmers.) I know that program speed depends on the implementation of
the language, not necessarily the language itself. I know that Fortran can
beat C for numeric work, and that with a tiny fraction of the work put into
optimization that C has seen, modern languages like Scala, Eiffel, Haskell
and D can get to a factor of 2-6 times as slow as C. And I know that PyPy
has managed to beat C in some (quite restrictive, but not completely
unrealistic) benchmarks:

http://morepypy.blogspot.com.au/2011/02/pypy-faster-than-c-on-carefully-crafted.html
http://morepypy.blogspot.com.au/2011/08/pypy-is-faster-than-c-again-string.html


So beating C is not impossible.

But, when you tell me that your very own personal interpreted language,
which I assume nobody else has worked on, is 40% faster than optimized C,
my first reaction is to expect that you've probably made a mistake
somewhere. I would have the same reaction if somebody casually dropped into
a conversation that they happened to beat Usain Bolt's 100m personal best
of 9.58 seconds by almost four seconds. While carrying a 20kg backpack.



-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-28 Thread Chris Angelico

On Sun, Mar 29, 2015 at 2:06 PM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
 On Sun, 29 Mar 2015 10:50 am, BartC wrote:

 (X is my own interpreted language, which is where my interest in this
 is. This had been generally faster than Python until PyPy came along. It
 does however use a pure byte-code interpreter, so the result is not too
 bad.

 But using X *and* my own brute-force algorithm, the same puzzle took 2
 seconds to solve - faster than C!

 But, when you tell me that your very own personal interpreted language,
 which I assume nobody else has worked on, is 40% faster than optimized C,
 my first reaction is to expect that you've probably made a mistake
 somewhere. I would have the same reaction if somebody casually dropped into
 a conversation that they happened to beat Usain Bolt's 100m personal best
 of 9.58 seconds by almost four seconds. While carrying a 20kg backpack.

I think you're misreading the stats. The first table compares
languages, all using the same algorithm, and in that, C beat X ten to
one, unoptimized. The second figure, when X took only 2 seconds, was
demonstrating the massive improvement that the algorithmic change
(from the OP's algorithm to [BartC's] own brute-force algorithm)
achieved. For comparison, that's like casually dropping into
conversation that you happened to drive a car faster than Usain Bolt's
personal best. :)

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-28 Thread Ian Kelly

On Fri, Mar 27, 2015 at 7:40 PM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
 Excluding that, the consensus seems to be that Perl's regexes are stronger
 than Chomsky regular expressions, but nobody quite knows how much stronger.
 It's likely that they are at least as powerful as context-free grammars,
 but not as powerful as a Turing machine (excluding embedded Perl code), but
 that covers a lot of ground in the hierarchy of language power:

Intuitively, I should think that the combination of recursive
subpatterns and assertions would make them able to generate at least
the context-sensitive languages.

 So it's an open question as to whether or not you could prove a Sudoku grid
 solvable using a Perl regex. Python regexes are less powerful than Perl's,
 so if you can't do it in Perl, you can't do it in Python.

As somebody else in the thread pointed out, the set of all valid
Sudoku grids is a finite language, and all finite languages are
regular. QED.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Christian Gollwitzer


Am 26.03.15 um 00:04 schrieb Mark Lawrence:

On 25/03/2015 22:50, Steven D'Aprano wrote:

On Wed, 25 Mar 2015 10:39 pm, Marko Rauhamaa wrote:


I have yet to find practical use for fibonacci numbers.


Many people have failed to find practical uses for many things from
mathematics. Doesn't mean they don't exist:

http://en.wikipedia.org/wiki/Fibonacci_number#Applications



I've just read Alan Turing: The Enigma.  Apparently he was fascinated
by the appearance of Fibonacci numbers in nature, as described here
http://en.wikipedia.org/wiki/Fibonacci_number#In_nature


https://xkcd.com/spiral/
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On Fri, Mar 27, 2015 at 8:07 PM, Frank Millman fr...@chagford.com wrote:
 There seems to be disagreement over the use of the term 'trial and error'.
 How about this for a revised wording -

 It should be possible to reach that solution by a sequence of logical
 deductions. Each step in the sequence must uniquely identify the contents of
 at least one cell based on the information available. Each time a cell is
 identified, that adds to the information available which can then be used to
 identify the contents of further cells. This process continues until the
 contents of all cells have been identified.

 Any puzzle that cannot be solved by this method does not qualify as a true
 Sudoku puzzle.

That's reasonable wording. Another way to differentiate between the
trial and error that we're objecting to and the logical deduction
that we're liking: Avoid backtracking. That is, you never guess a
number and see if the puzzle's solvable, and backtrack if it isn't; at
every step, the deductions you make are absolute certainties.

They might, in some cases, not result in actual result numbers (you
might deduce that either this cell or that cell is a 2), but it's a
certainty, based solely on the clue numbers given.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Frank Millman


Marko Rauhamaa ma...@pacujo.net wrote in message 
news:87fv8sndw1@elektro.pacujo.net...
 Frank Millman fr...@chagford.com:

 Here is another python-based sudoku solver -

 http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py

From its docstring -

 A proper Sudoku puzzle must have a unique solution, and it should be
 possible to reach that solution by a sequence of logical deductions
 without trial and error.

 I don't think that statement holds water. Trial-and-error is at the
 basis of deduction (reductio ad absurdum). The human solver employs it
 in their head. The question is, what is the difference between
 pen-and-paper and in-your-head for a computer program?

[...]

 It solved Marko's original puzzle and Ian's puzzle in less than a
 second. It could not solve Marko's second one, returning impossible
 immediately.

 ... but that realization greatly reduces the value of the solver.


I was not happy with that conclusion, but I was not sure why. Now I think I 
can put it into words.

There seems to be disagreement over the use of the term 'trial and error'. 
How about this for a revised wording -

It should be possible to reach that solution by a sequence of logical 
deductions. Each step in the sequence must uniquely identify the contents of 
at least one cell based on the information available. Each time a cell is 
identified, that adds to the information available which can then be used to 
identify the contents of further cells. This process continues until the 
contents of all cells have been identified.

Any puzzle that cannot be solved by this method does not qualify as a true 
Sudoku puzzle.

Frank



-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 03/27/2015 09:35 AM, Frank Millman wrote:


Dave Angel da...@davea.name wrote in message
news:551557b3.5090...@davea.name...


But now I have to disagree about true Sudoku puzzle.  As we said
earlier, it might make sense to say that puzzles that cannot be solved
that way are not reasonable ones to put in a human Sudoku book.  But why
isn't it a true Sudoku puzzle?



It seems you are correct.

According to Wikipedia http://en.wikipedia.org/wiki/Glossary_of_Sudoku -

A puzzle is a partially completed grid. The initially defined values are
known as givens or clues. A proper puzzle has a single (unique) solution. A
proper puzzle that can be solved without trial and error (guessing) is known
as a satisfactory puzzle. An irreducible puzzle (a.k.a. minimum puzzle) is a
proper puzzle from which no givens can be removed leaving it a proper puzzle
(with a single solution). It is possible to construct minimum puzzles with
different numbers of givens. The minimum number of givens refers to the
minimum over all proper puzzles and identifies a subset of minimum puzzles.

So what I am talking about is called a satisfactory puzzle, which is a
subset of a proper puzzle.



Thanks for the wikipedia reference.  Now we're in violent agreement, and 
even have a vocabulary to use for that agreement.



--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 03/27/2015 05:25 AM, Chris Angelico wrote:

On Fri, Mar 27, 2015 at 8:07 PM, Frank Millman fr...@chagford.com wrote:

There seems to be disagreement over the use of the term 'trial and error'.
How about this for a revised wording -

It should be possible to reach that solution by a sequence of logical
deductions. Each step in the sequence must uniquely identify the contents of
at least one cell based on the information available. Each time a cell is
identified, that adds to the information available which can then be used to
identify the contents of further cells. This process continues until the
contents of all cells have been identified.

Any puzzle that cannot be solved by this method does not qualify as a true
Sudoku puzzle.


That's reasonable wording. Another way to differentiate between the
trial and error that we're objecting to and the logical deduction
that we're liking: Avoid backtracking. That is, you never guess a
number and see if the puzzle's solvable, and backtrack if it isn't; at
every step, the deductions you make are absolute certainties.

They might, in some cases, not result in actual result numbers (you
might deduce that either this cell or that cell is a 2), but it's a
certainty, based solely on the clue numbers given.



I like that wording.  It fits what I meant by trial and error.

Frank:

But now I have to disagree about true Sudoku puzzle.  As we said 
earlier, it might make sense to say that puzzles that cannot be solved 
that way are not reasonable ones to put in a human Sudoku book.  But why 
isn't it a true Sudoku puzzle?


Isn't the fact that one resorts to trial and error simply a consequence 
of the fact that he/she has run out of ideas for more direct rules and 
the data structures to support them?


The simpler rules can be built around a list of possible values for each 
cell.  More complex rules can have a more complex data structure for 
each cell/row/column/box.  And when you run out of ideas for all those, 
you use guess and backtrack, where the entire board's state is your data 
structure.

--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On Sat, Mar 28, 2015 at 12:14 AM, Dave Angel da...@davea.name wrote:
 But now I have to disagree about true Sudoku puzzle.  As we said earlier,
 it might make sense to say that puzzles that cannot be solved that way are
 not reasonable ones to put in a human Sudoku book.  But why isn't it a true
 Sudoku puzzle?

 Isn't the fact that one resorts to trial and error simply a consequence of
 the fact that he/she has run out of ideas for more direct rules and the data
 structures to support them?

 The simpler rules can be built around a list of possible values for each
 cell.  More complex rules can have a more complex data structure for each
 cell/row/column/box.  And when you run out of ideas for all those, you use
 guess and backtrack, where the entire board's state is your data structure.

At that point, it may make a fine mathematical curiosity, but it's not
really a fun puzzle any more. Does true mean playable? I mean, I
could devise a game in which you point your gun anywhere and shoot,
and you kill someone and score 100 points, and no matter what you do,
you can't die, and the game never ends. No strategy, no challenge. No
goal. Is that a game? Well, it's virtually the same thing as any other
FPS, just with a few simplifications. Is it fun? Not very. So is it a
true game?

(This is not purely theoretical, incidentally. I'm currently alpha
testing a new game that I backed on Kickstarter. The Linux version is
built against a different libc than I have, so to make it even run, I
have to jump through some crazy hoops; it's slow, clunky, and not
exactly a fun game... yet. The alpha isn't designed to be
entertaining, it's designed to be a proof-of-concept and to let a
bunch of testers find issues before they go to a wider audience.
Eventually it'll become a fun game, but at the moment, firing it up is
work. Does that mean it's not a true game yet? Philosophical
debate!)

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Frank Millman


Dave Angel da...@davea.name wrote in message 
news:551557b3.5090...@davea.name...

 But now I have to disagree about true Sudoku puzzle.  As we said 
 earlier, it might make sense to say that puzzles that cannot be solved 
 that way are not reasonable ones to put in a human Sudoku book.  But why 
 isn't it a true Sudoku puzzle?


It seems you are correct.

According to Wikipedia http://en.wikipedia.org/wiki/Glossary_of_Sudoku -

A puzzle is a partially completed grid. The initially defined values are 
known as givens or clues. A proper puzzle has a single (unique) solution. A 
proper puzzle that can be solved without trial and error (guessing) is known 
as a satisfactory puzzle. An irreducible puzzle (a.k.a. minimum puzzle) is a 
proper puzzle from which no givens can be removed leaving it a proper puzzle 
(with a single solution). It is possible to construct minimum puzzles with 
different numbers of givens. The minimum number of givens refers to the 
minimum over all proper puzzles and identifies a subset of minimum puzzles.

So what I am talking about is called a satisfactory puzzle, which is a 
subset of a proper puzzle.

Frank



-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 03/27/2015 09:25 AM, Chris Angelico wrote:

On Sat, Mar 28, 2015 at 12:14 AM, Dave Angel da...@davea.name wrote:

But now I have to disagree about true Sudoku puzzle.  As we said earlier,
it might make sense to say that puzzles that cannot be solved that way are
not reasonable ones to put in a human Sudoku book.  But why isn't it a true
Sudoku puzzle?

Isn't the fact that one resorts to trial and error simply a consequence of
the fact that he/she has run out of ideas for more direct rules and the data
structures to support them?

The simpler rules can be built around a list of possible values for each
cell.  More complex rules can have a more complex data structure for each
cell/row/column/box.  And when you run out of ideas for all those, you use
guess and backtrack, where the entire board's state is your data structure.


At that point, it may make a fine mathematical curiosity, but it's not
really a fun puzzle any more.


That's why I addressed my comments at Frank.  You and I are already in 
rough agreement about what makes a human game worthwhile: it has to be 
easy enough to be solvable, and hard enough to be challenging.  Those 
cutoffs differ from one person to another, and from one age group to 
another.  At one time (50+ years ago) I though Tic-Tac-Toe was tricky 
enough to be fun, but now it's always a draw, and only playable against 
a kid.  On the other hand, I play some games which I can only solve 
with the aid of a computer.  Is that cheating?  Not for some games.  I 
have some challenges for which I need/prefer to use a wrench, or a 
screwdriver, or a lawnmower.  That doesn't make them less fun, just 
different fun.


But I took Frank's comments as defining the fine mathematical 
curiosity, and I have more interest in those than I generally do in 
games.


Many games that I hear people talking about, I've never even tried.
I have a TV set which has never been hooked up to an antenna or cable. 
 Only to CD/DVD/BluRay/computer/tablet/cellphone.  So I'm a bit 
strange.  I still enjoy riding a motorcycle,  walking on the beach, or 
seeing a sunset from the backyard.




--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Marko Rauhamaa

Frank Millman fr...@chagford.com:

 So what I am talking about is called a satisfactory puzzle, which is
 a subset of a proper puzzle.

That is impossible to define, though, because some people are mental
acrobats and can do a lot of deep analysis in their heads. What's
satisfactory to you may not be satisfactory to me.

Besides, looking for satisfactory patterns can involve a truckload of
trial and error.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On Sat, Mar 28, 2015 at 12:48 AM, Dave Angel da...@davea.name wrote:
 On the other hand, I play some games which I can only solve with the aid
 of a computer.  Is that cheating?  Not for some games.  I have some
 challenges for which I need/prefer to use a wrench, or a screwdriver, or a
 lawnmower.  That doesn't make them less fun, just different fun.

And I'm presently engaged in a very enjoyable task which most people
wouldn't call a game, but probably more like torture. I'm listening to
two different audio tracks (one on the left speaker, one on the
right), making adjustments to one of them to bring it into alignment
with the other. Not at all less fun... VERY different fun :)

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On Sat, Mar 28, 2015 at 1:09 AM, Dave Angel da...@davea.name wrote:
 On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:

 Frank Millman fr...@chagford.com:

 So what I am talking about is called a satisfactory puzzle, which is
 a subset of a proper puzzle.


 That is impossible to define, though, because some people are mental
 acrobats and can do a lot of deep analysis in their heads. What's
 satisfactory to you may not be satisfactory to me.

 Besides, looking for satisfactory patterns can involve a truckload of
 trial and error.


 I know, let's use regular expressions  g

Part of me is quaking in fear... the other part looking on in morbid
fascination. Can you build a regexp that proves a Sudoku grid
solvable?

OW! Okay, now all of me is quaking in fear. Please do not do this!

Or maybe do. Ow. I can't decide.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On Sat, Mar 28, 2015 at 12:56 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 Frank Millman fr...@chagford.com:

 So what I am talking about is called a satisfactory puzzle, which is
 a subset of a proper puzzle.

 That is impossible to define, though, because some people are mental
 acrobats and can do a lot of deep analysis in their heads. What's
 satisfactory to you may not be satisfactory to me.

 Besides, looking for satisfactory patterns can involve a truckload of
 trial and error.

Not really. I already gave a broad generation algorithm, capable of
generating puzzles at any difficulty you choose. (Well, maximum
difficulty. If you tell it generate HARD puzzles, it might still
generate a MEDIUM or EASY one. But you could post-filter for that.)
The only back-tracking required is at the last step, where it seeks to
minimize the number of clue digits - an optional step, and one that
involves very little backtracking. I think you subsequently posted
code which does broadly the same thing, but without the
difficulty-class checks.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver


On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:

Frank Millman fr...@chagford.com:


So what I am talking about is called a satisfactory puzzle, which is
a subset of a proper puzzle.


That is impossible to define, though, because some people are mental
acrobats and can do a lot of deep analysis in their heads. What's
satisfactory to you may not be satisfactory to me.

Besides, looking for satisfactory patterns can involve a truckload of
trial and error.



I know, let's use regular expressions  g


--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Mark Lawrence


On 27/03/2015 14:09, Dave Angel wrote:

On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:

Frank Millman fr...@chagford.com:


So what I am talking about is called a satisfactory puzzle, which is
a subset of a proper puzzle.


That is impossible to define, though, because some people are mental
acrobats and can do a lot of deep analysis in their heads. What's
satisfactory to you may not be satisfactory to me.

Besides, looking for satisfactory patterns can involve a truckload of
trial and error.



I know, let's use regular expressions  g



Thanks, I've been having a miserable day but that got me chuckling :)

--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread BartC


On 26/03/2015 00:07, Ian Kelly wrote:

On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa ma...@pacujo.net wrote:



It takes about 2 seconds for my Python program to find the answer but it
spends a total of 110 seconds to exhaust the problem space.

The analogous C program finished the whole thing in 200 milliseconds.


Hard for a human doesn't necessarily mean hard for a programmatic
solver in this case. Try your solver on this one:

$ cat sudoku2.dat
. . . 7 . . . . .
1 . . . . . . . .
. . . 4 3 . 2 . .
. . . . . . . . 6
. . . 5 . 9 . . .
. . . . . . 4 1 8
. . . . 8 1 . . .
. . 2 . . . . 5 .
. 4 . . . . 3 . .

I tried the first puzzle you posted, and it took about a second. I
then started running it on this one before I started typing up this
post, and it hasn't finished yet. While that was running, I then tried
running Norvig's solver on this puzzle, and it completed in about 0.07
seconds.


I tried my own brute-force solver, which normally takes 100msec, and it 
took 2 seconds for your hard puzzle, about 20 times longer. (In a 
language using a bytecode interpreter, not Python.)


Using Pypy, it took 90 seconds, instead of 1 second or so. So still 
possibly faster than a human (faster than me certainly).


--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread sohcahtoa82

On Friday, March 27, 2015 at 7:10:54 AM UTC-7, Dave Angel wrote:
 On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
  Frank Millman fr...@chagford.com:
 
  So what I am talking about is called a satisfactory puzzle, which is
  a subset of a proper puzzle.
 
  That is impossible to define, though, because some people are mental
  acrobats and can do a lot of deep analysis in their heads. What's
  satisfactory to you may not be satisfactory to me.
 
  Besides, looking for satisfactory patterns can involve a truckload of
  trial and error.
 
 
 I know, let's use regular expressions  g
 
 
 -- 
 DaveA

You jest, but...

http://www.perlmonks.org/?node_id=471168
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Larry Hudson


On 03/27/2015 07:09 AM, Dave Angel wrote:
[snip]


I know, let's use regular expressions  g



This is totally OT, but...

There was a recent (2015-03-23) item on The Daily WTF web site concerning 
regular expressions.

Take a look at http://thedailywtf.com/articles/regularly-expressing-hate

 -=- Larry -=-

--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Sayth

Good test for pypy to see where it's speed sits between C and Python. 
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Gregory Ewing


Chris Angelico wrote:

Part of me is quaking in fear... the other part looking on in morbid
fascination. Can you build a regexp that proves a Sudoku grid
solvable?


Well, it's *theoretically* possible, since there are a finite
number of possible sudoku puzzles, so if nothing else you
could just use an RE that explicitly matched all the solvable
ones.

I wouldn't like to have to write that RE out by hand, though.

--
Greg
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Steven D'Aprano

On Sat, 28 Mar 2015 01:19 am, Chris Angelico wrote:


 Part of me is quaking in fear... the other part looking on in morbid
 fascination. Can you build a regexp that proves a Sudoku grid
 solvable?

Perl's regular expressions can run arbitrary code using ?{...} which
technically makes them Turing Complete and capable of solving any problem
you can solve in any other language. However the code is written in Perl,
so I call that cheating :-)

Excluding that, the consensus seems to be that Perl's regexes are stronger
than Chomsky regular expressions, but nobody quite knows how much stronger.
It's likely that they are at least as powerful as context-free grammars,
but not as powerful as a Turing machine (excluding embedded Perl code), but
that covers a lot of ground in the hierarchy of language power:

http://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy

So it's an open question as to whether or not you could prove a Sudoku grid
solvable using a Perl regex. Python regexes are less powerful than Perl's,
so if you can't do it in Perl, you can't do it in Python.

But, for what its worth, you can test for prime numbers using a regex:

re.match(r'^1?$|^(11+?)\1+$', '1'*n)

matches if the number n is composite, i.e. it's not a prime.

http://code.google.com/p/pyprimes/source/browse/src/pyprimes/awful.py

My intuition is that given a completed Sudoku grid, you should be able to
prove that it is valid using a Python regex, but given an incomplete one,
probably *not* prove that it is solvable. But I can't justify that in any
objective way.




-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-27 Thread Steven D'Aprano

On Sat, 28 Mar 2015 05:18 am, sohcahto...@gmail.com wrote:

 On Friday, March 27, 2015 at 7:10:54 AM UTC-7, Dave Angel wrote:

 I know, let's use regular expressions  g
 
 
 --
 DaveA
 
 You jest, but...
 
 http://www.perlmonks.org/?node_id=471168

I'm not a Perl expert, but I call that cheating, as it uses the ?{ ... }
construct to embed Perl code in the regex.



-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Frank Millman


Marko Rauhamaa ma...@pacujo.net wrote in message 
news:87r3sdnw5t@elektro.pacujo.net...


 I post below a sudoku solver. I eagerly await neater implementations (as
 well as bug reports).


Here is another python-based sudoku solver -

http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py

From its docstring -

A proper Sudoku puzzle must have a unique solution, and it should be 
possible to reach that solution by a sequence of logical deductions without 
trial and error.  To the extent possible, we strive to keep the same ethic 
in our automated solver, by mimicking human rule-based reasoning, rather 
than resorting to brute force backtracking search.

A neat feature is that, having printed the solution, it then lists every 
step it took in its reasoning process to arrive at the solution.

It solved Marko's original puzzle and Ian's puzzle in less than a second. It 
could not solve Marko's second one, returning impossible immediately.

Here is another one that does not use python, but uses SQL -

https://www.sqlite.org/lang_with.html

You will find it at the bottom of the page, under the heading Outlandish 
Recursive Query Examples.

Frank Millman



-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

Abhiram R abhi.darkn...@gmail.com:

 On Thu, Mar 26, 2015 at 8:54 AM, Ian Kelly ian.g.ke...@gmail.com wrote:
 On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R abhi.darkn...@gmail.com wrote:
 On Mar 26, 2015 5:39 AM, Ian Kelly ian.g.ke...@gmail.com wrote:
 $ cat sudoku2.dat
 . . . 7 . . . . .
 1 . . . . . . . .
 . . . 4 3 . 2 . .
 . . . . . . . . 6
 . . . 5 . 9 . . .
 . . . . . . 4 1 8
 . . . . 8 1 . . .
 . . 2 . . . . 5 .
 . 4 . . . . 3 . .

 I tried the first puzzle you posted, and it took about a second. I
 then started running it on this one before I started typing up this
 post, and it hasn't finished yet.

 So... Is it done yet? And if yes, how long did it take?

 I don't know, I killed it at about 16 minutes.

 :( Too bad. I'll give it a go myself. And then try implementing my own
 solution. Have a lot of time on my hands today :D

Early optimization and so on and so forth...

I have optimized my solution slightly:

  1. precalculated integer division operations (big savings)

  2. interned integers (little savings)

The example above now finishes in 41 minutes on my computer. (The C
version finishes in 13 seconds).

The program runs single-threaded. Taking the trouble to parallelize the
algorithm is out of scope for the purposes of this discussion; it would
necessarily destroy the compactness of the solution.


#!/usr/bin/env python3

import sys

M = 3
N = M * M
P = M * N
Q = M * P

buddies = [ [ buddy
  for buddy in range(Q)
  if buddy != slot and
  (buddy % N == slot % N or
   buddy // N == slot // N or
   buddy // P == slot // P and
   buddy % N // M == slot % N // M) ]
for slot in range(Q) ]
interned = { n : n for n in range(1, N + 1) }
candidates = list(interned.values())

def main():
board = []
for n in sys.stdin.read().split():
try:
board.append(int(n))
except ValueError:
board.append(None)
solve(board)

def solve(board, slot=0):
if slot == Q:
report(board)
elif board[slot] is None:
for candidate in candidates:
if not any(board[buddy] is candidate for buddy in buddies[slot]):
board[slot] = candidate
solve(board, slot + 1)
board[slot] = None
else:
solve(board, slot + 1)

def report(board):
print(\n.join(
 .join(str(board[row * N + col])
 for col in range(N))
for row in range(N)))
print()

if __name__ == '__main__':
main()



Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

Frank Millman fr...@chagford.com:

 Here is another python-based sudoku solver -

 http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py

From its docstring -

 A proper Sudoku puzzle must have a unique solution, and it should be
 possible to reach that solution by a sequence of logical deductions
 without trial and error.

I don't think that statement holds water. Trial-and-error is at the
basis of deduction (reductio ad absurdum). The human solver employs it
in their head. The question is, what is the difference between
pen-and-paper and in-your-head for a computer program?

(Question: Are computers good at blindfold chess?)

 To the extent possible, we strive to keep the same ethic in our
 automated solver, by mimicking human rule-based reasoning, rather than
 resorting to brute force backtracking search.

That's cool...

 A neat feature is that, having printed the solution, it then lists
 every step it took in its reasoning process to arrive at the solution.

 It solved Marko's original puzzle and Ian's puzzle in less than a
 second. It could not solve Marko's second one, returning impossible
 immediately.

... but that realization greatly reduces the value of the solver.

I brought up sudoku solving as a real-world example of the usefulness
of exhaustive recursion. The concerns on astronomical execution times
must be considered but at the same time, one should realize things
aren't as bad as they would seem: exhaustion is a practical way to solve
sudoku puzzles and analogous programming challenges.

The compactness of a working sudoku solver should demonstrate something
about (1) the usefulness of recursion and (2) the expressive power of
Python.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Chris Angelico

On Thu, Mar 26, 2015 at 11:26 PM, Marko Rauhamaa ma...@pacujo.net wrote:
 Frank Millman fr...@chagford.com:

 Here is another python-based sudoku solver -

 http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py

From its docstring -

 A proper Sudoku puzzle must have a unique solution, and it should be
 possible to reach that solution by a sequence of logical deductions
 without trial and error.

 I don't think that statement holds water. Trial-and-error is at the
 basis of deduction (reductio ad absurdum). The human solver employs it
 in their head. The question is, what is the difference between
 pen-and-paper and in-your-head for a computer program?

Nothing. And solving a Sudoku puzzle - or any other puzzle - should
require no guessing. It should be possible to solve purely by logic.
Same goes for every other kind of puzzle out there; it's highly
unsatisfying to play Minesweeper and get to the end with a block of
four squares in a corner, two mines left, and no way of knowing which
diagonal has the mines and which is clear.

No trial-and-error, thanks.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Ian Kelly

On Mar 26, 2015 6:31 AM, Marko Rauhamaa ma...@pacujo.net wrote:

 Frank Millman fr...@chagford.com:

  Here is another python-based sudoku solver -
 
  http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
 
 From its docstring -
 
  A proper Sudoku puzzle must have a unique solution, and it should be
  possible to reach that solution by a sequence of logical deductions
  without trial and error.

 I don't think that statement holds water. Trial-and-error is at the
 basis of deduction (reductio ad absurdum). The human solver employs it
 in their head. The question is, what is the difference between
 pen-and-paper and in-your-head for a computer program?

It's an accurate characterization of the sort of puzzles that are typically
presented as sudoku. I don't think that I have used trial and error, in my
head or otherwise, in any sudoku I have ever solved.

  It solved Marko's original puzzle and Ian's puzzle in less than a
  second. It could not solve Marko's second one, returning impossible
  immediately.

Perhaps this is why that puzzle was described as being so difficult: it
required steps that human solvers don't usually take.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

Ian Kelly ian.g.ke...@gmail.com:

 On Thu, Mar 26, 2015 at 9:48 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 In fact, the trial-and-error technique is used in automated theorem
 proving:

   Lean provers are generally implemented in Prolog, and make proficient
   use of the backtracking engine and logic variables of that language.

   URL: http://en.wikipedia.org/wiki/Lean_theorem_prover

 Sure, but what has this to do with the statement that *sudoku* should
 not require trial and error to solve?

Trial-and-error was presented in opposition to logical deduction, while
really trial-and-error *is* logical deduction.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Ian Kelly

On Thu, Mar 26, 2015 at 9:48 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 Ian Kelly ian.g.ke...@gmail.com:

 On Thu, Mar 26, 2015 at 8:23 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 That's trial and error, aka, reductio ad absurdum.

 Okay, I've probably used single-lookahead trial and error in my
 reasoning at some point. But the example you give is equivalent to the
 deductive process That can't be a 5, so I remove it as a candidate.
 The only place left for a 5 is here, so I remove the 2 as a candidate
 and fill in the 5.

 In fact, the trial-and-error technique is used in automated theorem
 proving:

   Lean provers are generally implemented in Prolog, and make proficient
   use of the backtracking engine and logic variables of that language.

   URL: http://en.wikipedia.org/wiki/Lean_theorem_prover

Sure, but what has this to do with the statement that *sudoku* should
not require trial and error to solve?
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Pete Forman

Here's my Python sudoku solver which I wrote about 10 years ago.

http://petef.22web.org/sudoku/

It works by applying the solving techniques I came up with. No trial and
error or backtracking is used, so it is not up to cracking the very
hardest puzzles. Run time is 15 ms to 45 ms on a 2009 MacBook Pro using
Python 2.7.9.

There are verbose options to print the steps. Sizes and multiple grids
are flexible. IIRC it took a day or two to adapt the program when the
first samurai was published.

$ python sudoku.py -i sudoku2.sud
***|7**|***
1**|***|***
***|43*|2**
---+---+---
***|***|**6
***|5*9|***
***|***|418
---+---+---
***|*81|***
**2|***|*5*
*4*|***|3**
Solved, rating: dead easy
Calculation took 18.006 ms
264|715|839
137|892|645
598|436|271
---+---+---
423|178|596
816|549|723
759|623|418
---+---+---
375|281|964
982|364|157
641|957|382


-- 
Pete Forman
http://petef.22web.org/payg.html
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Chris Angelico

On Fri, Mar 27, 2015 at 1:14 AM, Dave Angel da...@davea.name wrote:
 On 03/26/2015 08:37 AM, Chris Angelico wrote:
 Nothing. And solving a Sudoku puzzle - or any other puzzle - should
 require no guessing. It should be possible to solve purely by logic.
 Same goes for every other kind of puzzle out there; it's highly
 unsatisfying to play Minesweeper and get to the end with a block of
 four squares in a corner, two mines left, and no way of knowing which
 diagonal has the mines and which is clear.

 No trial-and-error, thanks.


 I think you're making an unwarranted assumption here.  Your Minesweeper
 example has two solutions, so there's no way of telling which is the
 correct one.  But I'd claim that there are puzzles which have exactly one
 solution, but which need trial and error at some point to find that
 solution.

Only one can possibly be correct; if you dig one cell, you'll die, and
if you dig the other, you'll win. But you have no way of knowing which
is which, without dying, using some kind of undo feature (orange
smoke comes to mind), and trying the other. Or, of course, guessing
right, in which case you win.

 I'm not sure how to prove it, since somebody could claim that I just haven't
 tried all the non-trial-and-error rules.

With Sudoku, there are some pretty complicated rules and patterns.
Minesweeper is much simpler to prove. But there are still rules and
patterns, and at some point, you simply have to say that a puzzle is
beyond the logic of this set of rules. It might not be beyond a more
comprehensive set of rules, but that doesn't matter; you've proven the
puzzle to be unsolvable *with your (program's) skill set*.

 I did write a Sudoku-solver many years ago, in C++, and it solved the
 typical Sudoku I fed it in about 2ms.  But it was deliberately written to
 apply only rules that humans could readily apply.  No backtracking. I did
 not at that time have any electronic source for puzzles, and I got bored
 with manually entering them in from puzzle books.  So I never actually
 encountered a puzzle it couldn't solve.  I mostly used it to determine that
 a puzzle I couldn't manually solve was in fact uniquely solvable, and that
 I'd just messed up somehow.

 I wish I still had that source code, as it probably sounds like I'm blowing
 smoke here.

 The general approach I used was to make objects of each of the cells, which
 tracked its neighbors to decide whether its value was determined.  And when
 it was determined, it notified its other neighbors.  In turn, if that
 decided a value for any of the neighbors, that cell notified its neighbors.
 Likewise each row or column or box kept track of its state and notified the
 appropriate cells whenever something interesting was discovered.  Then the
 outer loop just tickled each cell in turn, and the solution rippled out.

Not entirely sure I have this correct, but it sounds like you have a
basic solver that uses one rule: If there is no other value that can
be in this cell, you can write this one down. It's certainly possible
to add a lot more sophistication to a solver; for instance, in this
grid, it's possible to place a 4 with certainty:

. . . | . . . | . . .
. . . | 4 . . | . . .
. . . | . . . | . . 4
--+---+--
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . 4 .
--+---+--
. . . | . . . | . . .
. . . | . 1 2 | . . .
4 . . | . . . | . . .

An examination of the bottom-center block shows that the 4 in it must
be on its top row (even though you don't know which of two
possibilities has it), ergo the bottom-right block must have its 4 on
the center row. The more of these kinds of rules you have, the more
puzzles you can solve - but I would still code the solver to avoid
guessing.

 Maybe I'm misinterpreting your phrase No trial and error, thanks. Perhaps
 you're saying that puzzles that require trial and error are no fun to solve
 for humans.  And that's a different matter entirely.  I do the daily KenKen
 puzzles in my local paper, and they're just hard enough to be fun, seldom
 taking longer than I'm willing to take in the mornings.

I agree that they're no fun for humans. That's part of the point, but
not the whole point. Since we're talking about puzzles, here, the
primary purpose of a machine solver is (or should be!) to prove that a
puzzle is solvable, and thus worthy of being given to a human. So the
solver should restrict itself to what's considered worth working with
- and in some cases, might restrict itself even further (generate an
easy puzzle, please), by cutting out some forms of logic. Now, if
your humans are happy with puzzles that they have to guess, then sure,
incorporate guessing in your solver. But if the humans aren't, then
what do you prove by having an electronic solver that can do the
puzzle? There's a small mathematical curiosity to finding out just how
few clues can carry sufficient information to uniquely define a grid,
but that's already been proven. So, that's why I would

Re: Sudoku solver

Dave Angel da...@davea.name:

 When in a playful mood, I wonder if all the Sudoku puzzles out there
 are just permutations of a few hundred written by Will Shortz.

A sudoku solver can be trivially turned into a puzzle generator:


$ ./sudoku.py --generate puzzle.dat
$ cat puzzle.dat
3 . 2 . 4 . . . .
4 5 . . . 6 . . .
6 . . . 9 . . 8 .
. . . . . . 5 . .
. 6 4 . . 9 . 3 .
. 7 3 5 . . . 4 8
. . . . . . 8 . .
. 8 . . 7 . . . 3
. . . . 1 . . . 2

$ ./sudoku.py puzzle.dat 
3 9 2 8 4 7 1 6 5
4 5 8 1 3 6 7 2 9
6 1 7 2 9 5 3 8 4
8 2 1 4 6 3 5 9 7
5 6 4 7 8 9 2 3 1
9 7 3 5 2 1 6 4 8
1 4 9 3 5 2 8 7 6
2 8 5 6 7 4 9 1 3
7 3 6 9 1 8 4 5 2




#!/usr/bin/env python3

import sys, random

M = 3
N = M * M
P = M * N
Q = M * P

EMPTY = .

buddies = [ [ buddy
  for buddy in range(Q)
  if buddy != slot and
  (buddy % N == slot % N or
   buddy // N == slot // N or
   buddy // P == slot // P and
   buddy % N // M == slot % N // M) ]
for slot in range(Q) ]
interned = { n : n for n in range(1, N + 1) }
candidates = list(interned.values())

def main():
if len(sys.argv)  1 and sys.argv[1] == --generate:
generate()
return
board = []
for n in sys.stdin.read().split():
try:
board.append(int(n))
except ValueError:
board.append(EMPTY)
for solution in solve(board):
report(solution)

def generate():
report(minimize(next(solve([ EMPTY ] * Q

def solve(board, slot=0):
if slot == Q:
yield board[:]
elif board[slot] is EMPTY:
shuffled = candidates[:]
random.shuffle(shuffled)
for candidate in shuffled:
for buddy in buddies[slot]:
if board[buddy] is candidate:
break
else:
board[slot] = candidate
yield from solve(board, slot + 1)
board[slot] = EMPTY
else:
yield from solve(board, slot + 1)

def minimize(board):
while True:
nonempty_slots = [ slot for slot in range(Q)
   if board[slot] is not EMPTY ]
random.shuffle(nonempty_slots)
for slot in nonempty_slots:
removed, board[slot] = board[slot], EMPTY
if uniquely_solvable(board):
break
board[slot] = removed
else:
return board

def uniquely_solvable(board):
it = solve(board[:])
next(it)
try:
next(it)
except StopIteration:
return True
return False

def report(board):
print(\n.join(
 .join(str(board[row * N + col])
 for col in range(N))
for row in range(N)))
print()

if __name__ == '__main__':
main()



Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Dave Angel


On 03/26/2015 10:41 AM, Chris Angelico wrote:
 that's already been proven. So, that's why I would avoid guessing.


I've written a lot of solvers for various puzzles. Minesweeper,
Sudoku, a binary Sudoku-like puzzle that I don't really have a good
name for, several others. Every time, I've tried to prove the puzzles
solvable by humans, and sometimes that means rejecting ones that could
technically be solved by brute force.


OK, we're on the same page.  I would use different terminology for some 
of it, but that's okay.


The purist in me would like to write a solver which (within a few 
seconds) could solve any unique puzzle, and identify puzzles which don't 
have a unique solution.  One reason I never got back to writing one was 
I also wanted a difficulty-ranker, which would identify how hard a human 
was likely to consider the puzzle.


Had I been writing it in Python, I'd probably have pursued adding brute 
force, and then used some of the code to write a puzzle-generator.  But 
even then, the problem of ranking was one that had me buffaloed.  It's 
clearly not enough to count the starting clues


(eg. easyness = (clues - 17) * pi )

And writing an efficient program that generates a non-trivial puzzle 
would seem to be quite hard.  I've heard it said that Sudoku puzzles 
generated by machines are much less satisfying than those generated by a 
human.


When in a playful mood, I wonder if all the Sudoku puzzles out there are 
just permutations of a few hundred written by Will Shortz.  Swap around 
rows, columns, boxes, and cryptogram the digit mapping.  Voila, a new 
puzzle.  g  i read a short story about the purpose of jokes, in which 
it said there were only a few hundred of them, the rest were just minor 
variants, and that they were an experiment being run on human beings. 
And once we realized it, they'd shut off our sense of humor.


--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

Marko Rauhamaa ma...@pacujo.net:

 I have optimized my solution slightly:

   1. precalculated integer division operations (big savings)

   2. interned integers (little savings)

 The example above now finishes in 41 minutes on my computer. (The C
 version finishes in 13 seconds).

Any considered harmfull.

Changing an any test to a loop shortens the solving time from 41
minutes to 14 minutes.

Object creation overhead seems to be the killer. The program still has a
prominent integer incrementation...


#!/usr/bin/env python3

import sys

M = 3
N = M * M
P = M * N
Q = M * P

buddies = [ [ buddy
  for buddy in range(Q)
  if buddy != slot and
  (buddy % N == slot % N or
   buddy // N == slot // N or
   buddy // P == slot // P and
   buddy % N // M == slot % N // M) ]
for slot in range(Q) ]
interned = { n : n for n in range(1, N + 1) }
candidates = list(interned.values())

def main():
board = []
for n in sys.stdin.read().split():
try:
board.append(int(n))
except ValueError:
board.append(None)
solve(board)

def solve(board, slot=0):
if slot == Q:
report(board)
elif board[slot] is None:
for candidate in candidates:
for buddy in buddies[slot]:
if board[buddy] is candidate:
break
else:
board[slot] = candidate
solve(board, slot + 1)
board[slot] = None
else:
solve(board, slot + 1)

def report(board):
print(\n.join(
 .join(str(board[row * N + col])
 for col in range(N))
for row in range(N)))
print()

if __name__ == '__main__':
main()



Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

Ian Kelly ian.g.ke...@gmail.com:

 On Thu, Mar 26, 2015 at 8:23 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 That's trial and error, aka, reductio ad absurdum.

 Okay, I've probably used single-lookahead trial and error in my
 reasoning at some point. But the example you give is equivalent to the
 deductive process That can't be a 5, so I remove it as a candidate.
 The only place left for a 5 is here, so I remove the 2 as a candidate
 and fill in the 5.

In fact, the trial-and-error technique is used in automated theorem
proving:

  Lean provers are generally implemented in Prolog, and make proficient
  use of the backtracking engine and logic variables of that language.

  URL: http://en.wikipedia.org/wiki/Lean_theorem_prover


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Dave Angel


On 03/26/2015 08:37 AM, Chris Angelico wrote:

On Thu, Mar 26, 2015 at 11:26 PM, Marko Rauhamaa ma...@pacujo.net wrote:

Frank Millman fr...@chagford.com:


Here is another python-based sudoku solver -

http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py

From its docstring -

A proper Sudoku puzzle must have a unique solution, and it should be
possible to reach that solution by a sequence of logical deductions
without trial and error.


I don't think that statement holds water. Trial-and-error is at the
basis of deduction (reductio ad absurdum). The human solver employs it
in their head. The question is, what is the difference between
pen-and-paper and in-your-head for a computer program?


Nothing. And solving a Sudoku puzzle - or any other puzzle - should
require no guessing. It should be possible to solve purely by logic.
Same goes for every other kind of puzzle out there; it's highly
unsatisfying to play Minesweeper and get to the end with a block of
four squares in a corner, two mines left, and no way of knowing which
diagonal has the mines and which is clear.

No trial-and-error, thanks.


I think you're making an unwarranted assumption here.  Your Minesweeper 
example has two solutions, so there's no way of telling which is the 
correct one.  But I'd claim that there are puzzles which have exactly 
one solution, but which need trial and error at some point to find that 
solution.


I'm not sure how to prove it, since somebody could claim that I just 
haven't tried all the non-trial-and-error rules.


I did write a Sudoku-solver many years ago, in C++, and it solved the 
typical Sudoku I fed it in about 2ms.  But it was deliberately written 
to apply only rules that humans could readily apply.  No backtracking. 
I did not at that time have any electronic source for puzzles, and I got 
bored with manually entering them in from puzzle books.  So I never 
actually encountered a puzzle it couldn't solve.  I mostly used it to 
determine that a puzzle I couldn't manually solve was in fact uniquely 
solvable, and that I'd just messed up somehow.


I wish I still had that source code, as it probably sounds like I'm 
blowing smoke here.


The general approach I used was to make objects of each of the cells, 
which tracked its neighbors to decide whether its value was determined. 
 And when it was determined, it notified its other neighbors.  In turn, 
if that decided a value for any of the neighbors, that cell notified its 
neighbors.  Likewise each row or column or box kept track of its state 
and notified the appropriate cells whenever something interesting was 
discovered.  Then the outer loop just tickled each cell in turn, and the 
solution rippled out.



Maybe I'm misinterpreting your phrase No trial and error, thanks. 
Perhaps you're saying that puzzles that require trial and error are no 
fun to solve for humans.  And that's a different matter entirely.  I do 
the daily KenKen puzzles in my local paper, and they're just hard enough 
to be fun, seldom taking longer than I'm willing to take in the mornings.


--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

Ian Kelly ian.g.ke...@gmail.com:

 I don't think that I have used trial and error, in my head or
 otherwise, in any sudoku I have ever solved.

Of course you have. This here can't be a 2 because if it were a 2, that
there would have to be a 5, which is impossible. Thus, the only
remaining alternative is 3, so I mark that down.

That's trial and error, aka, reductio ad absurdum.

(Additionally, sudoku solvers are known to pencil all kinds of markings
on the sudoku sheets to help the deduction work.)


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Chris Angelico

On Fri, Mar 27, 2015 at 2:03 AM, Dave Angel da...@davea.name wrote:
 On 03/26/2015 10:41 AM, Chris Angelico wrote:
  that's already been proven. So, that's why I would avoid guessing.


 I've written a lot of solvers for various puzzles. Minesweeper,
 Sudoku, a binary Sudoku-like puzzle that I don't really have a good
 name for, several others. Every time, I've tried to prove the puzzles
 solvable by humans, and sometimes that means rejecting ones that could
 technically be solved by brute force.


 OK, we're on the same page.  I would use different terminology for some of
 it, but that's okay.

Good, I thought we were in agreement. And yeah, terminology is tricky.

 The purist in me would like to write a solver which (within a few seconds)
 could solve any unique puzzle, and identify puzzles which don't have a
 unique solution.  One reason I never got back to writing one was I also
 wanted a difficulty-ranker, which would identify how hard a human was likely
 to consider the puzzle.

It'd be pretty straight-forward. You simply define a number of
rule-difficulty-categories, something like this:

EASY
* If eight digits are locked off from a cell by already existing in
its neighbours, the remaining digit must be the one.
* If eight cells in a {row, column, square} have a given digit locked
off, then the remaining cell must contain that digit.

MEDIUM
* Construct possibility regions for digits in squares (ie all the
possible cells that that digit could be in). Any such region which
sits within a single row/column is equivalent to an actual digit in
that row/column for the purposes of exclusions.
* Likewise the converse - if both possible places for the 7 in this
row are in this square, we can depend on the 7 being in one of those,
and not anywhere else in the square.

HARD
* Any complex rule that you feel like coding up. There are plenty of
Sudoku help web sites out there that can provide rule definitions.

IMPOSSIBLE
* Brute force. Attempt to put a digit in a cell, then see if you can
solve the puzzle thereafter. If you prove the puzzle to have no
solutions, that digit cannot be in that cell.

Then, in your solver, you use EASY rules until they provide you with
no more material, and only then move on to MEDIUM rules, etc. The
highest difficulty class that you had to use in solving the puzzle is
the puzzle's difficulty class.

This isn't a perfect system, of course, but it's a decent start. It
also deals with the terminology problem: you can declare a puzzle
solvable, but IMPOSSIBLE class difficulty, which means you have to
guess. Though I would strongly suggest disabling brute-forcing most of
the time, as it'll kill your CPU... especially if you have a puzzle
generation algorithm that looks like this:

Start with a blank grid.
While puzzle not solvable:
Add random clue digit
For each clue digit:
Remove clue
If puzzle not solvable: Reinstate clue

With IMPOSSIBLE deactivated, this is a reasonably straight-forward way
to generate puzzles (and you can deactivate HARD to require a
medium-difficulty puzzle, etc). Otherwise... kerchug, kerchug,
kerchug

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-26 Thread Ian Kelly

On Thu, Mar 26, 2015 at 8:23 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 Ian Kelly ian.g.ke...@gmail.com:

 I don't think that I have used trial and error, in my head or
 otherwise, in any sudoku I have ever solved.

 Of course you have. This here can't be a 2 because if it were a 2, that
 there would have to be a 5, which is impossible. Thus, the only
 remaining alternative is 3, so I mark that down.

 That's trial and error, aka, reductio ad absurdum.

 (Additionally, sudoku solvers are known to pencil all kinds of markings
 on the sudoku sheets to help the deduction work.)

Okay, I've probably used single-lookahead trial and error in my
reasoning at some point. But the example you give is equivalent to the
deductive process That can't be a 5, so I remove it as a candidate.
The only place left for a 5 is here, so I remove the 2 as a candidate
and fill in the 5.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-25 Thread Marko Rauhamaa

John Ladasky john_lada...@sbcglobal.net:

 On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:

 I post below a sudoku solver. I eagerly await neater implementations (as
 well as bug reports).

 So, it's a brute-force, recursive solver? The code is nice and short.
 But I bet it takes a long time to run.

Try it.

The C version takes milliseconds to complete (usually). The Python
version can take the bigger part of a second.

The strategy translates into many analogous problems. For example, I use
it for version dependency resolution in a component system.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-25 Thread John Ladasky

On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:

 I post below a sudoku solver. I eagerly await neater implementations (as
 well as bug reports).

So, it's a brute-force, recursive solver?  The code is nice and short.  But I 
bet it takes a long time to run.

I and a student of mine are working on Sudoku solvers which solve puzzles the 
way that humans would.  Smart, pattern-recognition strategies take less time to 
run... but, obviously, far more time to turn into code!
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On Wed, Mar 25, 2015 at 12:44 PM, John Ladasky
john_lada...@sbcglobal.net wrote:
 On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:

 I post below a sudoku solver. I eagerly await neater implementations (as
 well as bug reports).

 So, it's a brute-force, recursive solver?  The code is nice and short.  But I 
 bet it takes a long time to run.

 I and a student of mine are working on Sudoku solvers which solve puzzles the 
 way that humans would.  Smart, pattern-recognition strategies take less time 
 to run... but, obviously, far more time to turn into code!

I haven't written one myself, but Peter Norvig has a nice example on
the web of a Python sudoku solver using constraint propagation to
limit the search space.

http://norvig.com/sudoku.html

I don't know that I would do it much differently if I were going to
write one myself.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-25 Thread Marko Rauhamaa

Ian Kelly ian.g.ke...@gmail.com:

 The test puzzle that you posted has 23 values already filled in. How
 does it perform on harder puzzles with only 17 clues (the proven
 minimum)? One would expect it to be around a million times slower.

Just try it. The example had a minimum of clues (drop one clue and
you'll get multiple solutions).

URL: http://www.telegraph.co.uk/news/science/science-news/9359579/W
orlds-hardest-sudoku-can-you-crack-it.html mentions this puzzle:


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


It takes about 2 seconds for my Python program to find the answer but it
spends a total of 110 seconds to exhaust the problem space.

The analogous C program finished the whole thing in 200 milliseconds.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On Wed, Mar 25, 2015 at 1:37 PM, Marko Rauhamaa ma...@pacujo.net wrote:
 John Ladasky john_lada...@sbcglobal.net:

 On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:

 I post below a sudoku solver. I eagerly await neater implementations (as
 well as bug reports).

 So, it's a brute-force, recursive solver? The code is nice and short.
 But I bet it takes a long time to run.

 Try it.

 The C version takes milliseconds to complete (usually). The Python
 version can take the bigger part of a second.

The test puzzle that you posted has 23 values already filled in. How
does it perform on harder puzzles with only 17 clues (the proven
minimum)? One would expect it to be around a million times slower.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-25 Thread Chris Angelico

On Thu, Mar 26, 2015 at 7:31 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 Ian Kelly ian.g.ke...@gmail.com:

 The test puzzle that you posted has 23 values already filled in. How
 does it perform on harder puzzles with only 17 clues (the proven
 minimum)? One would expect it to be around a million times slower.

 Just try it. The example had a minimum of clues (drop one clue and
 you'll get multiple solutions).

That's not quite what Ian meant. You've shown that your particular
grid needs every clue to be solvable; Ian is pointing out that it's
possible to create a solvable puzzle (one with a unique solution) with
only 17 clues.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-25 Thread Steven D'Aprano

On Wed, 25 Mar 2015 10:39 pm, Marko Rauhamaa wrote:

 I have yet to find practical use for fibonacci numbers.

Many people have failed to find practical uses for many things from
mathematics. Doesn't mean they don't exist:

http://en.wikipedia.org/wiki/Fibonacci_number#Applications



-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa ma...@pacujo.net wrote:
 Ian Kelly ian.g.ke...@gmail.com:

 The test puzzle that you posted has 23 values already filled in. How
 does it perform on harder puzzles with only 17 clues (the proven
 minimum)? One would expect it to be around a million times slower.

 Just try it. The example had a minimum of clues (drop one clue and
 you'll get multiple solutions).

 URL: http://www.telegraph.co.uk/news/science/science-news/9359579/W
 orlds-hardest-sudoku-can-you-crack-it.html mentions this puzzle:

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

 It takes about 2 seconds for my Python program to find the answer but it
 spends a total of 110 seconds to exhaust the problem space.

 The analogous C program finished the whole thing in 200 milliseconds.

Hard for a human doesn't necessarily mean hard for a programmatic
solver in this case. Try your solver on this one:

$ cat sudoku2.dat
. . . 7 . . . . .
1 . . . . . . . .
. . . 4 3 . 2 . .
. . . . . . . . 6
. . . 5 . 9 . . .
. . . . . . 4 1 8
. . . . 8 1 . . .
. . 2 . . . . 5 .
. 4 . . . . 3 . .

I tried the first puzzle you posted, and it took about a second. I
then started running it on this one before I started typing up this
post, and it hasn't finished yet. While that was running, I then tried
running Norvig's solver on this puzzle, and it completed in about 0.07
seconds.

For the curious, this puzzle was arbitrarily collected from
http://theconversation.com/good-at-sudoku-heres-some-youll-never-complete-5234
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-25 Thread Mark Lawrence


On 25/03/2015 22:50, Steven D'Aprano wrote:

On Wed, 25 Mar 2015 10:39 pm, Marko Rauhamaa wrote:


I have yet to find practical use for fibonacci numbers.


Many people have failed to find practical uses for many things from
mathematics. Doesn't mean they don't exist:

http://en.wikipedia.org/wiki/Fibonacci_number#Applications



I've just read Alan Turing: The Enigma.  Apparently he was fascinated 
by the appearance of Fibonacci numbers in nature, as described here 
http://en.wikipedia.org/wiki/Fibonacci_number#In_nature


--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

--
https://mail.python.org/mailman/listinfo/python-list

Sudoku solver

2015-03-25 Thread Marko Rauhamaa


A lot of discussion was generated by the good, old fibonacci sequence. I
have yet to find practical use for fibonacci numbers. However, the
technique behind a sudoku solver come up every now and again in
practical situations.

I post below a sudoku solver. I eagerly await neater implementations (as
well as bug reports).

Usage:

./sudoku.py sudoku.dat


sudoku.dat:

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


output:

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



sudoku.py:

#!/usr/bin/env python3

import sys

M = 3
N = M * M
Q = N * N

candidates = list(range(1, N + 1))

def main():
board = []
for n in sys.stdin.read().split():
try:
board.append(int(n))
except ValueError:
board.append(None)
solve(board)

def solve(board, slot=0):
if slot == Q:
report(board)
elif board[slot] is None:
for candidate in candidates:
if good(board, slot, candidate):
board[slot] = candidate
solve(board, slot + 1)
board[slot] = None
else:
solve(board, slot + 1)

def good(board, slot, candidate):
(shelf, row), (stack, col) = (divmod(x, M) for x in divmod(slot, N))
for i in range(M):
for j in range(M):
if candidate in (board[(i * M + j) * N + stack * M + col],
 board[(shelf * M + row) * N + i * M + j],
 board[(shelf * M + i) * N + stack * M + j]):
return False
return True

def report(board):
print(\n.join(
 .join(str(board[row * N + col])
 for col in range(N))
for row in range(N)))
print()

if __name__ == '__main__':
main()



Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver

2015-03-25 Thread Abhiram R

On Mar 26, 2015 5:39 AM, Ian Kelly ian.g.ke...@gmail.com wrote:


 Hard for a human doesn't necessarily mean hard for a programmatic
 solver in this case. Try your solver on this one:

 $ cat sudoku2.dat
 . . . 7 . . . . .
 1 . . . . . . . .
 . . . 4 3 . 2 . .
 . . . . . . . . 6
 . . . 5 . 9 . . .
 . . . . . . 4 1 8
 . . . . 8 1 . . .
 . . 2 . . . . 5 .
 . 4 . . . . 3 . .

 I tried the first puzzle you posted, and it took about a second. I
 then started running it on this one before I started typing up this
 post, and it hasn't finished yet.

So... Is it done yet? And if yes, how long did it take?
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Sudoku solver