Challenge: Place N Queens on an NxN Chessboard

Problem statement

You are given an NxN chessboard, and you are required to place N queens on this chessboard such that no queen is under threat from any other queen.

In chess a queen can move any number of steps horizontally, vertically, or diagonally.

This means that no queen should share a row, column, or diagonal with another queen.

Input

As input, your function will take a number n, which is the size of the board, and a 2-D list of strings as board, which is a grid where each row is a list of strings. Each string represents a cell on the board, initially set to ‘-’ to show that the cell is empty.

n = 4
board = [["-", "-", "-", "-"], 
         ["-", "-", "-", "-"],
         ["-", "-", "-", "-"],
         ["-", "-", "-", "-"]]

Output

Your function should return the updated board, such that no queen denoted by q shares a row, column, or diagonal with another queen.

placeNQueens(n, board) = 
       [["-", "q", "-", "-"],
        ["-", "-", "-", "q"],
        ["q", "-", "-", "-"],
        ["-", "-", "q", "-"]]

Coding challenge

You can use the isSafe(i, j, board) function to test whether the position given by i$^{th}$ row and j$^{th}$ column is safe to place a queen. This function basically checks whether the box position given by row i and column j shares row, column, or diagonal with any other queen you had already placed on the board.

Do not change the prototype of either function as these are being used for testing. You can make your own helper functions though.

This one is a little trickier, but at the same time, it unleashes the real power of recursion. Feel free to look at hints. Best of luck!