Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #87940 > unrolled thread

Sudoku solver

Started byMarko Rauhamaa <marko@pacujo.net>
First post2015-03-25 13:39 +0200
Last post2015-03-30 12:24 +0300
Articles 20 on this page of 83 — 21 participants

Back to article view | Back to comp.lang.python

Contents

  Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-25 13:39 +0200
    Re: Sudoku solver John Ladasky <john_ladasky@sbcglobal.net> - 2015-03-25 11:44 -0700
      Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-25 13:05 -0600
      Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-25 21:37 +0200
        Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-25 14:09 -0600
          Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-25 22:31 +0200
            Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-26 09:40 +1100
            Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-25 18:07 -0600
              Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-27 20:04 +0000
            Re: Sudoku solver Abhiram R <abhi.darkness@gmail.com> - 2015-03-26 08:26 +0530
            Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-25 21:24 -0600
            Re: Sudoku solver Abhiram R <abhi.darkness@gmail.com> - 2015-03-26 08:58 +0530
              Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 14:13 +0200
                Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 16:15 +0200
            Re: Sudoku solver albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 23:10 +0000
        Re: Sudoku solver Sayth <flebber.crue@gmail.com> - 2015-03-27 20:39 -0700
          Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-28 23:50 +0000
            Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-29 11:12 +1100
              Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 21:59 +0100
                Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-29 22:19 +0100
                  Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 22:59 +0100
            Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-29 14:06 +1100
              Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-29 15:10 +1100
                Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-29 21:35 +1100
                  Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-29 21:54 +1100
                  Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 13:01 +0100
                    Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 16:23 +0100
              Re: Sudoku solver Christian Gollwitzer <auriocus@gmx.de> - 2015-03-29 09:57 +0200
                Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-30 11:54 +0100
              Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 12:25 +0100
                Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-29 21:03 +0300
                  Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-29 19:26 +0100
                    Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-29 21:33 +0300
                  Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 22:11 +0100
                  Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-30 00:50 -0600
                    Re: Sudoku solver Christian Gollwitzer <auriocus@gmx.de> - 2015-03-30 09:13 +0200
                      Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-30 01:29 -0600
                        Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-30 12:16 +0300
                      Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-30 04:16 -0400
                      Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-30 02:57 -0600
                      Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-30 20:13 +1100
            Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-29 22:21 +0100
              Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 23:17 +0100
                Re: Sudoku solver Seymore4Head <Seymore4Head@Hotmail.invalid> - 2015-03-29 21:40 -0400
    Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-26 09:50 +1100
      Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-25 23:04 +0000
        Re: Sudoku solver Christian Gollwitzer <auriocus@gmx.de> - 2015-03-27 07:40 +0100
    Re: Sudoku solver "Frank Millman" <frank@chagford.com> - 2015-03-26 10:19 +0200
      Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 14:26 +0200
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-26 23:37 +1100
        Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-26 07:15 -0600
          Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 16:23 +0200
            Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-26 09:06 -0600
              Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 17:48 +0200
                Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-26 10:20 -0600
                  Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 18:47 +0200
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-26 10:14 -0400
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-27 01:41 +1100
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-26 11:03 -0400
          Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 17:42 +0200
            Re: Sudoku solver Pete Forman <petef4+usenet@gmail.com> - 2015-03-26 22:24 +0000
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-27 02:21 +1100
        Re: Sudoku solver Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-03-26 20:42 -0400
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-27 09:14 -0400
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-28 00:25 +1100
        Re: Sudoku solver "Frank Millman" <frank@chagford.com> - 2015-03-27 15:35 +0200
          Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-27 15:56 +0200
            Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-27 10:09 -0400
              Re: Sudoku solver sohcahtoa82@gmail.com - 2015-03-27 11:18 -0700
                Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-28 12:46 +1100
              Re: Sudoku solver Larry Hudson <orgnut@yahoo.com> - 2015-03-27 16:48 -0700
            Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-28 01:07 +1100
            Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-28 01:19 +1100
              Re: Sudoku solver Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-03-28 14:13 +1300
              Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-28 12:40 +1100
                Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-28 02:24 -0600
            Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-27 16:03 +0000
            Re: Sudoku solver Virgil Stokes <vs@it.uu.se> - 2015-03-28 19:36 +0100
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-27 09:48 -0400
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-27 09:52 -0400
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-28 00:58 +1100
    Re: Sudoku solver mr.smittye@gmail.com - 2015-03-29 16:39 -0700
      Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-30 12:24 +0300

