xyz
Problem of the day
You must find distinct solutions to the 8-queen puzzle. The 8-queen puzzle involves placing 8 queens on a chess board of size (8 X 8) such that no two queens can attack each other.
Each solution contains distinct board configurations of the 8-queens’ placement where the solution are a permutation of [1, 2, 3, …., n], here the number in the ith index denotes that the ith column queen is placed in the row with that number.
For example, the permutation [1, 7, 3, 7, 5, 6, 7, 8] means the queen in the 1st column is placed in the 1st row, the queen in the 2nd column is placed in the 7th row, and so on. This permutation may or may not be a valid chessboard configuration for the 8-queen puzzle.
Note: In the output, you will have 1/0 corresponding to whether your answer is right/wrong, where 1 denotes right, and 0 denotes wrong. Also, your program will run only on one input file.
There is no input.
Output format:
Return a list of all possible chessboard configurations of the 8-queens puzzle.
You don't need to print anything. Just implement the given function.
Time Limit: 1-sec
Try to place queens one by one in different columns, from left to right.
The naive approach simulates the whole process, i.e. to try out all the possibilities and select valid ones. Array ‘ans’ will keep all the valid configurations of the chessboard. Some things to remember before starting with the algorithm:
We will use a recursive function that helps to place queens so that no two queens attack each other. We will go through all the columns using this function.
Suppose, I am in column ‘i’. So, from column 1 to column (i - 1), all the queens are placed in such a configuration that no two queens attack each other. Now, we try to place the queen at the ith column so that it doesn’t get attacked by any other queen. For this, we iterate from row 1 to row 8, and at each row, we check whether I can place my queen at this row of column ‘i’. If we can place the queen here, we place the queen and move to the next column. Since we are using a recursive function, Let’s say after calling the function for the next column i.e. for (i + 1), we are again at the column ‘i’ (i.e. we completed the recursive function for column (i + 1)). We will mark this row to contain no queen, and check for the remaining rows (By doing this, we can get all the valid configurations). We will stop when our row number is 9 (i.e, out of the chessboard). Otherwise, we go to the next row of the column. We do this until we are out of the chessboard (i.e. our column number is 9). Once we reach here, this means that we got a valid configuration. So, we insert this configuration in our ‘ans’ array.
The steps are as follows:-
// Function to return a valid chessboard configuration.
function insertConfiguration(char[][] board):
// Function to check that queen can be placed at (row, column) or not
function isSafe(char[][] board, int row, int column):
// Function to place the queen at cells of the board
function validConfiguration(int[][] ans, char[][] board, int column):
// Function to find all valid chessboard configurations 8-queen puzzle
function eightQueenPuzzle():
O( N X N! ), Where 'N' is the dimension of the chessboard.
In each column, we are iterating for N times, and at each cell, to check if it is valid to place a queen there, O(1) time is taken. Therefore, the recursive relation is, T(N) = N + N X (T(N - 1)), which gives T(N) = N X N!.
Hence the time complexity is O( N X N! ).
O( N ^ 2 ), Where 'N' is the dimension of the chessboard.
We use a 2-D board array of size N X N to store configurations.
Hence the space complexity is O( N ^ 2 ).