Tao of Coding

One of the final projects in the AI class is to teach middle schoolers about an aspect of AI. I chose to teach about the fun and joy of constraint satisfaction through Sudoku. Why constraint satisfaction? Because that is one of the first AI topics I came across in the class and thought ‘Wow, this is awesome… and I haven’t seen it twenty times before’. It is a solid method for solving a specific class of problems.

To see it in action, look here. Source code for everything (from the simple (and terrible) php webpage, to the Constraint Satisfaction Solvers, is available here.

I’ll warn though that the code isn’t completely clean. A fair amount of the code in the various solvers could have been implemented… differently. Such that it wouldn’t be a copy and pasting between the ~5 solver implementations.

Also, the way possible values are determined is a horrible kludge, that I should have known better then to do. Part of the goal of the Solver implementations is to make the intermediate states visible. To make that simpler, no actual recursion is used in the course of searching. Since no recursion is being used, it’s harder to make changes to intermediate state, such as ‘we need remove values 5 and 6 from the possible values for cell 15’, and then undo those changes. Being lazy, I opted to just generate the possible values for all cells on each step of the algorithm. Terribly inefficient, but, honestly, that’s not a problem for this. Drawing out the entire board on screen probably takes much more time. What was unfortunate was when I went to try and encode Forward Checking / Arc Consistency, I needed the Variables to store their possible values in order for the code to be not terrible. As such, Arc Consistency turned out to be rather messy, and surprisingly useless on the small Sudoku grid (or I did it wrong; but surely that is impossible), so I scrapped it and moved on. But, overall, the implementation would be more robust if the variables were responsible for storing their individual values. And if I didn’t need those intermediate states.

In conclusion, it was fun, I learned things, hopefully middle schoolers will also learn things, or at least lie and say they did, and I now have other finals I need to worry about.

Special thanks, again, to Peter Norvig’s Solving Every Sudoku Puzzle. It provided for entertaining quotes and thoughts, and the inclusion of a 62 digit number in the final website.

This entry was posted on Sunday, December 13th, 2009 at 15:14 by Matt and is filed under Education. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.