Sudoku

"Hey Amy, everyone else is playing games on their ipods, kindles, or laptops, is it ok if I do this Sudoku puzzle in the paper?" Ten minutes later I find myself thinking the same thing I always do when I try the Sudoku puzzle: "This is boring, I should just write a program to do this for me." Well, I'm on vacation, so last night I just went ahead and finally wrote that program. It took me a lot longer to write it than it took for Amy's (puzzle-fiend) father to solve the puzzle that was in the paper, but it was a lot more interesting to translate my fuzzy strategies into functional algorithms.

I started by writing a function that would generate all the vals that a missing entry could be. Since that only shakes out obvious missing entries, I wrote another routine to do eliminations (ie, this is the only cell that a number could be in for each of the three series). A little debugging and the C program spit out the solution as far as I had been able to do with paper (not guessing values). Last, I added a brute force guessing routine to iterate when no path forward was available. Following some tuning to eliminate dumb guesses, the program spit out the right solution in about a second.

Fun. Yeah, I know, they ask CS students to code these things up on AP exams and hot-startup job interviews. It was still fun to me, largely because none of the real world CS/CompE problems I've worked on have ever had such well-defined rules, easily-quantized inputs, or easily-validated solutions. Some day I'll work a CS job where all we do is implement quick sort instead of resolving configure dependencies between different aging source trees.