Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 26 Mar 2015 11:03:16 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Sudoku solver
References: <87r3sdnw5t.fsf@elektro.pacujo.net> <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>
In-Reply-To: <CAPTjJmr7p1wYhefJz4RGvhO4F8sTc7tT6BKtGy3m9xrPV+aegg@mail.gmail.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.204.1427382215.10327.python-list@python.org>
Lines: 40
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:88059

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