Mark As Completed Discussion

One Pager Cheat Sheet

  • You should design an N-Queen problem solver that can place n queens on a n x n square board in a way that no queen is in a mutual attacking position, with a minimum value of n = 4 and a maximum value of n = 100, in O(n^2) time and O(n) space complexity.
  • We need to use a backtracking algorithm to solve the NP-Complete 8-Queen problem due to its large search space ruling out a naive brute force solution.
  • A Board Validation Function is used to check if we can place a Queen in a cell of the board by looping through the rows and checking if there is a Queen in the same column, and by checking if a Queen appears in the first and second diagonals by observing the row and col variables in a loop.
  • We will returnTrue if a Queen is validly placed at a given row and col position.
  • We will start from the first element in the board and attempt to place Queens, incrementing the row until row is greater than n, at which point a solution is found and the board is saved for further backtracking.
  • The algorithm will recursively evaluate row-by-row for valid positions to place the Queen and add each solution to a list of results before backtracking to the next feasible place.
  • We will create a board by multiplying a string of size n and duplicating it n times, then start the backtracking process at row=0 and col=0.
  • We will recursively select Queen positions and build up the solution list, res, with a time complexity of O(n^2) and space complexity of board size times res.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.