Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Sudoku solver

by ecube (Initiate)
on Aug 11, 2012 at 08:53 UTC ( #986879=perlquestion: print w/ replies, xml ) Need Help??
ecube has asked for the wisdom of the Perl Monks concerning the following question:

Edmund von der Burg (ecclestoad.co.uk)has written a simple sudoku solver. The solver processes one sudoku and then dies.

To be able to handle a list of sudokus as input I adhoc replaced the "die" command by "warn".

That had the effect that the execution time for the 5 sudokos of the example increased from 82 s (for die) to 717 s.

How come?
use integer; my $start = time; while(<DATA>){ if(/#----END----#/){ my $duration = time - $start; die "Execution time: $duration s\n"; } @A = split //,; &R; } 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; } $sum=0; for(@A){$sum+=$_} print" $sum\n"; warn @A; # Execution time = 717 s # die @A; # Execution time 31 + 31 + 14 + 1 + 5 = 82 s } __DATA__ 1204003003000100500060001007000900000406030000030020005000807000070000 +05000000098 0000000390000010050030508000080900060700020001004000000090800500200006 +00400700000 1203000043500001000040000000054002006000700000000080900031005000000090 +70000060008 0030000004000800360080001000400600730009000000000020050040700686000000 +00700600500 8000000000036000000700902000500070000000457000001000300010000680085000 +10090000400 #----END----# 1284653793742198569568371427651984232496735818135429675923867144879216 +35631754298 7518462398923714656432598712381975469745623181654389273196847525279136 +84486725193 1263957843598471628746219539854162376319728452475386917631845294182593 +76592763418 1234567894571892369683271542495618735769384128317426953142759686958143 +27782693541 8127536499436821756754912831542378963698457212871695345219743684385269 +17796318452

Comment on Sudoku solver
Download Code
Re: Sudoku solver
by Anonymous Monk on Aug 11, 2012 at 09:54 UTC

    Its because you used an obfuscation golf as a starting point :) an obfuscation that uses recursion based on global variables , not arguments passed -- the main purpose behind obfuscations is to hide(trick) how the code works, and purpose behind golf is to do it in as few characters as possible

    If you want to do multiple games, you should use something from cpan ( sudoku solver ) like Games::Sudoku::Solver - Solve 9x9-Sudokus recursively

    or Games::Sudoku::OO::Board

Re: Sudoku solver
by moritz (Cardinal) on Aug 11, 2012 at 10:08 UTC
    The die is used for control flow here -- there's a deep recursion going on, and once a solution is found, all of these recursive subs can be terminated at once. That's what die does.

    And warn doesn't -- it just prints a warning, and doesn't abort the current routines. So it makes the solver search for more solutions even after a solution is found. Which is why it takes much longer.

    A possible (still hacky) approach is to do the BLOCK form of eval to catch the exception, print the result and then start the recursion anew with the next Sudoku.

      maybe like

      print forgetR( ... ); sub forgetR { local @A; if( 1 == @_ ){ @A = split //, @_; } else { @A = @_; } eval { R(); }; warn "CAUGHT DEATH $@ "; return @A; }

      forgetR takes either a line (like from __DATA__) or a list

      I actually found a non-obfuscated, non-golfed Sudoku solver in C++ once that used a similar technique; recurse, and then throw an exception for any branch that didn't pan out. There were exceptions at multiple levels, each being caught to wipe out branches. Worked pretty well, though I could faintly hear Dijkstra moaning when I ran it.

      I wish I could find and link to it now. It was interesting.


      Dave

Re: Sudoku solver
by sundialsvc4 (Monsignor) on Aug 11, 2012 at 14:49 UTC

    And for whatever it may be worth, GNU Prolog has an FD-solver that can easily solve any such problem, as well as logic-problems and other things.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (12)
As of 2014-08-29 14:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (280 votes), past polls