A recursive algorithm for generating all N-Rooks solutions and a linear time N-Queens solution

Below is my interactive implementation of the famous N-Rooks and N-Queens problem. If you're on a feed reader or have disabled for JavaScript some reason, you're missing the main feature of this page! Click below on the board to add and remove pieces. The board indicates threatened pieces. Checking 'All' solutions for rooks shows a random solution and logs them all into the JS console.

The N-Rooks Problem

The N-Rooks problem is as follows: on a chessboard with N columns and N rows, how can you place N rooks such than none of them threaten each other? Finding a single solution is trivially simple-- just place a rook at a corner and then place rooks along the diagonal, until reaching the opposite corner. Finding all solutions for a given N is a more difficult and more interesting problem. It also provided me with my first opportunity to surprise a few of my teachers at Hack Reactor!

Generating the set of all N-Rooks solutions given the solutions to size N-1

This solution works as follows:

1. Take each board from the N-1 solution set
2. Append an empty square to each row. This creates an N by N-1 board.
3. Create a new row with one rook on the very last square
4. Create N new boards by inserting the new row into each possible place in the N by N-1 board.

Following this pattern, the final column will have exactly one rook and a board will be created for each possible configuration. Furthermore all possible solutions for each size N will be generated without examining a single board which is not a solution. It's the rare case in which N! time is a good thing-- there are exactly N! solutions for a board of a size N. Here's the JavaScript:

  var allSolutions = _.memoize(function(n) {
    //Base cases
    if (!n) return [];
    if (n === 1) return [[[true]]];

    //Inductive step
    var solutions = [];
    for (var i = 0; i < n; i++) {
      _.each(allSolutions(n-1), function(nMinusOneSolution){
        solutions.push(generateSolution(nMinusOneSolution, i));
      });
    }
    return solutions;
  });

  var generateSolution = function(nMinusOneSolution, i) {
    //Takes in a solution for size n-1 and generates a solution for size n 
    //For every size n-1 solution there are n solutions of size n
    //This function returns the "i"th solution of those n possible solutions
    var n = nMinusOneSolution.length + 1;
    var newSet = [];
    for (var j = 0; j < n-1; j++) {
      var row = nMinusOneSolution[j];
      newSet.push(row.slice(0).concat(false)); //append empty square to every row
    }
    newSet.splice(i,0, makeTrueEndingRow(n)); //insert new rook ending row
    return newSet;
  }

  var makeTrueEndingRow = function(x) {
    var row = _.times(x-1, function(y) { return false; });
    row.push(true);
    return row;
  }

The N-Queens Problem

The N-Queens Problem is similar. Place N queens on an N row, N column board in such a way that none of them threaten each other. Since queens are such strong attackers, it's a far, far more difficult than N rooks. The tactic most people take is to examine every possible board configuration, stopping once a row, column or diagonal conflict is encountered. I tried pruning the solution space by using my All N-Rooks solution as a starting point. Unfortunately, starting with N! configurations to examine was idea killing. After an hour or two trying without success to use a recursive approach similar to my rooks solution, I stumbled upon a linear time solution-- painting the board with knight-moves!

The pattern was simple -- start from one square to the right of the bottom-left corner and place a queen. Move two squares to the right and one up (AKA a "knight's move") and place another. Repeat across the board. After getting to the right edge, wrap around to the left side and continue.

for (var i = 0; i < n/2; i++) {
  if ((i+1)*2-1 < n) { 
    solution[i][((i+1)*2)-1] = true;
  }
  if (i*2 < n){
    solution[i+Math.floor(n/2)][i*2] = true;
  }
}

The only problem is that this pattern doesn't work for all board sizes. It only works for boards of size N where N mod 6 is not 2 or 3.

if ((n % 6 === 2) || (n % 6 === 3)) {
  if (n % 6 === 3) {
    solution = quickSolve(n-1); //treat as board 1 size smaller
    solution[n-1][n-1] = true;  //then add a queen in the corner
    return solution;
  }
        
  //knight moves from center bottom, going left and up
  //the (n + stuff) % n calculation causes horizontal wrap
  if (Math.floor(n/2)-i*2 < n) {
          solution[i][(n + Math.floor(n/2)-i*2) % n] = true;
        } 
        //knight moves from center top, going right and down
        if ((n-i) >= 0) {
          solution[n-i-1][(n+ Math.floor(n/2)-1+i*2) % n] = true;
        }
      }

Amazingly, this technique of solving N-Queens is faster than just printing the chess board! While the size of the board is N^2, this solution traverses only N squares-- those on which it places a queen.

The set of all answers for N-Queens

Solving for all queens is a pretty intimidating problem.Unlike N-Rooks, which has N! solutions and must take N! time, there are far fewer solutions for N-Queens. Using the set of all solutions for N-Rooks and then eliminating solutions which collide on the diagonals would be a straight-forward solution, but by using N-Rooks as a starting point it would take N! time. While, I haven't found a similar recursive solution for N-Queens, it feels like there's a polynomial solution out there. There just has to be :D. Alas, our class at Hack Reactor only had 2 days of working on the problem before it was time to move on to another project.

More fun in the console.

If you're interested in playing around a bit with my program, open your JS console with Firebug or cmd-option-j in Chrome and look at the functions directly. Try solveNRooks(3, {'all':true}); and inspect the returned object to get a look how things work.