Skip to content

this concludes my interest in sudoku

This past week, for lack of much better to do, I’ve implemented a series of Sudoku solvers. I already had one from a few months ago, but the code was just plain ugly and while it kind of worked, I can no longer say conclusively how or why it did. Thus, version 2 was born with the goal of being clean and readable. That accomplished, I noted that my solver was fairly stupid and felt no qualms about taking stupidly long for puzzles rated “intermidiate” and above. So I wrote version 3 with the goal of generalizing the notion of a Sudoku strategy, as used by human players. This involved a tradeoff: the solver could now run into problems which it could not solve. On the other hand, it solved the problems much faster, and always returned in less than a second’s time, whether or not it could solve the problem.

Last night, I implemented version 4, which uses Knuth’s Dancing Links algorithm to solve any puzzle. This strategy is basically impossible for a human to use, but it’s well-suited for machines. Because of that quality, it’s fairly mind-bending: I spent a few hours just wrapping my head around the general plan of how it works. Unfortunately, this had consequences: I dreamed Dancing Links last night. My first thought upon awakening this morning was “That was an interesting debug case. I should try it out in the machine to see if it really works like that.” What’s more interesting is that I am highly motivated (an unusual experience, recently) to debug this thing as soon as possible, to the exclusion of food, my job, and my Japanese class. I’m not actually going to skip any of those things, but I’m hugely tempted to, which I find interesting.

A hypothesis regarding this behavior: programming really is a much better job for me than teaching, as I seem to be desperate for it.

RSS feed

1 Comment

Comment by ultimatepsi
2006-06-15 07:56:53

programming really is a much better job for me than teaching
Also, it tends to pay better. Alternatively, you could teach programming.

 

Sorry, the comment form is closed at this time.