I Used a Cultural Algorithm to Solve the Knight's Tour Problem. Here's What I Learned!

A complete Knight's Tour found via Backtracking on an 8×8 board, every square visited exactly once.

Knight's Tour is a classical problem that demands finding a path for a knight to step on every square on the chessboard exactly once.

There's more than one way to solve this problem:

1. Backtracking: The knight tries a path, and whenever it gets stuck, it backtracks to the last decision point and tries a different move, combined with Warnsdorff's heuristic, which always picks the next square with the fewest future options, so the knight avoids painting itself into a corner.
2. Evolutionary algorithms: Instead of one knight trying one path, you start with a whole population of knights, each attempting a different path. The best-performing ones "reproduce", combining their paths to produce offspring that (hopefully) do even better. Repeat for a few thousand generations, and you get surprisingly good solutions without ever explicitly telling the algorithm the "rules" for a good path.

But here's the thing about a plain genetic algorithm: it's a bit forgetful.

Every generation, the population evolves, the best individuals get picked, they "marry," they produce offspring, and then... that's it. The algorithm never stops to ask why the best paths were good. It just keeps rolling the dice with slightly better odds each time. It's optimization by vibes.

A Cultural Algorithm fixes that by giving the population something a plain GA doesn't have: memory. On top of the regular population, there's a second layer called the Belief Space. Think of it as the tribe's collective wisdom, sitting above the individuals, watching, learning, and occasionally tapping a knight on the shoulder to say "hey, trust me on this one."

In my implementation, the Belief Space isn't just one vague "lessons learned" blob; it's split into three specific types of knowledge, and each one earns its keep differently:

1. Situational knowledge: "just copy what worked"

This is the simplest one: the Belief Space keeps a running top 8 leaderboard of the best paths ever found. When it's time to nudge a new individual, it sometimes grabs a chunk, a stretch of 15 to 30 moves, straight from one of these champions and grafts it into a new path. It's less "learning" and more "cheating off the smart kid," but it works.

2. Normative knowledge: "statistically, this square goes here"

This one's more interesting. For every position in the path, the Belief Space tracks which square tends to show up there across the best individuals, weighted by how good those individuals were. Over time it builds a picture like: "position 12 in a winning path is usually square 34." So when it influences a new individual, it can swap things around to nudge that square toward its "usual spot", not forcing it, just tilting the odds.

3. Historical knowledge: "these three moves in a row tend to work"

The last one tracks short move sequences of 3 grams, basically "square A → square B → square C" patterns, and remembers which sequences show up often in strong solutions. When influencing a new path, it can inject one of these proven mini sequences directly into the chromosome.

None of these three influences is guaranteed to fire every generation. Each one has its own probability of kicking in, so the population doesn't get forced toward the belief space's opinion, it just gets nudged, generation after generation. That balance between exploration (random crossover and mutation) and exploitation (the belief space's accumulated wisdom) is really the whole point of a Cultural Algorithm.

Then I actually ran the numbers, and they told a story I didn't expect.

Here's the success rate across every algorithm I tested, broken down by board size:

Success rate averaged across multiple trials per board size. Individual runs can still fail, as I found out the hard way (see below).

Three runs on an 8×8 board found a complete tour in generation 0, before the algorithm even had a chance to "evolve" anything. Just a lucky initial population, 0.04 to 0.06 seconds, done. Cultural Algorithm's fancy belief space didn't even get to flex.

Then I tried a 7×7 board. The algorithm restarted the population fourteen times chasing stagnation, ran the full 3000 generations, burned through 95 seconds, and landed on... 47 out of 48. So close. Not close enough.

That gap is the whole personality of evolutionary algorithms in one comparison: sometimes you get lucky, and the answer just falls out. Sometimes you grind for a minute and a half and still miss by one square. And that inconsistency is exactly what Backtracking doesn't have; it's slower on average, but it always gets there if a solution exists. Looking back at my own test runs, Backtracking hit 100% success across every attempt, while the Cultural Algorithm landed a complete tour roughly two-thirds of the time. Neither number is "the truth" about these algorithms in general, it's a small sample from my own runs, but the pattern lines up with what you'd expect: guaranteed but slower vs. faster but not guaranteed.

A quick honesty check before I go further

This was my first time actually implementing a Cultural Algorithm, not just reading about belief spaces in a lecture slide, but wiring up situational/normative/historical knowledge and watching it (sometimes) work. So take the numbers above with that in mind. This isn't a polished, tuned system. It's a first pass, and it shows.

Which brings me to where I'm at right now: tuning.

Right now the algorithm has two mutation paths sitting in the code: a plain aggressive swap mutation, and a "smarter" one that tries to find the first broken move in a path and patch it using the belief space's suggestion before falling back to a random swap. I haven't properly A/B tested them against each other yet. My gut says the cultural version should converge faster since it's not just flailing randomly, but "should" isn't data, and that 7×7 run that burned 95 seconds and still landed on 47/48 makes me want actual numbers before I trust my gut on anything.

Some of the things I'm experimenting with next:

• Mutation rate: right now it's fixed. Too high and you're basically randomizing good solutions back into garbage every generation; too low and you never escape a local optimum. I want to try decaying it over generations: aggressive early, gentler once the population's converging on something decent.
• Mutation type mix: instead of picking one mutation function, letting the population use a blend of both (some individuals get the cultural fix, some get the random swap) and seeing which one actually deserves credit for good runs.
• The belief space's influence probabilities: situational, normative, and historical knowledge each fire independently right now, each with its own fixed chance. I want to see what happens if I let the algorithm shift those weights based on how well each type of knowledge has been performing, instead of hardcoding them.
• The restart threshold: 200 stagnant generations before a restart kicks in feels arbitrary. Worth testing whether a shorter patience (restart sooner) actually saves time overall, or whether it just wastes the progress the belief space had already made.

None of this is going to be a quick fix. Evolutionary algorithms are notoriously fiddly, and "just tweak one number" rarely tells the whole story because these parameters interact with each other in ways that aren't always obvious. But that's kind of the appeal too: there's a real, testable question behind every one of these, and the belief space gives me more knobs to turn than a plain GA ever did.

If you're thinking about trying a Cultural Algorithm yourself: don't expect it to just work better than a plain GA out of the box. The belief space is a tool, not a guarantee. It can nudge a population in a useful direction, but it can also nudge it confidently toward the wrong thing if your knowledge sources aren't well-tuned. Mine clearly isn't, yet. That's the next post.

---

This was written while building a Knight's Tour solver combining Cultural Algorithms and Backtracking, as part of my AI coursework. If you've experimented with Cultural Algorithms or evolutionary computation, I'd love to hear what worked (or didn't) for you in the comments.