Java Sudoku Solver

Jo has really been into Sudoku the past few months. Being the nerd that I am, I spent the past few weeks coding up a Sudoku solver that you can check out at http://www.ben61a.com/sudokusolver/. (If you’re not familiar with the game, read about it on its Wikipedia entry.) It has been, and continues to be, an interesting project because solving Sudoku turns out to be relatively complicated.

The first work item I completed was a fast solver. The solver first translates a Sudoku into an exact cover problem. It then uses the Dancing Links technique, originally suggested by Donald Knuth in this paper, to efficiently find all solutions to the exact cover problem. In the case of a well-formed Sudoku, there is only one solution. That exact cover solution is then translated back into a Sudoku solution grid.

Next, I used this Dancing Links solver to create a puzzle generator. This simple generator starts with a blank grid and adds a random digit to a random cell over and over. After each addition, I use the fast solver to see if there is only one solution; if so, then we have a new Sudoku. If there are no solutions, we have to backtrack because the last digit added messed up the puzzle. I used my puzzle generator to create 50,000 puzzles (it took about 8 hours or so because of the massive number of fast solves that are done).

Unfortunately, the nature of the algorithm used by the fast solver suffers two problems:

  1. It can’t give any clues as to how to solve a Sudoku in a stepwise, human-logic-based manner
  2. There is no way to judge difficulty aside from counting the number of hints given in the Sudoku

To remedy both problems, I wrote a new solver that uses human-logic-based solving techniques. Whereas the fast solver can solve any well-formed Sudoku, my new logic-based solver can only solve around 98% of puzzles since some require more advanced logic techniques that I just haven’t coded yet. These are the major solving techniques I have coded so far:

  • Singles
  • Naked Pairs
  • Locked Candidates
  • Naked Triples
  • Naked Quads
  • Hidden Pairs
  • X-Wings
  • Coloring

Based on the number of types of techniques a puzzle requires to be solved, I was now able to classify puzzles in an (admittedly) subjective manner:

  • Easy if the only technique required is Singles
  • Medium if the only techniques required are Singles, Naked Pairs, or Locked Candidates (and it’s not an Easy puzzle)
  • Hard if it’s not an Easy or Medium puzzle
  • Evil if my logic-based solver cannot solve it using any of its techniques

Surprisingly, 47739 of the 50000 generated puzzles (95.5%) were classified as Easy (only required Singles). That’s crazy! As for the rest, 755 were Medium, 493 were Hard, and 1013 were Evil.

Finally, I put a user interface on top of the logic-based solver and put it online as a Java applet, linked above. It’s really just a first blush at a UI, so I know there can be much improvement.

Anyway, I’d love to hear your impressions and feature ideas, so leave a comment!

Several notes:

  • Because of the sheer size of storing 50000 puzzles even just as strings, I made a decision to only include 250 Easy, 250 Medium, and 250 Hard puzzles in the applet. This means that when you click “Easy,” you will only be given a puzzle from a pool of 250 puzzles.
  • I’m thinking about porting my poker and Sudoku applets to Flash since no one uses Java =p. It looks like I’d need to buy some Adobe software to do that though (not to mention learning Flash), but it sounds fun. Look for that in the future.

16 thoughts on “Java Sudoku Solver

  1. prgmmer

    I usually solve my puzzles by doing the following. I check rows and columns for conflicting numbers and at the same time checking to see which boxes can actually hold those numbers generally pretty easy. Same with checking for last possibility (although even if there are two or three squares open in a row or column, you can sometimes rotate the final combination around and do a quick check for nakes? and get all three quite easily. Sometimes two, one, or of course nothing. It also works with boxes too.

    That is the human logic with which I use to solve the medium and easy puzzles quickly. Hard puzzles take much longer for me, and so I don’t have any particular set strategy on them. I think it’s still hard to teach “logic”. It’s more of something you figure out yourself. A computer can always do an extensive search correctly.

  2. jontsai

    impressive. i wrote sudoku solver once… I could never get the logic solver down.

    I was able to brute force it, though =)

  3. Gliska

    Решил добавить RSS и получать новости, мне лично понравилось, что написал автор

  4. Geshak

    Понравилась статья.Буду следить за комментами….

  5. Plovdiy

    Неплохая подборка в блоге, хорошо сделано, автору спс.

  6. Daheng

    неплохой ресурс, все полностью устроило. буду пользоваться дальше.

  7. Kevin Coulombe

    The coloring must have been pretty though to implement without guessing and recursion!

    But I’m more interested in your quick solver. I’m looking to compare the dancing links algorithm with my own backtracking with rules algorithm to see which actually solve faster. I chose not to go with the dancing links and I’m doubting my decision!

    My program never took more than 3 ms for any Sudoku problem I tried (on my netbook), but it’s impossible to compare without trying both on the same machine… Would you mind sending me the source so I can compare them?

    Here’s my blog post about my sudoku solver: http://www.byteauthor.com/2010/08/sudoku-solver/

    Thanks!

  8. elevat

    одесская компания ООО Позитив КС продает высококачественную продукцию ДКС и Electro House. электротехническая осветительная продукция – [+, +прожекторы|розетки|выключатели – . труба для прокладки кабеля и лотки металлические в городе Одесса по низким расценкам. Источник: http://elelife.com.ua/ – кабель-каналы

  9. xdozvat

    порнуха ролики на известном интернет-сайте для взрослых Xdoza. удобный поиск порно среди рубрик – БДСМ, большие сиськи, волосатые киски, куннилингус, милые девушки и игрушки. порнуха русская. Источник: http://xdoza.com/russkoe-porno/ – порно русских онлайн

Leave a Reply

Your email address will not be published.