Re: Sudoku solver

Date	2015-03-26 11:03 -0400
From	Dave Angel <davea@davea.name>
Subject	Re: Sudoku solver
References	(1 earlier) <mailman.188.1427358005.10327.python-list@python.org> <87fv8sndw1.fsf@elektro.pacujo.net> <CAPTjJmrq4+W7vgVmZZKnOCFtTy5R27vinD1mFUTEyhaUKA+BuQ@mail.gmail.com> <55141449.1030600@davea.name> <CAPTjJmr7p1wYhefJz4RGvhO4F8sTc7tT6BKtGy3m9xrPV+aegg@mail.gmail.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.204.1427382215.10327.python-list@python.org> (permalink)

Show all headers | View raw

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

Thread

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

csiph-web