Sudoku solver

When visiting family last week, the conversation turned to Sudoku puzzles and how to solve them through software (I know, it’s sad :) ). My initial impression was that it shouldn’t be too hard to write a program that fills in the missing numbers but, as so often, I now stand corrected.

My first attempt was to write a program that does the following:

  1. Pick a 3×3 box of numbers
  2. See which numbers are missing
  3. For each of these, check the number of possible positions
  4. If it fits in only one position, fill it in

While this worked for some Sudokus I soon realized I needed to also pick columns and rows in step 1. That helped. It then worked great on easy to medium puzzles but failed for Sudokus that require some thinking ahead. Determined I wasn’t going to write a chess-like program, I was just about give up when I realized that instead of checking for a single possible position, I could do educated guesses with numbers that fit in two spots. So this is what the current version does.

  1. Pick a 3×3 box, column of row
  2. See which numbers are missing in those 9 positions
  3. For each of these, check the number of possible positions
  4. If it fits in only one position, fill it in
  5. If that does not happen for a reasonable period of time, go into guessing mode and guess a number with two possible position
  6. If the process stalls again, delete all uncertain numbers and go back to step 5

This is how a third incarnation of my little Flash movie came to be, and it now solves pretty much all of the Sudokus I found online, labelled as ‘hard’ or ‘very hard’. As an application it’s still a little rough around the edges. You should see this as more of a proof of concept kind of thing. It is also built so you can see the progress and for low CPU utilization, it’s not at all optimized for speed. Therefore, it can take quite some time to solve difficult puzzles. Nevertheless, if you feel like playing with it, please feel free:

Black numbers are given, blue ones are deduced through logic, red ones are guessed and gray ones are results based on those guesses. Please do not try to edit the puzzle whilst solving, that will almost certainly result in weird behavior.

I realize there are tons of Sudoku solvers out there, almost all of which are better than mine. Please keep in mind that I made this because I wanted to see not if it could be done but whether or not I could do it…

20 Comments

  1. I was thinking about creating a sudoku website, and this would be great. :P

    One thing I noticed though,
    The black numbers are given numbers,
    but clicking them will remove them.

    so i I click them all, and leave an empty screen, your script just keeps running itself endlessly. :P

    Comment by Paul — November 8, 2008 @ 1:40 am

  2. Hi Paul. That’s why there’s also a ‘restore’ button. Once you click on a number you can then type a new one. This allows you to try and solve any puzzle you might have.

    The demo puzzle is very tricky, I chose it because the first two versions were unable to crack it, and it became my target for version three to be able to solve it. Pretty much every number you take out will make it impossible,

    Comment by Roy — November 8, 2008 @ 9:31 pm

  3. Nicely done :)

    I recall there was an article recently on Slashdot (and elsewhere) on how to use Debians apt-get to solve Sudokus =)

    Comment by phrozen77 — November 12, 2008 @ 2:37 am

  4. got here from redkinoko’s site ^^

    Nice Sudoku Solver.. Can I take a peek at the code? ^^ I know, the algortihm’s already there, maybe I can improve upon your code though..

    btw, I tried to enter an set of numbers given by my Math Major friend: http://i79.photobucket.com/albums/j123/Kadaj13_photos/Sudoku-Unsolvable.jpg (Screenshot). I let it run until 240,000+ ^^

    Comment by LantisGaius — November 12, 2008 @ 3:48 am

  5. Hi LantisGaius. Please contact me by email about the source code. I’ll be happy to email you a copy as long as you don’t spread it around.

    And yeah, it does not solve unsolvable puzzles… in fact he algorithm is weak compared to others floating around on the web. But then it only took a few hours to make…

    Comment by Roy — November 13, 2008 @ 10:07 am

  6. Hi, I was wondering if you can pass me the source code 2. I made my first Sudoku solver and generator in C++, and Im trying to lear Java and Actionscript, cause well C++ is very old, but it is the programing languaje I know (for now). Thanks

    Comment by Adolfo Fallas Zuñiga — November 23, 2008 @ 4:08 am

  7. During my free time I always play Sudoku on my phone. At first I was having a hard time playing it but later on it gets so easy. I love Sudoku game.

    Comment by Erich "Recruiters" Jam — December 3, 2008 @ 2:07 am

  8. I still think that solving Sudoku using computers, with procedural programming is easy.

    Try putting that to Prolog and you will find what’s hell on earth :D

    Comment by Dancing Squaregay — December 12, 2008 @ 3:44 pm

  9. hi there..
    i was wondering if you could send me the .fla..

    i just want to use it to learn.

    tks

    Comment by ricardo reis — January 5, 2009 @ 4:58 am

  10. Hi Roy, please can i take look at the source , im really curious how it looks and i wont spread it around. Was it written in c++??

    Comment by Rapheal — March 17, 2009 @ 10:35 am

  11. my email is rapheal2k6@yahoo.com

    Comment by Rapheal — March 17, 2009 @ 10:37 am

  12. NICE WORK!

    please email me the source for the sudoku solver i just wanna see the algorithm

    i will not spread it around

    10x

    Comment by ghedeon — March 17, 2009 @ 3:10 pm

  13. cool~ but seemed still cannot solve all puzzles. there may be some bugs in the traversal.
    and at least, as an algorithm, it should have an ending.

    sample:
    xxxxx86xx
    xxxx2xxxx
    42xxxxxx3
    9xx1xxxxx
    x463xxxx1
    xxxxx4x9x
    7xxxxxxxx
    xxxx715x2
    x5xxx3x64

    solution:
    519438627
    367925418
    428617953
    975182346
    246359871
    183764295
    732546189
    694871532
    851293764

    Comment by lingyi — March 20, 2009 @ 5:02 pm

  14. I am sincerely impressed. :)
    Even the easy games take a while to work out, though I am getting a little better nowdays.

    The best technique is to use a pencil and paper and lots of practise ! You tend to get sharper each time you do one, though a good 10 minute break between puzzles is a wise move too :)

    Though having an automated Sudoku solver like this one handy could help win a few contests to I guess !

    Comment by Online Word Games (Sudoku) — June 10, 2009 @ 3:31 pm

  15. You might want to add one more check before guessing.

    For each empty slot, check to see what numbers can fit in possibly, and if the possibilities limit to 1, then fill it in.

    Comment by Abhishek — September 2, 2009 @ 9:17 am

  16. Hi Roy,
    this tool il so nice !
    (first, sorry for my english, i’m french :))
    can I put this swf tool on my game blog ? with a roytanck.com link of course !

    Have an happy new year …
    Forro, from gamelogical.com

    Comment by Forro — January 3, 2010 @ 12:23 pm

    • Hi Forro. Yes you can. It’s not open source or anything, but since it’s just an experiment I have no interest in exploiting it commercially. A link would indeed be appreciated.

      Comment by Roy — January 6, 2010 @ 11:42 am

  17. Hi !
    this is it .. (?)
    Article with your solver is posted : http://www.gamelogical.com/article-resoudre-un-sudoku-45083637.html

    (design of the blog is not fixed… i’m in progress :))

    Thanks a lot, again and again :)

    Forro, from gamelogical !

    Comment by Forro — February 16, 2010 @ 8:33 pm

  18. Wow, thats really nice. What programming language did you use to build it?

    With Firebug, I see that it is Flash, but surely the brains of it isn’t flash? I could be wrong because Im more of a beginning programmer.

    Awesome nonetheless.

    Comment by DownloadSudoku.org — July 25, 2010 @ 9:08 pm

    • Yes, it is Flash. AS3 is a pretty advanced programming language these days. :)

      Comment by Roy — August 4, 2010 @ 11:35 am