Mooshu's Blog

Well, I would like to let everyone know that I did graduate from Bryn Mawr College magnum cum laude with Honors in Computer Science. Since then, I have been doing research at the CS department at my alma matter working on a cross platform multi-language programming editor called Pyjama.

As for my job outlooks, I have just been recruited by MIT Lincoln Labs and start working in late August/September. I’ll be working with the High Performance Computing and Embedded Digital Systems group, or group 102.

Life is good right know. I’m currently searching for apartments in the Boston/Cambridge/Somerville area and hope to find a reasonably priced room soon. I found one that is most ideal: its a 4 bedroom apartment, and I’ll be sharing it with 3 other females. The room itself is furnished, and tv, wireless, dishwaser/dryer come with it. 🙂 The rent is $700 a month, and I find that to be quite affordable even with a bad salary, and its very close to MIT, so I’m thinking of taking up the offer. On the downside, the room will not be available until September 1, so either I need to stay at Bryn Mawr longer than planned or find a way to move in earlier to the apartment.

Who knows. Either way, I need to make my decision soon if I am to get this room.

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.

This past two weeks I have been writing the necessary computer programs implementing Sudoku solving algorithms (constraint, human logic, depth-first search*). Depth-first search should be completed by tomorrow hopefully and then the timing data starts.

Decided to finally start on the Sudoku Surface App, and finally was able to implement a 9×9 grid structure.

To implement this, enter the xaml code and type a few lines:
<Grid Name=”Sudoku” Height=”450″ Width=”450″  ShowGridLines=”True”>
<Grid.RowDefinitions>
<RowDefinition Name=”row1″ Height=”50″ />
<RowDefinition Name=”row2″ Height=”50″ />
<RowDefinition Name=”row3″ Height=”50″ />
<RowDefinition Name=”row4″ Height=”50″ />
<RowDefinition Name=”row5″ Height=”50″ />
<RowDefinition Name=”row6″ Height=”50″ />
<RowDefinition Name=”row7″ Height=”50″ />
<RowDefinition Name=”row8″ Height=”50″ />
<RowDefinition Name=”row9″ Height=”50″ />
</Grid.RowDefinitions>
<Grid.ColumnDefinitions>
<ColumnDefinition Name=”col1″ Width=”50″ />
<ColumnDefinition Name=”col2″ Width=”50″ />
<ColumnDefinition Name=”col3″ Width=”50″ />
<ColumnDefinition Name=”col4″ Width=”50″ />
<ColumnDefinition Name=”col5″ Width=”50″ />
<ColumnDefinition Name=”col6″ Width=”50″ />
<ColumnDefinition Name=”col7″ Width=”50″ />
<ColumnDefinition Name=”col8″ Width=”50″ />
<ColumnDefinition Name=”col9″ Width=”50″ />
</Grid.ColumnDefinitions>
</Grid>

Splash Page

I also included a new feature on the recently released update of the Surface SP1. However, it does not work on the school’s surface unit since we will need to order a usb drive from Microsoft to get the upgrade (lame).

However, this new control called the ElementMenu is pretty cool. To implement this, I included some xaml code to get started.

<s:ElementMenu
Name=”MainMenu”
ActivationMode=”HostInteraction”
ActivationHost=”{Binding ElementName=TouchLabel}”>

<s:ElementMenuItem Header=”Open Game”/>
<s:ElementMenuItem Header=”Save Game”/>
<s:ElementMenuItem Header=”New Game”>
<!– Sub menu items –>
<s:ElementMenuItem Header=”Easy”
Click=”ElementMenuItem_Click”
ContactTapGesture=”ElementMenuItemEasy_ContactTapGesture”/>
<s:ElementMenuItem Header=”Medium”/>
<s:ElementMenuItem Header=”Hard”/>
</s:ElementMenuItem>
</s:ElementMenu>

ElementMenu Control

Since the ElementMenu does not work on the surface unit, I might need to trash this idea and go with the Menu Control, which is not nearly as cool as the ElementMenu control.

From the ElementMenu control, the user can choose New Game >> ‘Diff” and a new game of the difficulty will appear.

Visual of an Easy Sudoku Puzzle

Later on the right hand side will display the techniques used to solve the puzzle. If the user is unable to solve the game or quits, the user can select the Solve It button and the solution to the grid will appear.

Solution to Easy Sudoku Puzzle

The current status of the Sudoku Game for the Surface is this:

• Able to read from file to populate a Sudoku grid
• Solve easy puzzles using constraint propagation techniques
• ElementMenu allows to create a new puzzle by selected difficulty level
• Also included is a save and open menu, which I will write the functionality for later

What needs to be done:

• Write functionality for save/open menu
• Write human logic solver (lone rangers, twins, triplets)
• Write depth first search solver for most difficult puzzles
• Eventually write a Sudoku Generator (but right now that is a future work)
• Write text block to see track changes in grid and display what techniques were used to solve a cell
• Create a few buttons (redo, undo, clear)

Wrote up the lone ranger functions for a row, column, and minigrid. This past week started the twins API, but came across a bug. Found it on Wednesday (I ended up rewriting the givens which resulted in empty cells being filled with incorrect values). Need to finish the back tracking algorithm by implementing a stack API for C# (I think it is all ready built in but I need to verify). Start working on the design of the Surface app this weekend since I need a running version by Monday for another class.

Stress overload. My favorite.

Currently I have implemented the constraint propagation Sudoku solver to solve any easy to medium nxn Sudoku puzzle. Later this week I will edit QQwing’s Sudoku generator to create any nxn Sudoku puzzle (currently it only does 9×9). This week I will write the depth first search/brute force search Sudoku solver and to add pruning include the constraint solver to reduce the search space.
This and next week will include testing these solvers and designing and implementing the Sudoku game for the Microsoft Surface table.