Dropsafe

by Alec Muffett

So I wrote a Sudoku solver but … #firstworldprogrammerproblems

So I wanted something to do and wrote a Sudoku solver; I’ve never liked (or even done) Sudoku but ever since Nigel Ross told me of his travails of solving it in Prolog* I’ve wanted to have a go.

So I went for a nice long walk, worked out the algorithm (approximately), worked out the data structures in my head, came home, roughed it out in Python, got it working, and fed a newspaper puzzle into it.

Aaaaaaannnndd… and it never got past the loader. This is because I’d written the damn thing properly:

  1. start with a blank grid where every cell (range 0..80 inclusive) can contain any possibility in the range 1..9
  2. load the puzzle by setting specific cells to be specific numbers
  3. each time you set a cell to value N, elide possibility N from the possibilities of all other companion cells in the relevant row, column, and 3×3 square
  4. if the elision reduces a companion cell to a single possibility then (v. important) recursively elide that from all of its companion cells
  5. the grid is now stable but may still contain cells that have multiple possibilities
  6. iterate through the cells with the fewest remaining possibilities; for each one, clone the grid and use use the clone to test each possibility in turn (by recursing step 3)
  7. when no cell contains more than one possibility, the puzzle is solved.

…except the newspaper sudokus which I’d decided to use as test vectors never made it past step 5; the puzzles were so data-rich that they were solved by the loading process without even using the clone-and-recurse search mechanism.

Most disappointing. Most disappointed in mankind. I had to delete bits of data from the ‘newspaper-grade’ puzzles to get the engine to start hunting.

The interesting thing is that for an experiment I’ve now added two extra constraints – that numbers on the diagonals be unique – and the result seems to be pathological.  The puzzles go from instant solution to indefinitely chugging. Hmmm…

—
* and of wanting to wire it to an OCR system to save typing-in the puzzles; Nigel is an über-geek

⊞

Comments

11 responses to “So I wrote a Sudoku solver but … #firstworldprogrammerproblems”

  1. alecm

    aha: solution to the pathology, put something (anything) in the centre square; it collapses the search a lot faster once the diagonals are in play.

    215 637 894
    679 428 135
    348 159 267
    127 365 489
    594 812 673
    863 794 512
    436 571 928
    782 946 351
    951 283 746

    Reply
  2. Max Allan

    I think you never get to step 5 because you should never need to solve sudokus like that. There should always be a logical solution and never require a guess. (If I understand your explanation)
    Although I’m surprised the simple version of the algorithm gets it. I often see situations where I solve by noticing that a value is valid in a certain row but because that would leave the next block unable to hold that value due to existing entries, you can’t place it there. It’s a sort of second recursion of the basic logical process.
    (This might be your step4, I can’t quite follow your meaning)

    Reply
  3. Simon Waters

    I pondered doing this the “hard way”.

    In that I figure there aren’t that many possible solved Sudoku, especially if you include various symmetries and the obvious 9! multiplier of choosing the numbers. Should be possible to simple match the starting set with the solution.

    But seems I underestimated a bit since apparently there are 5.4 billion possible distinct solutions, so the look-up table might eat rather too much of my hard disk space. Still I think it is a plausible approach and a zillion times harder than writing a simple solver. Possibly one could not store most of the 5.4 billion, but maybe just the possible grids of permitted one number arrangements, which I assume is 9! fewer, and just see if a solution exists with each overlapping grid.

    Note where you have two cells in a row that must both be 1 or 2, then you can remove 1 and 2 as possibilities from all other cells in that row, and similar deductions involving more numbers, would reduce the iterative solutions you need to try. Although I assume on modern hardware even in interpreted languages it already solves them near instantly?

    And yes most newspaper Sudoku are too easy.

    Reply
  4. Brad Blumenthal

    I remember reading Peter Norvig’s take on this a couple of years ago: http://norvig.com/sudoku.html

    He also did it in Python and treated it as a tutorial on the language (which is why I was reading it).

    Simon is referring to the concept that Norvig calls “naked twins.” As Norvig points out, there are many such strategies, they require lots of code, and they don’t bring much to the party.

    As is often the case, however, you are confusing the destination with the journey.

    Try KenKen next….

    Reply
    1. alecm

      Excellent article – glad I didn’t read it beforehand, though.

      http://www.kenken.com/ ? seems to require some representation…

      Reply
  5. Poul-Henning Kamp

    WRT doing OCR: You have seen the guy who did a Lego Mindstorms robot which first does OCR, then solves, then prints the solution with a pen ?

    Reply
    1. alecm

      Link?

      Reply
  6. Peter Jenkins

    You know Google goggles does this including the OCR right?

    Reply
    1. alecm

      No I didn’t, but then my discussion with Nigel dates from when we were all working for Sun, so probably 2007-era…

      Reply
  7. Ebeneezer Smooge

    I believe that the Soduku’s are like many crossword puzzles.. they are supposed to get progressively harder as the week goes. So the Sundays I believe are either the hardest or easiest depending on the paper :).

    Reply
  8. Dave Walker

    Apparently, a minimum of 17 pre-populated squares are necessary to solve a Sudoku uniquely: http://www.bbc.co.uk/news/magazine-20801504

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

More posts