Page 1 of 5  [1] 2 3 4 5  Next page →

#87940 — Sudoku solver

FromMarko Rauhamaa <marko@pacujo.net>
Date2015-03-25 13:39 +0200
SubjectSudoku solver
Message-ID<87r3sdnw5t.fsf@elektro.pacujo.net>
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

[toc] | [next] | [standalone]

#87963

FromJohn Ladasky <john_ladasky@sbcglobal.net>
Date2015-03-25 11:44 -0700
Message-ID<4e81bdb9-52db-46e6-b449-d4241cb2a3f2@googlegroups.com>
In reply to#87940
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!

[toc] | [prev] | [next] | [standalone]

#87966

FromIan Kelly <ian.g.kelly@gmail.com>
Date2015-03-25 13:05 -0600
Message-ID<mailman.155.1427310381.10327.python-list@python.org>
In reply to#87963
On Wed, Mar 25, 2015 at 12:44 PM, John Ladasky
<john_ladasky@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.

[toc] | [prev] | [next] | [standalone]

#87969

FromMarko Rauhamaa <marko@pacujo.net>
Date2015-03-25 21:37 +0200
Message-ID<87twx8amww.fsf@elektro.pacujo.net>
In reply to#87963
John Ladasky <john_ladasky@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

[toc] | [prev] | [next] | [standalone]

#87977

FromIan Kelly <ian.g.kelly@gmail.com>
Date2015-03-25 14:09 -0600
Message-ID<mailman.159.1427314248.10327.python-list@python.org>
In reply to#87969
On Wed, Mar 25, 2015 at 1:37 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> John Ladasky <john_ladasky@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.

[toc] | [prev] | [next] | [standalone]

#87979

FromMarko Rauhamaa <marko@pacujo.net>
Date2015-03-25 22:31 +0200
Message-ID<87iodoakft.fsf@elektro.pacujo.net>
In reply to#87977
Ian Kelly <ian.g.kelly@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

[toc] | [prev] | [next] | [standalone]

#87988

FromChris Angelico <rosuav@gmail.com>
Date2015-03-26 09:40 +1100
Message-ID<mailman.165.1427323235.10327.python-list@python.org>
In reply to#87979
On Thu, Mar 26, 2015 at 7:31 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Ian Kelly <ian.g.kelly@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

[toc] | [prev] | [next] | [standalone]

#88005

FromIan Kelly <ian.g.kelly@gmail.com>
Date2015-03-25 18:07 -0600
Message-ID<mailman.171.1427328485.10327.python-list@python.org>
In reply to#87979
On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Ian Kelly <ian.g.kelly@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

[toc] | [prev] | [next] | [standalone]

#88180

FromBartC <bc@freeuk.com>
Date2015-03-27 20:04 +0000
Message-ID<RJiRw.1183730$xe1.222210@fx47.am4>
In reply to#88005
On 26/03/2015 00:07, Ian Kelly wrote:
> On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa <marko@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

[toc] | [prev] | [next] | [standalone]

#88016

FromAbhiram R <abhi.darkness@gmail.com>
Date2015-03-26 08:26 +0530
Message-ID<mailman.175.1427339107.10327.python-list@python.org>
In reply to#87979

[Multipart message — attachments visible in raw view] — view raw

On Mar 26, 2015 5:39 AM, "Ian Kelly" <ian.g.kelly@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.

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

[toc] | [prev] | [next] | [standalone]

#88017

FromIan Kelly <ian.g.kelly@gmail.com>
Date2015-03-25 21:24 -0600
Message-ID<mailman.176.1427340295.10327.python-list@python.org>
In reply to#87979
On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R <abhi.darkness@gmail.com> wrote:
>
> On Mar 26, 2015 5:39 AM, "Ian Kelly" <ian.g.kelly@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.
>
> Sooooo... Is it done yet? And if yes, how long did it take?

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

