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 3 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 5 of 5 — ← Prev page 1 2 3 4 [5]

#88160

FromChris Angelico <rosuav@gmail.com>
Date2015-03-28 00:58 +1100
Message-ID<mailman.257.1427464997.10327.python-list@python.org>
In reply to#88045
On Sat, Mar 28, 2015 at 12:48 AM, Dave Angel <davea@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

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

#88296

Frommr.smittye@gmail.com
Date2015-03-29 16:39 -0700
Message-ID<eab75711-fabf-4725-ab5c-d19432a0d564@googlegroups.com>
In reply to#87940
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.

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

#88330

FromMarko Rauhamaa <marko@pacujo.net>
Date2015-03-30 12:24 +0300
Message-ID<87bnjarg6i.fsf@elektro.pacujo.net>
In reply to#88296
mr.smittye@gmail.com:

> 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.

It ain't neater if it don't fit in your posting like mine did.


Marko

[toc] | [prev] | [standalone]

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

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

csiph-web