Java Sudoku Solver and Wikipedia Exaggeration

Feeling like programming, I decided to work on another puzzle solver other than my Rubik’s Cube program. This time I decided to tackle Sodoku in Java instead. I used two stacks and a pure brute force method of solving. First off I made the grid with a simple 9×9 array, filled it with some test numbers. I used 0’s for unkowns. I created a pair object to store (x,y) values into the stacks, and then made two stacks. The program located all the unknowns, adds them as pairs to the first stack, and gets to work checking for legal values when told to solve. It starts at the first number, checks to see if it can be a 1, 2, 3, etc. When found it moves on. Once it reaches a number it can’t find, it goes back one and increases that number to the next legal one. It does this until the main stack is empty.

Most puzzles it can solve in less than a second, even the ones rated “evil”, but I decided to try and find hard ones for it. On Wikipedia I found the “Near worst case sudoku puzzle for brute force solver”, located below.

Solving this puzzle by brute-force requires a large number of iterations because it has a low number of clues (17), the top row has no clues at all, and the solution has “987654321” as its first row. Thus a brute-force solver will spend an enormous amount of time “counting” upward before it arrives at the final grid which satisfies the puzzle. If one iteration is defined as one attempt to place one value in one cell, then this puzzles requires 641,580,843 iterations to solve. These iterations do not include the work involved at each step to learn if each digit entered is valid or not (required for every iteration). Based on the specific construction of the computer code, programmers have found the solution time for this puzzle to be between 30 and 45 minutes with a computer processor running at 3 GHz.

“Perfect!” I thought to myself, and plugged it in, thinking it was time to go get a cup of coffee and read my latest Asimov novel for 30 minutes. However, before I even look away, my results pop up.

Solved puzzle below

9 8 7 |6 5 4 |3 2 1 |
2 4 6 |1 7 3 |9 8 5 |
3 5 1 |9 2 8 |7 4 6 |

1 2 8 |5 3 7 |6 9 4 |
6 3 4 |8 9 2 |1 5 7 |
7 9 5 |4 6 1 |8 3 2 |

5 1 9 |2 8 6 |4 7 3 |
4 7 2 |3 1 9 |5 6 8 |
8 6 3 |7 4 5 |2 1 9 |
Elapsed time in milliseconds: 134015
740,190,074 values were tested

Wait, it solved it in just over 2 minutes? If for some reason I got an answer that less than 640,000,000 iterations were tested, I would start wondering how it solved it differently, but I had nearly 100 million MORE iterations than the Wikipedia article said was needed, and I still solved it much faster, with only a 1.4ghz Intel Core 2 Duo.

Apparently some Sodoku fans like to exaggerate about how hard their puzzles really are… Either that, or they really sucked at writing the code to check if a value is legal.

Note: I’ll throw up a link to my solver once I get a GUI together and put up an applet.

Rubik’s Cube Programming: Part 3

I’m still messing with the Rubik’s Cube and Java3D every now and then, so here’s an update. Instead of making the cubies actually rotate, I just decided to make them change color. And instead of bothering to keep track of all the cubies and change the colors, I instead just decided to display the cube as a BranchGraph, and then remove the BranchGraph and generate a new one when you twist a side. Result, the colors of the cubies change. Not the best way to do it probably, but it works well enough. In order to rotate a side I’d need to have cubies in more than one transform group, delays to not rotate one side until another side is done rotating, and regenerating the transform groups every twist anyway because the same cubies would no longer be on the same faces. I’ll save that for version 2…

Rubik's Cube Program Version 0.1

At the top you have controls to reset the cube to a solved state, scramble the cube,  and display either a black Rubik’s Cube or a see through Rubik’s Cube. In the center, we have the Rubik’s Cube itself, can be rotated, moved, and zoomed using the mouse. The right is a list of text values describing the arrays, and on the bottom is an entry box which will allow values f, f’, b, b’, l, l’, r, r’, t, t’, d, d’, rotating the sides either clockwise or counterclockwise. You can either enter one value at a time or a handful of values seperated by spaces. Everything works fine and I declare it version 0.1!

You can go play with it if you download Java 3D API here,

http://java.sun.com/products/java-media/3D/download.html

And you can find the Rubik’s Cube in it’s current version here,

http://wolfhacker.jumbofx.com/cube/cube.html

Note: it will NOT work at this moment without downloading and installing the Java 3D API first. It’s a small and fast install though.

To do list:

1. Display the sides not visable by means of some sort of mirror.
2. Program the methods to actually solve the cube and display how.
3. Create user entry mode so people can program in their own cube permutation to be solved.
4. Run without the need for users to download Java 3D manually.

I’ll get right on that… after writing up an EE120 lab report, doing MAT267 homework, and finishing up homework that’s actually for my Java class… and maybe watching some TV. Stay tuned for most likely the last Rubik’s Cube programming post, part 4!

Rubik’s Cube Programming: Part 2

In the beginning, there was nothing. Then the programmer said, “let there be light!”

Let there be light!

And then… there was still nothing, but now you could at least see it if there was something. So begins the adventure in Java 3D. I decided to make a bunch of little square cubies instead of actual cubed cubies, just cause it kinda looks cool. Maybe I’ll try it with cubes later, but whatever. I think all I have to do is make all the cubies, add them to transform groups, and then add those into transform groups which will rotate the sides, and then add those into the branchgroup, and then add that into the universe, and everything will work out. Well I’m really not sure, Java3D tutorials are so very boring, but I’ll try it and find out. I don’t have anything else to post tonight, so here’s a pic of the cube being built. As usual school and work are taking up almost all of my time, leaving most of the Rubik’s cube program and specs in a purely theortical state of exisetence. It’ll all work fine, in theory, I think. Although, as soon as you open the box, the state may collapse along with the entire theory. ::incoherent rambling of 1:00am::

Cube Building