Paul R. Potts
I’ve become aware of a job opportunity in Cambridge, MA. The company offering the job want to see a programming example. They recommend solving one of two problems posted on their web site. This one looked the most interesting to me. They say:
Unless otherwise specified, you may use any language you like for the programming problem. If you send code for a problem, please include the final answer in the body of your email and please send code that actually compiles and runs, so we can test it – no pseudo-code please. If you’re submitting a program, try to make it as efficient as possible.
Queens & Knights
In 1850, Carl Friedrich Gauss and Franz Nauck showed that it is possible to place eight queens on a chessboard such that no queen attacks any other queen. The problem of enumerating the 92 different ways there are to place 8 queens in this manner has become a standard programming example, and people have shown that it can be solved using many different search techniques.
Now consider a variant of this problem: you must place an equal number of knights and queens on a chessboard such that no piece attacks any other piece. What is the maximum number of pieces you can so place on the board, and how many different ways can you do it?
I was just recently going through old papers and looking at a solution to the Knight’s Tour problem I wrote for a computer science class in my sophomore year of college. The Knight’s Tour asks for a “tour” in which the knight, using his unique L-shaped move, touches every square on the chessboard once and only once. My program allowed the user to specify the size of the chessboard (there are “degenerate” cases; obviously, on a 1x1 or 2x2 board the knight cannot move; on a 3x3 board the knight either starts in the center square and is stuck there, unable to move, or starts on an edge square and can quickly hit all the edges but can’t get into the center).
I ran solutions up to a 10x10 board, but this was about eighteen (!) years ago, and the code was written in Pascal for the VAX 11/750. I can’t remember if the 10x10 solution ever completed. The standard 8x8 board took some time, perhaps an hour or more, depending on the load on the system. My fellow students and I took great joy in all firing off our programs at once and watching the system crawl. I put in diagnostic output which would dump out an ASCII representation of the board in progress, and as you may guess, the I/O was much more expensive than the search, and so the runtime would increase by at least an order of magnitude.
We were studying recursion, but deep recursion in VAX Pascal was dicey: deep searches tended to blow up the stack. A follow-up assignment for some classes was to implement the solution using a hand-rolled stack data structure, which was considerably more efficient. I don’t think my class implemented that program; we did something else with stacks. In any case the lesson taught, inadvertent or not, was that was recursion was a powerful tool for performing a brute-force search of a problem space, but “real” programs would not use it because building and unwinding the program call stack is expensive and the program is likely to run out of stack space.
Now I know that VAX Pascal probably didn’t properly optimize tail recursion. I’ve got several other programming techniques and more expressive languages at my disposal these days. So I’m going to take on the Queens and Knights problem and see what I can come up with. I have friends that would probably try it using a genetic algorithm or a purely functional language like Clean, but I’m not quite to that point; I’m going to write it in Dylan, using the Gwydion implementation. I’ll first re-implement the Knight’s Tour to warm up, using a naive technique, and then see if I can start to improve the run time.
You can follow my efforts on my Wiki here.
P.S.: I have an initial Knight’s Tour implemented, using a combination of iteration (to track starting positions) and recursion (to backtrack) along with a table of offsets to describe the moves. This took me about one work day, so I’ve certainly come a ways since 1986. The Gwydion d2c compiler is still frustratingly slow, although using a BBEdit worksheet helps; it doesn’t quite have a real-time listener for writing and testing functions interactively, like Apple’s Dylan did (and yes, I’m familiar with d2c’s interactive mode; it is still too slow and fragile). I’d like to try this using Functional Objects Dylan, but I don’t have access to a working PC at the moment, and the free version is missing some basic library functions (I believe format-out is missing, for example, unless you pay for at least the minimal console libraries package).