The N - Queens Puzzle

A naive way to solve this problem is to generate all the possible combinations of given N queens on the N x N chessboard and check if the current combination satisfies the N Queen problem constraints or not. If it does, then add the configuration to the solution and move ahead to find other possible combinations. 
 

Algorithm:   

Create an output array that stores all the possible solutions of N - queen puzzle. 

• Suppose we place the queens column-wise, and we start with the very first column.
• If all the queens are placed and the configuration is a valid one, then we have found a valid solution. Add it to the output array.
• Iterate over all the rows in the current column:
  • Place the queen in this square(row, column) and recursively place the queens in the other columns
• If all rows have been tried and nothing worked, simply return from the function.
   

Checking if a configuration is valid:

• For checking if no queen is present in the current row:
  • Iteratively check if there is a queen in any of the previous columns, i.e. (0, col - 1) for the current row ‘row’. If yes, this arrangement is not valid, return false.
• For checking if no queen is present along the diagonals:
  • Iteratively check if there is a queen in the upper left diagonal and lower left diagonal. If yes, this arrangement is not valid, return false.
  • For checking the diagonals, we can simply check if the difference between the coordinates of the queens is the same or not.
• If reached here, return true as placement is safe.

At last, we will return the output array containing all the configurations in which we can successfully place the N queens.

The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check if it’s safe to place the queen here, by checking for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack.

Note: There could be the only one queen in a row and the only one queen in a column.
 

Algorithm: 

Create an output array that stores all the possible configurations of N - queen puzzle. 

• Suppose we place the queens column-wise, and we start with the very first column.
• If all the queens are placed, we have found a valid solution. Add it to the output array.
• Iterate over all the rows in the current column:
  • Check if the queen can be placed safely in this square(row, column) or not. If yes, then recursively check if placing the queen here leads to a solution.
    • If placing the queen in the square(row, column) leads to a solution, then add the solution to the output array.
    • Unmark this square(row, column), i.e. remove the queen from this square and backtrack to check other rows.
• If all rows have been tried and nothing worked, simply return from the function.
   

Checking if placing queen at square[row, col] is valid/safe:

• For checking if no queen is present in row and column:
  • Iteratively check if there is a queen in any of the previous columns, i.e. (0, col - 1) for the current row ‘row’. If yes, this arrangement is not valid, return false.
• For checking if no queen is present along the diagonals:
  • Iteratively check if there is a queen in the upper left diagonal and lower left diagonal. If yes, this arrangement is not valid, return false.
• If reached here, return true as placement is safe.

At last, we will return the output array containing all the configurations in which we can successfully place the N queens.

We can optimize the previous algorithm by not using a 2-D array for checking whether it’s safe to place a queen or not. We will use the property of diagonals to achieve this. 

For checking upper left diagonal and lower left diagonal, try finding a pattern between the index of row and column.

1. Upper left diagonal has a difference of row and column as constant.
2. Similarly, the lower-left diagonal has a sum of row and column as constant.

So to check for diagonals we will match that particular constant(difference for upper left and sum for lower left), if that constant as the index is set for that specific array, that means the queen is present in the diagonal, and that cell is not safe. 

To make it more clear, let’s move to the algorithm. 
 

Algorithm: 

Create an output array that stores all the possible configurations of N - queen puzzle.

• We will use three linear arrays, queensInRows, queensInDiag1 and queensInDiag2, to depict the chessboard. This will decrease the cost to check if the cell is safe or not from O(N) to O(1) as well as our space complexity will get reduced.
• Initialise the 3 linear arrays with -1.
  • ‘queensInRows’ of size ‘N’.
  • ‘queensInDiag1’, and ‘queensInDiag2’ of size (2 * N).
• For a queen to be safe in a cell, it should be safe in its row, column, upper left diagonal and lower-left diagonal.
• Suppose we place the queens column-wise, and we start with the very first column. If all the queens are placed, we have found a valid solution. Add it to the output array.
• Iterate over all the rows in the current column:
  • To check  if placing the queen at square[row, col] is valid/safe:
    • If queensInRows[row] or queensInDiag1[row + col] or queensInDiag2[col - row + N - 1] is NOT equal to -1, continue with the next position as placing queen at square[row, col] is not valid/safe.
  • If the placement of the queen is valid,
    • Mark that index as column number in the arrays ‘queensInRows’, ‘queensInDiag1’, and ‘queensInDiag2’. 
      queenInRows[row] = queenInDiag1[row + col] = queenInDiag2[col - row + N - 1] = col.
    • After placing the queen, then recursively call the function to place the remaining queens. If this leads to a solution, then add the solution to the output array.
  • Unmark this square(row, column), i.e. remove the queen from this square and backtrack to check other rows.
• If all rows have been tried and nothing worked, simply return from the function.
• When we can place a queen at the Nth row, it means we have successfully placed all the N queens so add this configuration to our final answer array.
   

At last, we will return the array containing all the configurations in which we can successfully place the N queens.