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,
Thursday, July 08, 2010
Sudoku Solver
Subscribe to:
Post Comments (Atom)
16 people have spouted off:
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
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.
Why is there an empty button on the dialog that sets the box value?
I entered today's easy NY Times puzzle to test the app. My reaction: "Wow, that's fast!" :D
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.
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.
Your roller coaster analogy is bullshit.
Although, programming a robot to enjoy roller coasters would be quite a challenge.
Probably something to do with probability could possibly work in place of guessing. But that's just a guess.
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/
but the idea is to see if I can come up with the algorithms myself as a challenge/test of my programming ability.
Spout off: