Mooshu's Blog

Its the final stretch, and for once I’m on time. My thesis and thesis presentation is done, and tomorrow is my Sudoku Surface presentation. For the status of the Sudoku Surface project, everything I originally wanted is done, except for the fact that I dislike Surface List Boxes and really wanted to use a Library Stack to play the game. But as of right now, the game is fully functional.

🙂 Turned in my thesis!
Currently, I’m wrapping up the Sudoku Surface application for the Microsoft Surface table. I’m still confused on how drag/drop works in C#, because all I really want to do is to read in the tag on the image and write that information to the textblock… Sounds easy but it is more than likely the mouse/finger events are not firing.

Well, I decided not to go with the viewing of the user’s moves/techniques. I am more interesting in how items from the library stack can have their tags read in and added to the text block. However, I did add functionality to the element menu controls with saving and resuming games.

I fail at updating, cant you tell? Currently, I have all my testing finished expect for counting the difference in the branching factor for AI Sudoku and the Backtracking solver. For the programs I wrote, my Constraint Solver was the most efficient in solving a large number of puzzles, even though all three are very fast to solve single puzzles of any level.

As such, I think I’m still going to implement the AI Sudoku solver for the Surface table since that way the user can see the techniques being used to solve a puzzle. Maybe if the user is interested in knowing the details of the technique, he/she can press the technique name and be provided the definition and example of the technique in a new window. But that is future work :).

As for now, I changed the background colors for the game. I changed it to a plain black and white board since most puzzles are of that design.

I still have not figured out how I can make a grid a scatter item nor how to have images lock in place to the grid when the user plays the game. These issues will be investigated this upcoming weekend.

And for my thesis…I’m in the process of heavy editing and creating graphs and tables for the data I collected. Also I need to expand on a few important concepts mentioned in my thesis (like constraint satisfaction problem/constraint programming) and include a few footnotes of terms/topics readers might not know (traveling salesman problem/scheduling).

So I mentioned in the last post that I had the backtracking algorithm working. So I tested it against the claimed hardest Sudoku puzzle in the world (Al Escargot, which by the way is not the hardest anymore), and my backtracking solver solved it in about 0.8 seconds. 🙂 However, I tried it on a randomly generated hard puzzle by QQwing, and the backtracking solver took 10 seconds!!!! Argh, why is it taking so long??? That is totally unacceptable! If it took just one puzzle ten seconds, when I run the algorithm against 1000 hard puzzles, it should take the solver 2.7 hours!!!! Not good at all.

Finally found the bug in my backtracking algorithm, in which I again forgot to delete a cell if a invalidation occurred.

Now, I can optimize my backtracking algorithm by limiting the number of backtracks by only applying moves to possible values than trying all 1…n values. That should limit the branching factor.

Now, I just need to create the data necessary to test all these algorithms.

First, with backtracking and backtracking with CPS, QQwing will generate n puzzles of easy, medium, and hard, and diabolical levels. These two algorithms will be timed, and their branching factor will be measured. Also, each algorithm will solve the Al Escargot puzzle n times and determine the average branching factor. Also, it would be neat to reverse/shuffle the order of values possible in the cell and see if that makes a difference.

Lastly, I will use that same data to test my human logic solver against a large number of Sudoku puzzles of various difficulties and see how many can be solved. Each puzzle should take no more than a second, so I will limit the time the human logic solver can take per puzzle. The program will keep a count of how many puzzles were solved out of those that were skipped. It is more than likely those puzzles that were skipped couldn’t be solved using the human logic solvers, and needs to be searched for the answer.

Hypothetical Dream Sequence Begins…

I wake up one morning and make myself a cup of coffee. I walk over to my Surface table and lay down my coffee and turn on the table. I open one app that connects to the New York times and proceed to read the news for the day. However, I feel that I am up for a game of Sudoku, so I click on the Sudoku app. Since I just finished reading the New York Times, I feel like I want to play their daily Sudoku. Thus, I remotely connect to the Sudoku game on the New York times with the Sudoku Surface application, and the daily NY Times Sudoku puzzle is now on my table. Sweet!

Hypothetical Dream Sequence Ends…

So I feel that this “dream sequence” can be a reality, as long as the Surface is connected online and the Sudoku app is able to connect to the New York Times (or any online newspaper).

For the current Sudoku app, while not pretty, is functional. I’m not sure yet if I really want to save the game since I checked out the Checkers and Chess Surface app and there is no option to save the progress of the game.

Also, I want to include a timer somewhere on the Sudoku Surface app. Currently, the user needs to have a keyboard to play the game, but since the SP1 upgrade now includes new objects, like the LibraryStack, I was hoping that the user can drag numbers from the LibraryStack and place them on the Sudoku board. This way the user can experience a true touch system.