[toc] | [prev] | [next] | [standalone]

#88018

FromAbhiram R <abhi.darkness@gmail.com>
Date2015-03-26 08:58 +0530
Message-ID<mailman.177.1427340533.10327.python-list@python.org>
In reply to#87979
On Thu, Mar 26, 2015 at 8:54 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R <abhi.darkness@gmail.com> wrote:
>>
>> On Mar 26, 2015 5:39 AM, "Ian Kelly" <ian.g.kelly@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.
>>
>> Sooooo... Is it done yet? And if yes, how long did it take?
>
> I don't know, I killed it at about 16 minutes.
> --
> https://mail.python.org/mailman/listinfo/python-list

:( 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

-- 
-Abhiram R

[toc] | [prev] | [next] | [standalone]

#88044

FromMarko Rauhamaa <marko@pacujo.net>
Date2015-03-26 14:13 +0200
Message-ID<87k2y4neh5.fsf@elektro.pacujo.net>
In reply to#88018
Abhiram R <abhi.darkness@gmail.com>:

> On Thu, Mar 26, 2015 at 8:54 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R <abhi.darkness@gmail.com> wrote:
>>> On Mar 26, 2015 5:39 AM, "Ian Kelly" <ian.g.kelly@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.
>>>
>>> Sooooo... 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

[toc] | [prev] | [next] | [standalone]

#88056

FromMarko Rauhamaa <marko@pacujo.net>
Date2015-03-26 16:15 +0200
Message-ID<878uejondt.fsf@elektro.pacujo.net>
In reply to#88044
Marko Rauhamaa <marko@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

[toc] | [prev] | [next] | [standalone]

#88787

Fromalbert@spenarnc.xs4all.nl (Albert van der Horst)
Date2015-04-10 23:10 +0000
Message-ID<5528587a$0$23291$e4fe514c@dreader34.news.xs4all.nl>
In reply to#87979
In article <87iodoakft.fsf@elektro.pacujo.net>,
Marko Rauhamaa  <marko@pacujo.net> wrote:
>Ian Kelly <ian.g.kelly@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.

That is a more reasonable time for a realistic algorithm. This puzzle
takes 255 ms in a program that I wrote in 2008 in Forth.

>
>
>Marko

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#88200

FromSayth <flebber.crue@gmail.com>
Date2015-03-27 20:39 -0700
Message-ID<82e7c5b9-2f0f-405b-859c-b74916c475e0@googlegroups.com>
In reply to#87969
Good test for pypy to see where it's speed sits between C and Python.

[toc] | [prev] | [next] | [standalone]

#88239

FromBartC <bc@freeuk.com>
Date2015-03-28 23:50 +0000
Message-ID<R6HRw.1255136$4b6.945049@fx44.am4>
In reply to#88200
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

[toc] | [prev] | [next] | [standalone]

#88240

FromChris Angelico <rosuav@gmail.com>
Date2015-03-29 11:12 +1100
Message-ID<mailman.296.1427587957.10327.python-list@python.org>
In reply to#88239
On Sun, Mar 29, 2015 at 10:50 AM, BartC <bc@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

[toc] | [prev] | [next] | [standalone]

#88281

FromBartC <bc@freeuk.com>
Date2015-03-29 21:59 +0100
Message-ID<JIZRw.476853$mB1.230685@fx32.am4>
In reply to#88240
On 29/03/2015 00:12, Chris Angelico wrote:
> On Sun, Mar 29, 2015 at 10:50 AM, BartC <bc@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

[toc] | [prev] | [next] | [standalone]

#88283

FromMark Lawrence <breamoreboy@yahoo.co.uk>
Date2015-03-29 22:19 +0100
Message-ID<mailman.314.1427664015.10327.python-list@python.org>
In reply to#88281
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 <bc@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

[toc] | [prev] | [next] | [standalone]

Page 1 of 5  [1] 2 3 4 5  Next page →

Back to top | Article view | comp.lang.python

csiph-web