Thursday, July 08, 2010

Sudoku Solver

I think I've learned enough Java to try to write a Sudoku solving applet.

The first step in running the solver will be setting the board. Click on a box to set it's value (right now, each click increments the value, later I might use a dialog to pick the value, but this is good enough for now)

UPDATE: I added a dialog to set a box value.

UPDATE2: It was a hell of a fight, but I managed to get the GUI to look pretty much how I want. I ended up having to draw the heavy dividing lines manually, so they don't quite re-size right.

UPDATE 3: Added functionality.

UPDATE 4: Changed the look a bit. The boxes now change color when manually set. Adding the advanced techniques is tougher than I thought. I may take some time. After hitting the "Solve" button, the dialog function changes. Instead of setting the box value, it allows you to change the restricted values (blue means value is restricted).

this is just the GUI. the "Solve" button does nothing yet.
The applet goes as far as it can with the very basic algorithm it uses.
It successfully solved the NYT Easy and Medium Sudokus for July 15, 2010.
It wasn't able to completely solve the Difficult one, but I have ideas for more advanced techniques to add, so it shouldn't be long. YAY!!!

Note: it doesn't error check (yet). If you enter an impossible sudoku, it will still try to solve it.

*** Removed. See post dated 7/23/2010 for sudoku solver applet. ***

"I am so smart! S-M-R-T... I mean S-M-A-R-T!"
</Homer>

Praise me! PRAISE ME!
</GIR>

Later,

16 people have spouted off:

John said...
If anyone cares, the basic algorithm is this:

1) scan the board, update restricted values for each box

2) look for boxes with only one value available - set those values

3) look for rows/columns/squares that only allow a given value in one box - set those values

4) repeat from (1) until no new values are set
7/15/10, 11:05 PM
John said...
If you can't see the board, you probably need the latest Java Plug-in to run this.
7/15/10, 11:56 PM
Jackie said...

Cool. I guess we now know that it require more than two rules and an update. I'll be sure to share this with Kyle.

Jackie said...

Why is there an empty button on the dialog that sets the box value?

Jackie said...

I entered today's easy NY Times puzzle to test the app. My reaction: "Wow, that's fast!" :D

tom said...

You should add a save-point feature and try both options when two values are available for a box/row/column/square. I think that would allow it to solve all but the most challenging boards.

John said...
the blank button is there so that if a value is entered by mistake, it can be removed.
7/16/10, 5:50 PM
John said...
Tom - I thought of that. I decided that I don't want to have it work by guessing. But I still may add that if all else fails.
7/16/10, 5:52 PM
Andy said...

Am I understanding the point right? You are trying to write a program to solve sudoku puzzles? I thought the whole point of sudoku was to exercise the mind and solve/prevent boredom, so a computer program that solves problems engineered and designed for the human mind to solve seems counterproductive to me. It would be like engineering a robot to ride roller-coasters. Sure it can be done, but roller-coasters are build specifically for humans to enjoy... but hey good luck in your endeavor.

John said...
Ok Andy. You come up with an algorithm. That exercises the mind, too. As for boredom, why do you think I'm doing this. This is way more interesting. Plus, if I solve a sudoku, I have nothing else to show for it. But doing this gives me experience programming, as well. (Which is kind of the point; I'm doing this as a Java learning exercise - see the first line of my post.)

Your roller coaster analogy is bullshit.

Although, programming a robot to enjoy roller coasters would be quite a challenge.
7/19/10, 5:54 PM
John said...
Oh yeah. I find the sudoku much less challenging now, too. I'm also likely to get bored and stop before finishing. Now that I've broken it down to a mindless algorithm, solving sudoku is just rote mechanics. I'm having a much harder (and more engaging) time trying to code that algorithm.
7/19/10, 6:01 PM
John said...
I know I said I didn't want it to work by guessing, but that is so very much simpler than trying to code all the advanced strategies that might be needed. Plus, I'm sure there are strategies I don't know. So, it will guess.
7/19/10, 7:22 PM
tom said...

Probably something to do with probability could possibly work in place of guessing. But that's just a guess.

John said...
Figuring probabilities would just make the guesses more educated. Still guessing, though. Anyway, why bother? I can't see it making any difference. Figuring the relative probabilities is probably more work than just straight guessing.
7/21/10, 4:04 PM
Kevin Coulombe said...

I had an assignment to do the fastest Sudoku solver and ended up using 4 strategies, along with standard guessing/backtracking. You may be able to use what I call rule #4 to reduce the amount of guessing your algorithm does.

Take a look at my blog post on the matter : http://www.byteauthor.com/2010/08/sudoku-solver/

John said...
Thanks, Kevin,

but the idea is to see if I can come up with the algorithms myself as a challenge/test of my programming ability.
8/10/10, 2:46 PM