This blog is highly personal, makes no attempt at being politically correct, will occasionaly offend your sensibility, and certainly does not represent the opinions of the people I work with or for.
Having fun solving games
avatar
This evening I played Sudoku for the first time (I had to look up Wikipedia to learn the rules, because I really didn't have a clue of what it was), and then I decided to write a program to solve it. One hour and half later (between 11pm and 0.30am) it was done...

... but then, maybe I should start the story from the beginning.

Two months ago I was sitting next to Aubrey when I saw her playing a game called Unblock Me, by KiraGames. The principle is somehow simple, you need to slide the pieces horizontally or vertically in order to unblock the red one.

I didn't have any intention to actually play this game, but decided to write a program to solve it. I draw the picture I saw on her screen and started coding.





What really motivated me wasn't the fact that it is a difficult problem (in fact it's not), but the fact that I have always been interested in game analysis without having had any opportunity to write programs in this area, so I thought that for my own education, I might as well spend some time on it.

The program takes a description of the initial board in input (using of course my own conventions)

h2,2,3,1
v3,4,2,0
v3,5,2,0
h2,1,4,0
v2,3,4,0
v2,2,5,0
h2,3,6,0

and outputs the solution (the sequence of moves to free up the red one)





The initial implementation was done in PHP and worked perfectly (of course). Few days later I decided to re-implement the entire thing in Objective-C, also as a command line utility. The two implementations follow the same logic (building an increasingly big tree of possibilities) and outputs the exact same answer, but are not of identical implementation, there is a slight difference in the way the children of a given node are computed in the Objective-C implementation (this said, the two trees are the same in the end).

The surprising thing is that Objective-C, despite of being compiled, didn't do as much better than PHP as I had anticipated. Objective C is only just about twice faster than PHP on the above board. PHP took 6.39 seconds, while the Objective-C implementation took 3.45 seconds. (This result seems to be quite a constant, from very easy to more complex boards).

Anyway, coming back to tonight, I came across the following: Oracle RDBMS 11gR2, Solving a Sudoku using Recursive Subquery Factoring which I found was genius, but I also realised that I didn't know how to play Sudoku. Quick online search and I found Web Sudoku. The first game was the following





Which has given birth to the following program: http://pastebin.com/f37fe848a (I embedded the board in the code, so not to have to read it for an external file -- and don't pay attention to nslog, it's one of my standard functions, I use it for debugging) and the following solution





So now, given how easy it was to write a program to solve that thing, I don't understand all the fuzz about Sudoku. People should learn, say, Chess (or even better, Go). Just to make my life a bit more complicated :-)

[ add a comment ]

Archives