Generating Numbrix-like Puzzles

Very tiny
Numbrix-like
 example.

We got the kids interested in a simple kind of logic puzzle called Numbrix.  I showed my son a multiplication table and he became obsessed for a time with filling out more and more tables with bigger and bigger numbers.  Since he seemed to like writing numbers into boxes, we looked around for a puzzle we could print off the web that he could do, and found some kids' Numbrix at this "Math in English" site.

Numbrix is apparently a puzzle published in Parade magazine, developed by Marilyn vos Savant, who had the Guinness Book of World Records "Highest IQ" in the late eighties and also a serendipitous surname.  The goal is to complete a Hamiltonian path on a grid with consecutive numbers.  If you've heard of Hidato, it's like that but you can't move diagonally.  The ones at Math in English seem to be randomly generated, but the ones made by vos Savant are cleverly constructed by hand.

Either way, there are a limited number of Numbrices at both places.  I haven't found anything that generates them "while u wait", so I set about writing some code to do that.

A randomly generated Numbrix-like puzzle.

The first step is to generate a random-ish Hamiltonian path.  With a little googling I came across this "HamPath" library, which does the trick well enough.  Next we need to take away random numbers until we have a puzzle we like.  The puzzle has to have a unique solution, so each time we take away a number we have to check to see if there's another solution, so we need a solver.  The solver just runs all the possibilities and stops early if it finds a second solution.

I wanted it to have a difficulty knob, so we need some kind of measurement of difficulty and then we need to make sure when we take a number away we haven't made it too difficult.  I use two measures of difficulty: "choice count" and "stretch".

Choice count is a measure of how many branches were encountered in the solver.  This vaguely represents the number of ways you can go wrong if you just jot down numbers without thinking or looking ahead.  It's not perfect, because sometimes the path forward is obvious to a human but not to the solver.  It measures a choice at each number, but it would be better if it considered sequences of numbers that link two given cells.  For instance, starting with 1 in the above picture, you need to reach the 6.  There are a few ways to get to the 6, and the solver counts those, but it also counts ridiculous choices that never reach the 6, and I don't think humans would count those as making the puzzle more difficult.

The other measure is stretch.  Stretch is just the maximum distance between two given numbers.  A smaller stretch generally means you need to look ahead a smaller distance to find the next number, and it tends to mean fewer paths between one number and the next.  This one also has the benefit that it speeds up the solver; a very large gap in the numbers causes the solver to consider a large number of possible paths and while that might make an interesting puzzle, we need the solver to finish in a reasonable amount of time.

So we take away numbers, making sure the solution is unique and keeping the difficulty in check, and then stop after a certain number of tries, and now we have a puzzle.  The rest is user interface.

Puzzle in progress.

I tried to keep the interface simple.  The Parade site requires you to type the numbers, which I found annoying.  Instead I wanted to just click to place the next number.  There are some edge cases to consider, however.  The user should be able to start at any number, and go in both directions.  Also, the user needs to be able to remove numbers they've entered.  And when you hit a sequence you've already placed, it should skip over that to set you up to put the next number after the sequence.

As you'll guess from the intro menu, I'm thinking of adding more puzzle types later.

Probably Puzzles