Soduku solver

Stuff 1 Minute

Soduku (Sudoku) is a Japanese number puzzle game that seems to be taking the world by storm. It’s played on a 9×9 grid. Each square can contain one of the numbers from 1 to 9 (inclusive). A given “problem” has some of the squares filled in, and you are required to fill in the remaining squares, satisfying the constraints:

  • Each row has to contain each of the numbers 1 through 9 exactly once.
  • Likewise for each column.
  • The board can be broken down into 9 3×3 squares (top-left, top-middle, top-right, etc.). Each of these has to contain each of the numbers 1 through 9 exactly once.

Anyway, these puzzles can get pretty tricky. Especially if you don’t know the third rule above — which until recently, I didn’t. Anyway, they’ve sufficient annoyed me now that I had to do something about it; so I wrote

The Langabi.name Soduku Solver

It’s not fancy, but is (in my opinion) very efficient. Enjoy!

Edit: Now available: an explanation of the method my solver uses, and the source code.

Unknown's avatar

Published by Paul Cook

Published

69 thoughts on “Soduku solver”

  1. I just tried out one example online that had a given solution. Your solver matched it exactly.

    Awesome job, Paul. Very well done.

    Like

  4. UPDATE: GV found a class of (unsolvable) problems that break my solver. I’ve enhanced my solver to detect those sorts of solutions as unsolvable, and dramatically improved its efficiency more generally.

    Then MDA adapted GV’s problems to invent another class of (unsolvable) problems that the solver doesn’t recognise as unsolvable. Fix pending.

    Like

  7. a coding challenge, if you choose to accept it: write a doublet solver. this site has more about doublets . Your program should be able to take in two words of equal length and output the optimal answer.

    my friend and I had a code-off my senior year of college. the rules, write a doublet-solver in the amount of time it takes to listen to Mozart’s Don Giovanni. neither of us came up with the optimal solution, which I stumbled upon theoretically a few days later. I never implemented it though.

    Like

  8. Wow, pretty cool. I was thinking about writing one of these but thought I’d google it first. I guess not much point now…
    I’m curious: how much of this problem was a brute force search vs. intelligent algorithms?

    Mike

    Like

  10. The third rule is the rule mentioned third above: that is, the one about how each 3×3 susection also has to have the numbers 1 through 9 exactly once.

    Like

  12. News: I’ve finally summoned up the time to clean up and make available the source code, and a brief explanation, of the solver. See the link at the bottom of the post above.

    Like

  13. Is the spelling “Soduku” a typo or can one really say “Soduku” instead of “Sudoku” ? Google finds 9 Million Sudokus and about 57k Sodukus 🙂

    Like

  14. Well done, you found me out. When first I was looking for the spelling of Sudoku, I tried Soduku and found lots of hits. So without further thought, I used that. However, the correct spelling is, I suspect, Sudoku. Now, however, most of the hits to this post come from people who also mispell the word, so I’m reluctant to entirely change over.

    Like

  15. your “solver” did not have a solution for this one–i worked it out by hand. Starting
    upper left corner by rows: 5–4—9- then 2nd row–and so on,
    37—6–1
    –8——
    4–9–8–
    831—579
    –5–7–4
    ——7–
    6–3—42
    -4—2–8

    Like

  16. Yes, as said by Bill, your solver seems to have a flaw. I input several puzzles from my paper’s Soduku puzzle, and your solver failed to find a solution to 9/10 of them, even though none were terribly difficult.

    Like

  17. Thanks for the comments — when I was commenting and cleaning up the source code a few days ago, so as to be able to post it on this site, I introduced a small typo in some of the code. Then it seems my test example happened to be one of the few examples that were still solvable, so indeed it has been broken for the last few days.

    Well, I’ve now fixed the mistake, and so the solver should be working at full strength again. Thanks again!

    Like

  18. Seems to be solving okay now, but having problems w/ more complex problems

    Trying to solve this:

    0 0 0 0 1 0 7 0 0
    0 0 0 0 3 0 0 0 5
    0 0 0 8 9 0 0 0 0
    3 2 0 0 0 0 5 0 0
    0 0 6 0 0 0 2 0 0
    0 0 8 0 0 0 0 9 0
    0 0 0 0 2 0 0 0 0
    9 0 0 0 7 0 0 0 1

    0 0 1 4 6 0 0 7 0

    and it times out. Proggy I wrote in C solves it in about 200ms…

    Like

  20. It would be a nice touch if the HTML grid on the input page showed the 3×3 blocks graphically – it would make it easier to transcribe puzzles from books/newspapers etc onto the screen without having to count columns and rows.

    Like

  21. To type it in from a paper graph its much quicker if you go from top-left row then press tab once more then the spaces between them so 908 would be ( 9 tab tab 8) and then on. Works great. Nice work man.

    Like

  23. An amazingly trivial and simple puzzle requiring no insight and nearly no thought, just methodicalness. And this is the new rage! What a very very sad comment on what our intellect has degraded to. I can see why this is supplanting crossword puzzles, however. Probably a real sense of accomplishment for the “Wheel of Fortune” crowd.

    Like

  29. Pingback: Apparent Horizons » Blog Archive » Paying the bills
  31. Pingback: Apparent Horizons » Blog Archive » Moore suduku mispelling phun

  33. You really have a intresting program here, but i found the most intresting outcome was when I put one number in the center square. ie a problem looked like this:

    0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0
    0 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0

    A problem like this should have many possible answers but your program gave me a single set answer, why is this? The only change between answer mats when i changed the center number were certain key number changes (in a some what predictable manner.)

    Can you explain this?
    Thank you

    Like

  34. There are indeed many solutions to your problem. However, my program is designed to find a solution, not ALL solutions. So as soon as it finds a solution, it stops and outputs that solution.

    Furthermore, since there is no randomness in the program, the same solution will be found each time.

    Thanks for stopping by!

    Like

  35. this isn’t working for me. Each time I try I get a message that script time has run out. Could this be because I’m still using dial up?

    Like

  39. 003008610
    000003080
    000500007
    058000104
    001305900
    609000570
    100009000
    080700001
    024100700

    please solve!

    Like

  40. Amanda, just click on the link in the text of the above post that says “The Langabi.name Soduku Solver”. Then, enter the non-zero numbers in their correct positions in the table. All you have to do at that point is click “Submit”.

    I did that with your puzzle (assuming I didn’t make any typos), and this is the result the solver gave me:

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

    Like

  41. Whoops, I had a typo in the third line. I fixed that, so assuming no more typos, here is the result:

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

    Like

  43. Looks pretty good! I wrote a Sudoku Solver too. It is written in Java and it uses a backtracking algorithm with optimized guessing (It is very fast). It also tells if the sudoku has more than one solution. It is online and it is free. You’ll need the Java plugin installed in your browser. Envoy: Jon’s Sudoku Solver!

    Like

  44. one number in each column from 0 through 9.select even number from odd and odd number select from even.and hwo after even number play aodd number?Its Urgent

    Like

  47. Hey guys check out a fab new grid game i’ve just found called SHENDOKU. You can play with 2 or more friends which is great, theres a wide range of games to try and other bits and bobs too. http://www.shendoku.com. Let me know how you get on.

    Like

  48. Can you send me the code for this please? I’m fascinated…

    I swear I won’t tell what happened to the puzzle cover before the party…

    Like

Comments are closed.