in reply to Subroutine overhead in Perl

I ran your code as written and it didn't work. I used the sample input (taken from the sudoku widget in my iGoogle): 
-,-,4,-,-,2,-,-,3
-,2,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

[download]

In reading the code, your recursive function doesn't actually solve anything, as far as I can tell. Please verify that you actually posted the right code.

As for what's going on, there are a number of places I can see as possibly improving the code and the performance, potentially by several orders of magnitude. I just need to see working code first in order to apply the right fixes.

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?

Replies are listed 'Best First'.
Re^2: Subroutine overhead in Perl
by enemyofthestate (Monk) on Nov 06, 2007 at 18:31 UTC
    Your grid has no solution since 2 appear twice in the second row. 
    -,-,4,-,-,2,-,-,3
-,2,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

    [download]

    Sorry, the program is not very friendly about errors. I kinda try to get the algorithm right then work on the error checking...

[reply]
[d/l]
      Cool. I have a functioning run now. It ran in 0.012s on my Macbook Pro on that test input. What input did you use?
      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?
[reply]

        Here are "easiest" and "hardest" of the final test files plus one really evil bugger one of developers found. Test time are on a Dell Optiplex 745:

        Processor: Core 2
        Speed: 1.86 GHz
        Level 1 cache: 32KB
        Level II cache: 256M
        Main RAM: 4G 

        easy

-,-,-,-,-,-,5,-,-
7,6,-,5,1,-,3,-,-
8,5,-,-,7,-,-,1,4
-,-,-,-,-,1,-,7,3
3,1,7,9,-,5,8,4,6
4,9,-,7,-,-,-,-,-
9,7,-,-,3,-,-,2,5
-,-,6,-,9,2,-,8,1
-,-,4,-,-,-,-,-,-

real    0m0.038s
user    0m0.027s
sys     0m0.006s

hard

-,-,-,-,-,-,-,-,-
-,-,-,-,-,3,-,8,5
-,-,1,-,2,-,-,-,-
-,-,-,5,-,7,-,-,-
-,-,4,-,-,-,1,-,-
-,9,-,-,-,-,-,-,-
5,-,-,-,-,-,-,7,3
-,-,2,-,1,-,-,-,-
-,-,-,-,4,-,-,-,9

real    0m5.324s
user    0m5.311s
sys     0m0.007s

evil

-,-,5,-,-,-,-,4,-
-,-,-,8,-,-,-,-,6
3,-,2,-,-,1,-,-,-
-,-,-,-,-,4,-,2,-
-,-,9,-,-,-,5,-,-
-,6,-,3,-,-,-,-,-
-,-,-,-,-,-,-,-,3
-,-,-,-,-,5,-,-,-
-,1,-,-,-,-,6,8,-

real    0m27.371s
user    0m27.207s
sys     0m0.020s

        [download]
[reply]
[d/l]
Re^2: Subroutine overhead in Perl
by Anonymous Monk on Nov 06, 2007 at 18:44 UTC
    i'm not a sudoku player, but i thought that the objective was...
    ...each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9, only one time each (that is, exclusively).
    (from wikipedia sudoku article, emphasis added).

    since the second row ("-,2,2,-,9,-,7,1,5") contains 2 twice, is your test input correct?

[reply]
[d/l]

      A very special testcase is the following sudoku:

      9-6-7-4-3
---4--2--
-7--23-1-
5-----1--
-4-2-8-6-
--3-----5
-3-7---5-
--7--5---
4-5-1-7-8

      [download]
      which has two solutions: 
      926571483
351486279
874923516
582367194
149258367
763194825
238749651
617835942
495612738

      [download]
      and 
      926571483
351486279
874923516
582367194
149258367
763149825
238794651
617835942
495612738

      [download]

      Best regards,
      perl -e "s>>*F>e=>y)\*martinF)stronat)=>print,print v8.8.8.32.11.32"

[reply]
[d/l]
[select]
        AFAIK, a "good" SuDoKu puzzle should have a unique solution.

        Flavio
        perl -ple'$_=reverse' <<<ti.xittelop@oivalf

        Io ho capito... ma tu che hai detto?
[reply]

In Section Seekers of Perl Wisdom