Having issues trying to solve N Rook problem . Always get n*n solution and not N factorial

Question

I'm trying to get N ways of solves a N rook problem. The issue I am having is currently, I seem to get n*n solutions while it needs to be N! . Below is my code, I have written it in simple loops and functions, so it's quite long. Any help would be greatly appreciated

Note: Please ignore case for n = 2. I get some duplicates which I thought I would handle via JSON.stringify

var createMatrix = function (n) {
    var newMatrix = new Array(n);

    // build matrix
    for (var i = 0; i < n; i++) {
      newMatrix[i] = new Array(n);
    }

    for (var i = 0; i < n; i++) {
      for (var j = 0; j < n; j++) {
        newMatrix[i][j] = 0;
      }
    }

    return newMatrix;
  };

  var newMatrix = createMatrix(n);

  // based on rook position, greying out function 
  var collision = function (i, j) {
    var col = i;
    var row = j;

    while (col < n) {
      // set the row (i) to all 'a'
      col++;
      if (col < n) {
        if (newMatrix[col][j] !== 1) {
          newMatrix[col][j] = 'x';
        }
      }
    }

    while (row < n) {
      // set columns (j) to all 'a'
      row++;
      if (row < n) {
        if (newMatrix[i][row] !== 1) {
          newMatrix[i][row] = 'x';
        }
      }
    }

    if (i > 0) {
      col = i;
      while (col !== 0) {
        col--;
        if (newMatrix[col][j] !== 1) {
          newMatrix[col][j] = 'x';
        }
      }
    }
    if (j > 0) {
      row = j;
      while (row !== 0) {
        row--;
        if (newMatrix[i][row] !== 1) {
          newMatrix[i][row] = 'x';
        }
      }
    }
  };

  // checks position with 0 and sets it with Rook
  var emptyPositionChecker = function (matrix) {
    for (var i = 0; i < matrix.length; i++) {
      for (var j = 0; j < matrix.length; j++) {
        if (matrix[i][j] === 0) {
          matrix[i][j] = 1;
          collision(i, j);
          return true;
        }
      }
    }

    return false;
  };


  // loop for every position on the board
  loop1:
    for (var i = 0; i < newMatrix.length; i++) {
      var row = newMatrix[i];

      for (var j = 0; j < newMatrix.length; j++) {
        // pick a position for rook
        newMatrix[i][j] = 1;

        // grey out collison zones due to the above position
        collision(i, j);

        var hasEmpty = true;

        while (hasEmpty) {
          //call empty position checker
          if (emptyPositionChecker(newMatrix)) {
            continue;
          } else {
            //else we found a complete matrix, break
            hasEmpty = false;
            solutionCount++;
            // reinitiaze new array to start all over
            newMatrix = createMatrix(n);
            break;
          }
        }

      }
    }

Answer 1

There seem to be two underlying problems.

The first is that several copies of the same position are being found.

If we consider the case of N=3 and we visualise the positions by making the first rook placed red, the second placed green and the third to be placed blue, we get these three boards:

They are identical positions but will count as 3 separate ones in the given Javascript.

For a 3x3 board there are also 2 other positions which have duplicates. The gets the count of unique positions to 9 - 2 - 1 -1 = 5. But we are expecting N! = 6 positions.

This brings us to the second problem which is that some positions are missed. In the case of N=3 this occurs once when i===j==1 - ie the mid point of the board.

This position is reached:

This position is not reached:

So now we have the number of positions that should be found as 9 - 2 - 1 - 1 +1;

There appears to be nothing wrong with the actual Javascript in as much as it is implementing the given algorithm. What is wrong is the algorithm which is both finding and counting duplicates and is missing some positions.

A common way of solving the N Rooks problem is to use a recursive method rather than an iterative one, and indeed iteration might very soon get totally out of hand if it's trying to evaluate every single position on a board of any size.

This question is probably best taken up on one of the other stackexchange sites where algorithms are discussed.