NZ20200311 nQueens

JavaScript performance comparison

Test case created by Nick-Zabalza

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
countNQueensSolutions with bitwise operations
window.findNRooksSolution = function(n) {
  var solution = undefined; //fixme
  var board = new Board({'n': n});
  var numPieces = n;
  var curCol = 0;
  var curRow = 0;
  while (numPieces > 0 && curRow < n) {
    board.togglePiece(curRow, curCol);
    if (board.hasAnyRowConflicts() || board.hasAnyColConflicts()) {
      board.togglePiece(curRow, curCol);
    } else {
      numPieces--;
    }
    if (curCol === n - 1) {
      curRow++;
      curCol = 0;
    } else {
      curCol++;
    }
  }
  if (numPieces === 0) {
    solution = [];
    for (var i = 0; i < n; i ++) {
      solution.push(board.get(i));
    }

  }
  console.log('Single solution for ' + n + ' rooks:', JSON.stringify(solution));
  return solution;
};

for (var i = 0; i < 8; i++) {
  findNRooksSolution(i);
}
pending…
countNQueensSolutions with bitwise and 180degree mirror counting
window.countNQueensSolutions = function(n) {
  if (n === 0 || n === 1) {
    return 1;
  }
  var solCount = 0;
  var possibleValues = [1];
  var currentRow = 0;
  var currentCombo = new Array(n).fill(-1);

  var isNodd = n % 2 === 1;
  var nHalved = Math.ceil(n / 2);
  var rowZeroAtHalfWayPoint = false;

  for (var i = 1; i < n; i++) {
    possibleValues.push(1 << i);
  }

  var recursiveCombos = function() {
    var storedPosVal;
    if (currentRow < n) {
      for (var i = 0; i < possibleValues.length; i++) {
        if (currentRow !== 0 || i < nHalved) {
          if (currentRow === 0 && i === nHalved - 1) {
            rowZeroAtHalfWayPoint = true;
          }
          if (possibleValues[i] > -1) {
            currentCombo[currentRow] = possibleValues[i];
            var diagonalConflict = false;

            for (var j = currentRow - 1; j >= 0; j--) {
              if (currentCombo[currentRow] >> (currentRow - j) === currentCombo[j] || currentCombo[currentRow] << (currentRow - j) === currentCombo[j]) {
                diagonalConflict = true;
                break;
              }
            }

            if(!diagonalConflict) {
              storedPosVal = possibleValues[i];
              possibleValues[i] = -1;
              currentRow++;
              recursiveCombos();
              possibleValues[i] = storedPosVal;
            }

            currentCombo[currentRow] = -1;

          }
        }
      }
    } else {
      if (isNodd) {
        if (!rowZeroAtHalfWayPoint) {
          solCount++;
        }
      } else {
        solCount++;
      }
      solCount++;
    }
    currentRow--;
  };

  recursiveCombos();

  console.log('Number of solutions for ' + n + ' queens:', solCount);
  return solCount;
};


for (var i = 0; i < 9; i++) {
  countNQueensSolutions(i);
}
pending…

You can edit these tests or add even more tests to this page by appending /edit to the URL.

0 Comments