Here is a single solution for n=8, one of 92 possible solutions:
One of the first things students notice is that correct solutions require each queen to occupy a different row and column, and every row and column need to have a queen for the solution to be valid. Think about it: if queens can attack along rows or columns, then each queen needs to have her own row and column — and every row/column on the board needs a queen if you’re going to get to n!)
This realization lead to our team’s first breakthrough in implementing a solution. Placing a queen in a single square in the first row eliminates a vast swath of options — including the entire top row. You can continue building solutions by moving to the next row, where a tree of solutions begins to emerge: each space where you can still place a queen after placing one in the top row is now a “child” solution to the problem.
Realizing that the solutions resembled a tree caused our team to think about recursive traversal of trees. It seems like a lot of engineers are hesitant to use recursive solutions when there are ways to create iterative solutions, but I find that odd. Using a recursive solution forces engineers to scale down the solution to discrete, repeated tasks that can be well-understood.
In the case of n-Queens, we repeated one childishly simple process over and over: place a queen, look at the next row, place a queen in the first available spot, look at the next row, place a queen in the first available spot, look at the next row… you get it. Here’s a snippet of our recursive solution:
Our remaining problem was about remembering which solutions we’d tried. We thought about copying the entire board and reversing steps when we hit an invalid solution (nowhere to place a queen on the next row) or storing the solutions we’d tried in memory.
Eventually we stumbled onto the concept of “backtracking” — the fundamental principle that most computer science professors are trying to teach when they assign this problem to students. We needed to iterate across each of the n squares at the top of the chess board, but each branch of solutions stemming from that top square had invalid solutions that could be “pruned” from the tree and considered no further. If we hit a row where we couldn’t place a queen, we needed to backtrack to the last row and try placing a queen at the next available square. If there were no more available, we needed to go back another row and try the next available square… and so on.
If our recursive function crawled to the bottom of the tree and placed 8 queens, we needed to iterate a counter that recorded how many solutions we had found. Here’s a table of the number of solutions for each value n:
Our function was able to find 92 solutions to 8-queens in less than 1 second. We started to experience lags at n=11 (4 seconds), n=12 (15 seconds), and n=13 (>90 seconds).
One of our classmates tried to refactor his code to use bit-shifting to evaluate attacks along diagonals, easily the most time-consuming step of our code. He claimed that his implementation with bit-shifting could find the solution to n-15 (over 2.2 million solutions) in one second! His primary motivation, however, was that the refactored code — using bit-shifting and recursive search — can fit into a tweet. Here’s a tweet-sized implementation from one of the HR guys behind the world-record n-Queens solution:
I really enjoyed n-Queens. It feels amazing to solve a challenging problem like this in only two days — especially one that computer science students might take a few weeks in college to solve. Hack Reactor pushes students to tackle big problems and get used to pushing through the feeling that you don’t know enough about a subject to get started. If you’re willing to approach unfamiliarity with an open and curious mind, you can do big things quickly.
Onward to web security and foiling XSS/CSRF attacks!