N-Queens

This post is based on a report I wrote with Jean-Baptiste Michel and Gaiëtan Renault for the class Markov Chains and Applications (EPFL, 2022).

When I was in highschool, I braved an applied mathematics class in the dustiest computer room known to man. It was like a dungeon, where photons dared not enter lest they be immediately subsumed by the blinding blaze of the computer screens.

One fateful Friday afternoon, our professor issued a challenge. "How many configurations of 8 queens on a chessboard are there, where none of the queens can attack each other?". Before I reveal how I found every configuration, can you find one?

Click anywhere!

The first thing we might want to think about is skipping any configurations that are obviously wrong, like, if all the queens are huddled up in a corner, or standing in a line. We can imagine considering one column at a time, trying every row until we find a safe position. Sometimes we will get stuck and have to go back one column. Inductively, finding a safe position for the queen in the final column is the same as finding a complete solution to the puzzle, since all the previous queens are also safe. This algorithm is called depth-first backtracking. Step through animation below to watch how it works on a smaller board.

When I returned to the dusty classroom on Monday, I showed the professor my code, and the answer for an 8 by 8 board, 92. I got my bonus points and complimentary chocolate, and promptly forgot about the puzzle.

That is until five years later, when I took a class on Markov Chains. For the class project, we had to answer the question "About how many configurations of 1000 queens on a 1000 by 1000 chessboard are there such that none of the queens can attack each other"?

Perhaps the word "about" should clue you in to why this is an entirely different beast of a problem. But to really grasp the computational difficulty, look at this graph showing the number of valid configurations for increasing board sizes.

~~WORK IN PROGRESS~~

The Markov Chain Monte Carlo Method

Sources

• [link] Cheng Zhang & Jianpeng Ma. Counting solutions for the N-queens and Latin-square problems by Monte Carlo simulations.

09/04/2023