Zorac (zorac) wrote,
Zorac
zorac

Sudoku

Ages ago, I started coding up a perl-based sudoku solver and managed to get it solving lots of puzzles with only a very basic set of rules for solving them. Recently, alnitak (who is also writing a solver, this time in java) showed me a really nasty puzzle which neither of our solvers could completed (although a human could spot the next step). After some discussions we came up with a new solving rule, which I've implemented in my code and now allows me to solve the puzzle.

Anyway, what I'm looking for is some truly evil sudokus to test my solver with, so if you've got any nasty ones that you can send me, that would be much appreciated.

+---+---+---+
|738|.1.|.9.|
|.9.|5..|74.|
|..4|...|...|
+---+---+---+
|64.|28.|3..|
|...|...|...|
|..2|.95|.87|
+---+---+---+
|...|...|1..|
|.87|..2|.3.|
|.5.|.6.|279|
+---+---+---+
Tags: geekery, puzzles
Subscribe

  • RIP shirts

    So, this evening I did the first batch of laundry in the shiny new washer-dryer in my shiny new kitchen. It killed two of my favourite T-shirts. The…

  • That's Mister Bananabeak to you, Fuzzy!

    No TTT EE today :(( Am consoling myself with the fact that I got it really, really cheap. Or, will have got it really, really cheap if/when it…

  • D00med

    Some days it really isn't worth getting out of bed. Or maybe it's the not getting out of bed until after midday part that's the problem. Either way,…

  • Post a new comment

    Error

    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    switch
    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    Help
  • 11 comments

chrisvenus

January 20 2006, 14:03:01 UTC 15 years ago

Would it be rude to ask what your rules are? I've not done many sudokus but would be interested in seeing how you'd code up a a solver.

zorac

January 20 2006, 14:17:31 UTC 15 years ago

OK, firstly the solver maintains a full set of pencilmarks for each cell, and for each group (row, column or box), and then applies these rules in order:
  1. Look for cells with only one pencilmark in. Put that number in. (This one alone is sufficient to solve the 9x9x9 so-called Dion Cube).
  2. Look for pencilmarks which appear in only one cell of a group. Put the number in that cell (these first two rules solve pretty much all 'Easy' and most 'Medium' difficulty puzzles).
  3. Look for n cells in a group containing exactly the same n pencilmarks. Remove those pencilmarks from all other cells in the group. (Adding this solves most 'Difficult' puzzles).
  4. Look for pairs, triples etc - eg two pencilmarks, both of which appear in exactly the same two cells within a group. Remove all other pencilmarks from those cells. (I'm not sure if this one is actually needed).
  5. Consider intersections - on a standard 9x9 sudoku board, this will be groups of three cells which appear in the same box and row/column. If those three cells are the only ones in a box which contain a give pencilmark, remove that pencilmark from all the other cells in the corresponding row/column, or vice-versa. (This is the one which cracked the really hard puzzle).
That may not be terribly clear, but it's probably the best I can manage without resorting to diagrams and/or psuedo-code.

chrisvenus

January 20 2006, 15:00:46 UTC 15 years ago

I understand the first three. I'm a little fuzzy on the other two but I suspect its not worth diagrams and stuff. I have vaguely worked out the first 3 I think. I did have a puzzle I couldn't solve so may have been sufficient. Unfortunately it was just one I had in the paper and I don't have it any more so it doesn't help. Its also possible that I applied rules one to three worse than a computer would. :)

I've certainly found online places that offer different difficulty levels of puzzles. Try for example "Solo" from Simon Tatham's Portable puzzle collection (http://www.chiark.greenend.org.uk/~sgtatham/puzzles/). That allows you to create "unreasonable" difficulty solutions which may be able to tax your puzzle. Its possible you could ask nicely and get the code to generate the puzzles and then connect your two programs up to just run continuous tests to try to solve things it comes up with.

imc

January 20 2006, 14:16:43 UTC 15 years ago

There was a truly evil sudoku a while back which appears to require a trial-and-error for the solution.

zorac

January 20 2006, 14:28:56 UTC 15 years ago

Hmm. My solver gets stuck at the same point as everyone else. If it really can only be solved by trial and error from that point, then it's a faulty puzzle (although, it should be possible to code up a solver which can do trail and error, backtracking where needs be). Clearly it bears further investigation...

imc

January 20 2006, 23:55:07 UTC 15 years ago

Faulty puzzle? Or just a fiendish puzzle?

Surely any sudoku with a unique solution cannot be considered faulty.

zorac

January 21 2006, 01:42:05 UTC 15 years ago

Hmmm. Possibly not faulty, but a properly constructed soduku ought to be solvable purely by logical deduction without trial and error - although what constitutes higher-level trial and error and what is logical deduction is a rather open question...

Anonymous

January 20 2006, 15:11:29 UTC 15 years ago

You will find some truly evil sudoku puzzles at my site Fiendish Sudoku (http://www.fiendishsudoku.com/).

Based on your description above, the hardest two of the five levels will defeat your solver. But all the puzzles on the site are solvable with pure logic, as you will see if you use the Solve Step feature (which offers a terse explanation).

To get the puzzles to your solver without typing the starting digits, use the Permalink link (lower right of the Fiendish Sudoku grid) to copy the puzzles to the clipboard.

- Rob

zorac

January 20 2006, 16:12:20 UTC 15 years ago

I could solve today's Evil one, but not the Fiendish. It looks like I'll need to code up X-Wings and the like. Thanks for that!

sophie10

January 20 2006, 16:25:47 UTC 15 years ago

You updated!

*is in awe of the power of the nudge*

zorac

January 20 2006, 17:13:22 UTC 15 years ago

Well, it's more the pestering power of the frayer...

  • RIP shirts

    So, this evening I did the first batch of laundry in the shiny new washer-dryer in my shiny new kitchen. It killed two of my favourite T-shirts. The…

  • That's Mister Bananabeak to you, Fuzzy!

    No TTT EE today :(( Am consoling myself with the fact that I got it really, really cheap. Or, will have got it really, really cheap if/when it…

  • D00med

    Some days it really isn't worth getting out of bed. Or maybe it's the not getting out of bed until after midday part that's the problem. Either way,…