findNQueensSolution

PHOTO EMBED

Thu Jun 24 2021 05:26:32 GMT+0000 (Coordinated Universal Time)

Saved by @ejiwen #javascript

window.findNQueensSolution = function(n) {
  var solution; //fixme
  var done = false;

  // means we reached the end of the board.
  // but what if reached the end of the board, but don't have a solution? will that never happen?
  var board = new Board({'n': n});

  if(n===0){
      return [];
  }
  // recurse on columns
  var repeat = function(board,j){

    // means we reached the end of the board.
    // but what if reached the end of the board, but don't have a solution? will that never happen?


    // we only increment j when we place a rook/queen. so when j reaches n, it means we
    // placed all n rooks/queens, since we reached the end of the board.
    if(j >= n){
      return true;
    }

   for(var i = 0; i < n; i++) // loop on rows
   {
      board.togglePiece(i, j);
     if(!board.hasRowConflictAt(i) && !board.hasMajorDiagonalConflictAt(board._getFirstRowColumnIndexForMajorDiagonalOn(i,j))
      && !board.hasMinorDiagonalConflictAt(board._getFirstRowColumnIndexForMinorDiagonalOn(i,j)))
     {
       if(repeat(board, j + 1) === true)
       {
          if(solution === undefined){
            solution = board;
            done = true;
          }
          return true;
       }

     }
     board.togglePiece(i, j);
     if(done)
      return true;
   };

    return false;
  }

  repeat(board, 0);

  if(solution === undefined){
    solution = board.rows();
  }
  else{
    solution = solution.rows();
  }


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