Beefy Boxes and Bandwidth Generously Provided by pair Networks DiBona
more useful options
 
PerlMonks  

Golf: Sudoku solving

by dragonchild (Archbishop)
on Nov 08, 2007 at 15:51 UTC ( #649734=perlmeditation: print w/ replies, xml ) Need Help??

(Inspired by Re: Subroutine overhead in Perl)

Challenge: Golf a sudoku solver. Bonus points to fast solutions as well. Correct solutions must provide all solutions to a given starting position (test data provided below).

If you want, you can use any/all of the following infrastructure:

  1. @grid - starts with the initial position (with 0's for empty squares).
  2. %search - contains 81 entries, indexed by 0-80, each pointing to an arrayref of 21 entries. These entries are squares that cannot contain the same value as the key.
  3. sudoku_print() - a method that prints the sudoku board as listed in @grid.
  4. Assume that the input has already been parsed into @grid.

I'll post my solutions in a response to this post.

Some samples are:

-,-,4,-,-,2,-,-,3 -,2,-,-,9,-,7,1,5 7,-,-,3,1,-,4,-,- -,1,-,-,-,-,2,-,9 -,4,-,2,7,-,-,-,6 2,8,-,5,-,-,-,-,- 5,-,-,-,-,3,6,-,4 -,3,1,-,-,8,-,-,2 4,6,-,-,5,-,-,3,1 -,-,5,-,-,-,-,4,- -,-,-,8,-,-,-,-,6 3,-,2,-,-,1,-,-,- -,-,-,-,-,4,-,2,- -,-,9,-,-,-,5,-,- -,6,-,3,-,-,-,-,- -,-,-,-,-,-,-,-,3 -,-,-,-,-,5,-,-,- -,1,-,-,-,-,6,8,- -,-,-,-,-,-,-,-,- -,-,-,-,-,3,-,8,5 -,-,1,-,2,-,-,-,- -,-,-,5,-,7,-,-,- -,-,4,-,-,-,1,-,- -,9,-,-,-,-,-,-,- 5,-,-,-,-,-,-,7,3 -,-,2,-,1,-,-,-,- -,-,-,-,4,-,-,-,9 (This input has two solutions. Both are required to be correct.) 9,-,6,-,7,-,4,-,3 -,-,-,4,-,-,2,-,- -,7,-,-,2,3,-,1,- 5,-,-,-,-,-,1,-,- -,4,-,2,-,8,-,6,- -,-,3,-,-,-,-,-,5 -,3,-,7,-,-,-,5,- -,-,7,-,-,5,-,-,- 4,-,5,-,1,-,7,-,8

My criteria for good software:
  1. Does it work?
  2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

Comment on Golf: Sudoku solving
Download Code
Re: Golf: Sudoku solving
by downer (Monk) on Nov 08, 2007 at 17:23 UTC
    a good chance to try backtracking tree search? this sounds like a fun challenge, time to hone my oop perl skills! BTW- what does golf mean?

      Golf is a game in which players try to put a little ball in a little hole with the fewest attempts to do so (called "strokes").

      Perl golf attempts to write a program that achieves some goal in the fewest strokes also—keystrokes. Programmers compete to write the shortest code possible to do the same thing.

      Personally, I dislike Perl golf because it perpetuates the notion that Perl is a line noise write-only language.

        How about tgolf (or pgolf) for shortest time (t in tgolf for time, silent p in pgolf for performance)?
Re: Golf: Sudoku solving
by oxone (Friar) on Nov 08, 2007 at 17:33 UTC
Re: Golf: Sudoku solving
by lidden (Deacon) on Nov 08, 2007 at 20:17 UTC
    "(This input has two solutions. Both are required to be correct.)"

    I am pretty sure a sudoku is only considered to be correct if it has one and only one solution.

      I'm pretty sure you're mistaken.

      Sudoku is a simple constraint resolution problem. The static constraints describe the rules of the game. The dynamic constraints are specified by the initial state of the board.

      You seem to be implying that for some initial state (a partially filled board), there'll be only one correct solution (filled board).I'm quite sure that's not the case.

      It's surely the case that for some problems where the board is mostly filled, that there is only one correct solution; I'd need to see a damn nifty proof to believe that is the case for all conceivable (and valid) starting states.

      -David

        If you are given a Sudoku grid to solve (such as in a newspaper or a puzzle book) and there is more than one solution to it, then you've gotten a decidedly inferior offering, some would say an invalid one (as would I).

        I'm at a loss as to how you got from "only considered to be correct" to "all possible starting states". And proving that, for example, a standard grid with only a single digit filled in can be "solved" in more than one way is trivial.

        But I would disagree with lidden if that was an implied assertion that a program for solving a Sudoku need not be able to deal with such flawed offerings. Indeed, it should probably be able to produce at least two solutions so that you can include them when you write to the source of the puzzle to complain. :)

        - tye        

Re: Golf: Sudoku solving
by eyepopslikeamosquito (Canon) on Nov 08, 2007 at 21:46 UTC

    Mark Byers created a wonderful Shortest Sudoku Solver page, showing shortest Sudoku solvers in many different languages, but the old link seems to be broken now. I remember being amused at the time to notice that several different folks whittled the Perl solution from 188 to 187 to 185 to 184 ... and then along came Ton Hospel and chopped it straight down to around 120! It's sort of deflating when thospel does that to you. :-)

    Update: original link courtesy of the Wayback Machine (Aug 2007). The original shortest was based on a version by "Eccles & Toad":

    use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_ +/9==$i/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80; +R($A[$i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R
    Here is the audit trail of shortenings:
    * Original Eccles & Toad solution (slightly modified) * Mark Byers reduced it to 187 bytes * Gordon McCreight reduced it to 186 bytes * Pablo Carbonell reduced it to 181 bytes * Simon Stroh changed @A=split//,<> to $/=\1;@A=<> to reduce the prog +ram to 179 bytes * Mitsuru Kariya changed @A[map{ ... }] to map@A[ ... ] to reduce th +e program to 178 bytes * Ton Hospel shortened the program to 121 bytes
    Ton Hospel's 121 stroke solver:
    $_=$`.$_.$'.<>;split//;${/[@_[map{$i-($i="@-")%9+$_,9*$_+$i%9,9*$_%26+ +$i-$i%27+$i%9-$i%3}0..8]]/o||do$0}for/0/||print..9
    which can be reduced to 120 bytes, at the cost of using large amounts of memory:
    $_=$`.$_.$'.<>;split//;map{/[@_[map{$i-($i="@-")%9+$_,9*$_+$i%9,9*$_%2 +6+$i-$i%27+$i%9-$i%3}0..8]]/o||do$0}/0/||print..9

      $_=$`.$_.$'.<>;split//;${/[@_[map{$i-($i="@-")%9+$_,9*$_+$i%9,9*$_%26+ +$i-$i%27+$i%9-$i%3}0..8]]/o||do$0}for/0/||print..9

      Dear Monks, I need your help

      I don't understand the "split" statement: no return value, apparently no side effect. Reading split was not helpful... :-/

      Another thing: this solver works fine on debian but loop on win xp (strawberryperl 5.14.2.1)

      UPDATE (solved):Thanks to BrowserUk, tobyink and eyepopslikeamosquito. Very clear and fast answers. FYI, in my case, difference between debian and winxp was in fact, between perl 5.8.8 and 5.14.2.1.

      English is not my mother tongue.
      Les tongues de ma mère sont "made in France".

        Perhaps this explains it:

        C:\test>\perl32\bin\perl -wnle"print $]; split; print join '|', @_" Use of implicit split to @_ is deprecated at -e line 1. evry good boy deserves food 5.008009 evry|good|boy|deserves|food C:\test>\perl64\bin\perl -wnle"print $]; split; print join '|', @_" Use of implicit split to @_ is deprecated at -e line 1. the quick brown foox 5.010001 the|quick|brown|foox Terminating on signal SIGINT(2) Terminating on signal SIGINT(2) C:\test>perl -wnle"print $]; split; print join '|', @_" Useless use of split in void context at -e line 1. evry good boy deserves food 5.016001

        As you can see, in 5.8 and 5.10, split in a void context was deprecated, but it put its results into @_;

        Somewhere between 5.10 and 5.16, the deprecation was enforced and that facility was removed. Which mean your golf script no longer works.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

        For Perl up to and including 5.10, calling split in scalar or void context had the side-effect of setting @_. This mis-feature was removed in Perl 5.12. That was great news for most Perl programmers because this side-effect "feature" was unnecessary, an ugly wart. It was sad news for golfers though because side-effects are frequently useful in golf. In fact, I recently experienced a similar split annoyance in Compression in Golf: Part III, as described in the "Fun with split" section in that node.

        Simply changing @_ to @z say should fix thospel's original solution at the cost of three strokes:

        $_=$`.$_.$'.<>;@z=split//;${/[@z[map{$i-($i="@-")%9+$_,9*$_+$i%9,9*$_% +26+$i-$i%27+$i%9-$i%3}0..8]]/o||do$0}for/0/||print..9
        I expect you could do better than that, though I haven't tried.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://649734]
Approved by Corion
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (7)
As of 2014-04-18 01:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (460 votes), past polls