[>]

Blog » Soduku solver

15 Jul 2005

Soduku solver

Filed under: Stuff — paulcook @ 2:03 am

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.



« Previous post in category Next post in category »

79 Comments »

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

    Awesome job, Paul. Very well done.

    Comment by jjk — 15 Jul 2005 @ 10:12 am

  2. Thanks, jjk! It’s an interesting little problem to solve!

    Comment by paulcook — 15 Jul 2005 @ 11:10 am

  3. Oh nos! Infinite recursion!

    Comment by MDA — 15 Jul 2005 @ 11:31 am

  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.

    Comment by paulcook — 15 Jul 2005 @ 3:02 pm

  5. You guys need to drink more.

    Comment by Adam — 16 Jul 2005 @ 1:13 am

  6. Any chance of seeing the code? :)

    Comment by Paul F — 16 Jul 2005 @ 5:35 pm

  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.

    Comment by suavisimo — 17 Jul 2005 @ 7:59 pm

  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

    Comment by Mike Stall — 10 Aug 2005 @ 8:47 am

  9. so what is the 3rd rule ?

    Comment by stevenf — 13 Aug 2005 @ 8:26 pm

  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.

    Comment by paulcook — 26 Sep 2005 @ 1:16 am

  11. Thats pretty cool. Its temptng to use…Why must you torment me :)

    Comment by Melinda — 8 Oct 2005 @ 3:33 am

  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.

    Comment by paulcook — 11 Oct 2005 @ 12:11 pm

  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 :)

    Comment by Blandi — 11 Oct 2005 @ 4:31 pm

  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.

    Comment by paulcook — 11 Oct 2005 @ 5:25 pm

  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

    Comment by Bill — 13 Oct 2005 @ 9:40 am

  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.

    Comment by Stephen — 14 Oct 2005 @ 12:12 pm

  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!

    Comment by paulcook — 15 Oct 2005 @ 12:42 pm

  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…

    Comment by Stephen — 17 Oct 2005 @ 6:58 pm

  19. This is phun.I like!

    Comment by goofy guy — 8 Nov 2005 @ 8:25 am

  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.

    Comment by Peter — 16 Nov 2005 @ 10:25 am

  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.

    Comment by Denny — 8 Dec 2005 @ 9:29 pm

  22. yea… dont know what with the smiley face. it shoulda been ( 9 tab tab 8 )

    Comment by Denny — 8 Dec 2005 @ 9:30 pm

  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.

    Comment by HurP — 10 Dec 2005 @ 6:08 pm

  24. Did you try to generate sudoku problem ? I think it can be very usefull.

    Comment by Ujin — 21 Dec 2005 @ 8:00 am

  25. Great puzzle solver thx :D

    Comment by cj — 2 Jan 2006 @ 8:13 pm

  26. I wrote a solver in APL. Using recursion, it works out to a simple and brief 12 liner.

    Comment by Lance — 4 Jan 2006 @ 8:22 am

  27. 5678_886_7878_6426_67968_57468_

    Comment by Anonymous — 4 Jan 2006 @ 1:21 pm

  28. i want the code for sudoku in java

    Comment by chola — 5 Jan 2006 @ 10:32 am

  29. [...] I repay him for his generous hosting? Simple, try to follow along. I link to Paul’s soduku solver. Paul’s page rank for “sodoku” misspelled as “soduku&#822 [...]

    Pingback by Apparent Horizons » Blog Archive » Paying the bills — 1 Feb 2006 @ 11:06 am

  30. This solver is going far over my head. :-)

    Comment by blubbie — 1 Feb 2006 @ 4:49 pm

  31. [...] 71.3 million The “correct” spelling, if you believe there is such a thing. soduku 750,000 Paul is in good [...]

    Pingback by Apparent Horizons » Blog Archive » Moore suduku mispelling phun — 27 Feb 2006 @ 9:31 pm

  32. Here is a program i made recently, it solved any Soduku puzzle I could find to throw at it, very quickly as well, it would be great if some of you Soduku lovers out there could test it for me and let me know what you think of it :)

    You can download it at
    http://home.exetel.com.au/amurgshere/soduku.phtml

    Comment by TheToid — 3 Mar 2006 @ 4:42 am

  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

    Comment by Josh — 10 Apr 2006 @ 9:15 pm

  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!

    Comment by paulcook — 10 Apr 2006 @ 9:26 pm

  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?

    Comment by Paul Etner — 29 Apr 2006 @ 5:05 pm

  36. yall are fuckin dweebs

    Comment by bob — 9 May 2006 @ 4:19 pm

  37. yall need a girlfreind. or sum lotion

    Comment by bob — 9 May 2006 @ 4:20 pm

  38. Check and check.

    Booya Bob!

    Comment by jjk — 9 May 2006 @ 5:09 pm

  39. 003008610
    000003080
    000500007
    058000104
    001305900
    609000570
    100009000
    080700001
    024100700

    please solve!

    Comment by amanda — 18 May 2006 @ 9:15 am

  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

    Comment by jjk — 18 May 2006 @ 10:16 am

  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

    Comment by jjk — 18 May 2006 @ 10:18 am

  42. Thanks Jeff! I’m back in the country now, so should start catching up the backlog of posts soon!

    Comment by paulcook — 18 May 2006 @ 2:50 pm

  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!

    Comment by Jon — 22 Aug 2006 @ 6:29 pm

  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

    Comment by Amit — 3 Sep 2006 @ 9:54 pm

  45. I’m afraid I don’t understand the question. Sorry.

    Comment by paulcook — 5 Sep 2006 @ 10:22 am

  46. my math teacher gives us extra credit if we do these thanx for making this

    Comment by zach — 3 Oct 2006 @ 4:20 pm

  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.

    Comment by gridrat — 17 Oct 2006 @ 5:11 am

  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…

    Comment by Anne — 14 Nov 2006 @ 11:01 pm

  49. hello ,
    please can you send me the sorce code for what steps you hava given for doing the project.

    Comment by sona — 15 Dec 2006 @ 5:16 am

  50. Hey!!! Thank you so much for this solver!!! I had some extra credit sodukus in math and this puzzle solver works magic!!!

    Comment by Krazy8s — 10 Jan 2007 @ 7:53 pm

  51. Sure! I’m pleased it helped you scam your maths class!

    Comment by paulcook — 11 Jan 2007 @ 1:12 pm

  52. Hmm… I tried with a super hard soduku and the results just came out and here i am cracking my brains to solve it.

    ;-)

    Comment by Niz — 13 Mar 2007 @ 5:57 pm

  53. 200308007
    100000005
    400759006
    809000504
    020000083
    304080709
    902845001
    500000002
    000102058

    Comment by alyssa — 6 Apr 2007 @ 6:02 am

  54. plese help me find this i have been tring to find this onefor 2 weeks

    Comment by alyssa — 6 Apr 2007 @ 6:03 am

  55. Hi Alyssa,

    You can just put the problem into my solver, following the link at the top of the page, and it’ll solve it for you. I actually just did so, and got:

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

    Comment by paulcook — 6 Apr 2007 @ 11:26 am

  56. I have a little Neopets help site and Neopets created the game Roodoku which is their version of Sudoku. I was hoping to find a free script that I could host myself for my visitors to use to solve the puzzles for them. I found the source code to this, but I’m not a programmer and can’t get it to work. :(

    I’ve seen the online version though, and it’s a blessing!

    Comment by Lindsey — 21 May 2007 @ 8:52 pm

  57. This puzzle won’t solve because it times out with Firefox. Any suggestions?
    –9 –6 4–
    –3 — -7-
    -2- -8- —
    1– 5– –6
    -8- 2– -3-
    7– — –9
    — -4- -8-
    -5- — 1–
    –6 9– 2–
    Thanks,
    Bob E

    Comment by Anonymous — 2 Jul 2007 @ 3:43 pm

  58. Unfortunately, there seem to be a few puzzles for which my algorithm is not ideal — in technical terms, it needs to do the “bound” part of the branch and bound algorithm sooner. I’ve thought of a few ways to achieve this … and then ran out of energy. Sorry. But it works for nearly all other puzzles.

    Comment by paulcook — 25 Jul 2007 @ 3:12 pm

  59. Why when I enter my numbers and hit solve, does it timeout?

    Comment by t Chester — 24 Aug 2007 @ 11:35 am

  60. See above comment.

    Comment by paulcook — 31 Aug 2007 @ 2:57 pm

  61. I test this.Great.
    2**1*7***
    7*5******
    *84****15
    6**9*****
    *28*6419*
    ****8***3
    ****41**6
    ******9*1
    16****47*

    Comment by Yulihua — 30 Oct 2007 @ 3:02 am

  62. Any idea where I can find an efficient java source code for soduko?

    Comment by jabbz — 26 Nov 2007 @ 12:58 am

  63. Nope, sorry — you could of course re-code mine, but it’s actually not very efficient in its current form, it prunes the branches a little late.

    Comment by paulcook — 26 Nov 2007 @ 1:06 am

  64. …quick question not related to the sudoku but rather to php, are there any php video tutorials/awesome php books that you may recommend to someone who’s good at programming in java?

    Comment by jabbz — 5 Dec 2007 @ 11:16 pm

  65. Cud u pls give the source code of the Sudoku game & the Sudoku solver in Java

    Comment by Ragini — 7 Sep 2008 @ 6:36 pm

  66. Cud u pls give the source code of the Sudoku game & the Sudoku solver in Java

    Comment by Ragini — 7 Sep 2008 @ 6:36 pm

  67. There’s a link at the bottom of the post to the source code in PHP. Translation to Java should be easy enough!

    Comment by paulcook — 8 Sep 2008 @ 11:15 pm

  68. Hi
    I’ve found another run timeout error
    on the f_1_1_1 put value=2
    then f_8_9_9 put value=2 too

    It leads me to error.. would you explain or fix it?

    Thanks

    Comment by angelia_chai — 11 Feb 2009 @ 8:19 pm

  69. Not working as it did before

    Comment by John — 23 Jun 2010 @ 3:25 am

  70. I drop a comment when I especially enjoy a post on a
    site or I have something to add to the discussion. It is
    a result of the fire displayed in the post I looked at.

    And after this post Langabi.name Soduku solver. I was actually excited enough to leave a thought :-)
    I do have a couple of questions for you if you do not mind.
    Is it simply me or does it look like a few of these remarks look as if they are written by brain dead individuals?
    :-P And, if you are posting at other online sites, I would like
    to keep up with you. Would you make a list all of your shared sites like your linkedin profile, Facebook page or twitter feed?

    Comment by Edwardo — 9 Sep 2012 @ 5:32 pm

  71. You’re really a good webmaster. The website loading pace is amazing. It kind of feels that you’re doing any distinctive trick. Moreover, The contents are masterwork. you have done a wonderful task in this matter!

    Comment by free black sex ebony amateur sextape blackpornamateurporn — 14 Jun 2013 @ 10:56 am

  72. Hey there, You have done an incredible job. I will certainly digg it
    and personally suggest to my friends. I am confident they’ll be benefited from this web site.

    Also visit my web site … Breville BJE200XL

    Comment by Jeanne — 10 Jul 2013 @ 6:40 am

  73. Yes! Finally someone writes about celebs :: Gwen ::.

    Comment by Gwen — 20 Jul 2013 @ 5:24 am

  74. Heya this is kinda of off topiс but Ι ωas
    wanting to know if blogs use WYSIWYG еditοrs or if уou havе to manuallу code with HТML.
    I’m starting a blog soon but have no coding experience so I wanted to get advice from someone with experience. Any help would be greatly appreciated!

    Also visit my website … Guarantor Loans

    Comment by Ulrich — 20 Jul 2013 @ 11:23 pm

  75. Wow that was odd. I just wrote an really long comment but after I clicked submit my comment didn’t appear. Sucks! Anyways, just wanted to say great blog!
    My spouse and I often write guest articles or blog posts for other web site owners to help gain publicity to our work, as well as provide terrific content to blog owners. It really is a win win situation! If you are interested feel free to contact me so we can talk further. Thank you!

    Keep up-to-date and visit my web-site at K53 learners test for even more know-how.

    Comment by Jacelyn — 7 Aug 2013 @ 5:10 am

  76. Wonderful website you have here, but I was wanting to
    know if you knew of any forums that cover the same
    topics talked about in this article?
    I’d really love to be a part of online community where I can get advice from other knowledgeable people that share the same interest. If you have any recommendations, please let me know.
    Kudos!

    More to follow on my web page fleet management

    Comment by Cristina — 17 Aug 2013 @ 12:12 am

  77. What’s up colleagues, its enormous article about tutoringand entirely explained, keep it up all the time.

    my blog: jorve roofing (Hyman)

    Comment by Hyman — 26 Aug 2013 @ 8:42 am

  78. Great website. Plenty of useful info here. I’m sending it to some buddies ans
    also sharing in delicious. And of course, thanks on your sweat!

    my site :: Goodgame Empire Cheats

    Comment by Elizabeth — 3 Oct 2013 @ 8:19 pm

  79. Как сделать минусовку (вырезать слова) из песни | Блог Симонова . сделать минус онлайн, и в некоторых случаях он действительно.
    bulgari bracciale imitazione prezzo http://www.venditagioielli.ru/cheap-copy-bvlgari-serpenti-bracelet-18k-pink-gold-with-demi-pave-diamonds-p72.html

    Comment by bulgari bracciale imitazione prezzo — 30 Nov 2017 @ 5:50 am

RSS feed for comments on this post. TrackBack URL

Leave a comment

Line and paragraph breaks are automatic. You can use the following HTML tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <img src="">