Brief instructions:
To watch the program solve a puzzle, click "Solve." You can enter new puzzles by typing numbers in the text box and clicking "update." I recommend going to websudoku.com, copying a hard puzzle, and cheating to get a fast time.
Future updates include (if I don't get too lazy):
- The program doesn't validate the initial state, so you can enter an obviously unsolveable puzzle and it will waste a fair amount of time trying to solve it. This is my top priority for a fix.
- I'd like to be able to click directly on the image and be able to type in numbers there.
- No guarantees, but you might be able to paste a websudoku.com URL and have it automatically load the puzzle from there.
- Kevin, the director of engineering, discussed some methods to automatically generate new puzzles. I might give that a try. But it's a solver, not a game, so I might not.
One of the reasons people switched to dancing links was the significant speed increase. Realizing this made me stop making mine as it makes backtracking look like an epic waste of time (*sniff*). Also try a puzzle like the following:
ReplyDelete1 5
3
2 4
34 7
2 6 1
2 5
7 3
1
You'll notice that it takes a pretty long period of time. Also, this puzzle has two solutions as it lacks an 8 or 9 in the puzzle itself.
Checking the initial state is exactly like checking any other state. If you are only checking the important contradictions when you add a number then I recommend that you add the puzzle itself into the checker. If the puzzle ever wants to backtrack out of the original puzzle, then there is no solution. This will cover the case of initially setting up the puzzle and the case of a puzzle having no solution.
Done writing this comment and the solver is still working on that puzzle.
I don't know what speed you had it set to, but there is a selection box that sets the speed. The fastest speed does a sleep of 1 MS between each step. Another improvement I forgot to suggest is making a "max" speed where it only sleeps once every 1000 steps or so. It was working in an earlier version, but then I changed the algorithm and haven't yet added the move counter back in. Anyway, if you set it to the current top speed, it will finish in a minute or so.
ReplyDeleteAlso I wanted to display the number of moves and the status. That's the next thing I plan to fix after initial state validation. My best time on a puzzle that was considered really hard was something like 43,000 moves (backtracking is not counted as moving). I have some plans to improve the algorithm, but once I add the max speed link, it should be fast enough to solve anything in what "looks like" almost no time. I was more interested in the visuals than perfecting the efficiency, but there's time to get to that later.
Updated; see edit at the bottom of original post.
ReplyDelete