Sudoku Solver

My Micro-C for CoCo project is showing some real strength!  Yesterday, in just a couple of hours I was able to crank-out a non-trivial C program to solve a popular style of number puzzle.  That was a lot of fun!  Moreover, it was simpler than trying to implement the same thing in pure assembly language and the resulting program ran a lot faster than it would run if it were written in Color BASIC.

Sudoku

In the past decade or so, Sudoku puzzles have become as commonplace as the venerable crossword puzzle.  The use of numbers seems to have a special appeal for some folks, and it has been quite common for people to implement solvers for these puzzles as a programming exercise.  Quite a lot of discussion is available over various algorithms for solving such puzzles, and implementations of these algorithms are quite numerous.

A friend of mine had such a project a while back.  When he learned of my current project, he jokingly suggested that I should try to compile his solver for the CoCo.  I think that his project implemented some clever algorithm or another -- I never saw his code, so I don't know if it would be out of the question for the CoCo or not.  But, I did find a brute force algorithm that seemed simple enough to implement.

Recursion

If one makes the distinction between computer scientists and computer engineers, one often finds that the scientists love recursion while the engineers are more skeptical.  To be sure, recursive algorithms often lead to elegant programs that are powerful, expressive, and succinct.  On the other hand, language implementations often impose practical costs on function call stacks that can grow very deep with recursion.  The engineers...ahem...are correct, of course!

Recursive algorithms are only safe when there is a finite and tolerable limit to the recursion.  In the case of Sudoku, there are only 81 positions on the game board to evaluate.  My implementation uses a recursive, brute force algorithm, and it runs without issue in the 8K of RAM that I'm currently allocating for the code and the stack.  It will probably run in half of that or even less, but I haven't tested to find out.

Load 'Em Up

A puzzle solver isn't of much use if it always solves the same puzzle.  On the other hand, writing a puzzle editor doesn't sound like much fun for the amount of effort involved.  What to do?  If only the CoCo came with some sort of built-in editing facility that could help with such tedious tasks...hmmm...

Rather than delving into the minutiae of building a Sudoku editor in C, I decided to let BASIC do the work for me.  I wrote a short BASIC program that first reserves space for the C program and loads that there.  The BASIC code then READs the Sudoku game setup from the included DATA statements and pokes that into memory where the C program can find it.  The puzzle can be changed by simply editing the DATA statements to reflect the new puzzle.  It would be hard to make things any easier, and IMHO it isn't worthwhile to do so.

Burlington Mini Maker Faire

Where I live, we have a little "maker club" called the Alamance Makers Guild.  Last year we held a mini Maker Faire at the local mall, and we will do so again this year on August 17, 2013.  At last year's event, Fahrfall made a good showing and at least some people seemed to enjoy seeing that and my video player for the CoCo3.  I think the Sudoku solver will make its public debut there this year, and I am planning to make a little contest out of it.  I'm thinking that I will challenge humans to see if they can solve a Sudoku puzzle before the CoCo can do it.  I might even make them edit the BASIC program with the Sudoku data themselves before they run it!  Well, it sounds like fun to me...

This seems like a high note on which to end this summer's Retrochallenge event.  I probably won't be doing much more technically on this project before the end of that event.  I do, however, plan to be back with a more reflective post as a wrap-up.  Until then, please do stay tuned...