Wife: Dancing lynx? That would be really cute. Of course, they’d have to get fitted for special little shoes, if they were going to be, like, tap-dancing or anything. Still…

Me: It’s links. With an “i”.

Wife: Yes, I know that, but it would be much cuter if it was a bobcat.

Me: And less useful.

Yesterday I implemented the Dancing Links algorithm. I first heard about it a few years ago after I wrote a simple Sudoku game. I didn’t write a version back then because I had tired of writing Yet Another Sudoku Game, and my game languished and was forgotten. This time, however, my current project could benefit from it.

It is a surprisingly easy algorithm to write. With the way people talk about it—and with some of the implementations I have seen—I was expecting it to be a long, drawn out battle to get it done. Not so! It was the work of maybe a few hours to read about it and get it completed. Now I just need to see if it will work for my purposes. 😛

While optimizing the Prim algorithm I ran into a annoying situation. I couldn’t make the mazes match between the faster implementation and the original one. I triple checked the logic. I scoured the lines of code. Nothing seemed to be wrong! In the end I decided to have the old version print out exactly which cells it was checking, because it obviously wasn’t doing what it was supposed to. And it wasn’t. Here’s where things were going awry:

void PrimMaze::moveNeighbors(const QPoint& cell)
{
	int size = m_out.size();
	for (int i = 0; i < size; ++i) {
		if (areNeighbors(cell, m_out.at(i))) {
			m_frontier.append(m_out.takeAt(i));
			--size;
		}
	}
}

The code looks simple enough. The problem is that I didn’t decrement the counter along with the size, so it was skipping cells. Because of this the mazes generated by the current implementation of the Prim algorithm are actually wrong. The new implementation does not suffer from the bug, and it would make the new code messy (and slower) to try and recreate it.

This means that when I release the next version of CuteMaze any saved gave that uses the Prim algorithm will have to be restarted. Otherwise you’ll end up who knows where with incorrect information.