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

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

Sudoku solver

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

#88101

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

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

#88065

On Fri, Mar 27, 2015 at 2:03 AM, Dave Angel <davea@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

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

#88114

On Thu, 26 Mar 2015 23:37:10 +1100, Chris Angelico <rosuav@gmail.com>
declaimed the following:

>
>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.
>
	I've encountered (a few years ago, when Sudoku became popular) some
puzzles in books that were like your Minesweeper example.

	The difference being that either "diagonal" produced a valid solution,
whereas Minesweeper was "ask the Fates to be kind" (and the reason the
original M$ Minesweeper never "died" on the first move -- the mines weren't
placed until the player made the first choice).


	These were Sudoku puzzles where the last four empty cells formed a
square, such that putting X on one diagonal and Y on the other diagonal
formed a valid solution... But so did swapping the X/Y diagonals.
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

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

#88149

On 03/27/2015 05:25 AM, Chris Angelico wrote:
> On Fri, Mar 27, 2015 at 8:07 PM, Frank Millman <frank@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

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

#88152

On Sat, Mar 28, 2015 at 12:14 AM, Dave Angel <davea@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

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

#88155

"Dave Angel" <davea@davea.name> wrote in message 
news:551557B3.5090102@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

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

#88159

"Frank Millman" <frank@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

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

#88161

On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
> "Frank Millman" <frank@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

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

#88176

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" <frank@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

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

#88199

On Sat, 28 Mar 2015 05:18 am, sohcahtoa82@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

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

#88190

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

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

#88162

On Sat, Mar 28, 2015 at 12:56 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> "Frank Millman" <frank@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

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

#88165

On Sat, Mar 28, 2015 at 1:09 AM, Dave Angel <davea@davea.name> wrote:
> On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
>>
>> "Frank Millman" <frank@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?

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

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

ChrisA

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

#88196

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

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

#88198

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

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

#88211

On Fri, Mar 27, 2015 at 7:40 PM, Steven D'Aprano
<steve+comp.lang.python@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.

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

#88170

On 27/03/2015 14:09, Dave Angel wrote:
> On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
>> "Frank Millman" <frank@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

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

#88235

On 27-Mar-2015 15:09, Dave Angel wrote:
> On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
>> "Frank Millman" <frank@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

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

#88156

On 03/27/2015 09:25 AM, Chris Angelico wrote:
> On Sat, Mar 28, 2015 at 12:14 AM, Dave Angel <davea@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

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

#88158

On 03/27/2015 09:35 AM, Frank Millman wrote:
>
> "Dave Angel" <davea@davea.name> wrote in message
> news:551557B3.5090102@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

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

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

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

csiph-web