New update is available. Click here to update.

Last Updated: 19 Dec, 2022

Easy

```
There is no input.
```

```
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
```

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:

- Each column of the chessboard should have exactly one queen because the queen can attack vertically.
- Each chessboard row should have exactly one queen because the queen can also attack horizontally.
- There should be no diagonal in which two or more queens are present, as the queen also attacks diagonally.

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.

**// **Function to return a valid chessboard configuration.

**function **insertConfiguration(char[][] board):

- Create a 1-D array ‘config’ of size 8, which will hold the current chess board configuration in the form of permutation from 1 to 8.
- Iterate over the columns from ‘1’ to ‘8’ using variable j:
- Iterate over rows from ‘1’ to ‘8’ using the variable i:
- If board[i][j] == ‘Q’:
- config[j] = i

- If board[i][j] == ‘Q’:

- Iterate over rows from ‘1’ to ‘8’ using the variable i:
- Return ‘config’.

**// **Function to check that queen can be placed at (row, column) or not

**function **isSafe(char[][] board, int row, int column):

- Initialize two variables, ‘i’ and ‘j’, each assigned to ‘row’ and ‘column’ respectively.
- While j > 0:
- If board[i][j] == ‘Q’:
- Return false

- j = j - 1

- If board[i][j] == ‘Q’:
- j = column // Re-initializing
- While i > 0 AND j > 0:
- If board[i][j] == ‘Q’:
- Return false

- j = j - 1, i = i - 1

- If board[i][j] == ‘Q’:
- i = row, j = column // Re-initializing
- While i < 9 And j > 0:
- If board[i][j] == ‘Q’:
- Return false

- j = j - 1, i = i + 1

- If board[i][j] == ‘Q’:
- Return true

**// **Function to place the queen at cells of the board

**function **validConfiguration(int[][] ans, char[][] board, int column):

- If column > 8:
- Insert array received from ‘insertConfiguration(board)’ into ‘ans’.

- Iterate over the rows from ‘1’ to ‘8’ using variable ‘i’:
- If isSafe(board, row, column): // Calling isSafe function
- board[i][column] = ‘Q’ // Placing the queen here
- Call validConfiguration(ans, board, column + 1)
- board[i][column] = ‘.’

- If isSafe(board, row, column): // Calling isSafe function

**// **Function to find all valid chessboard configurations 8-queen puzzle

**function **eightQueenPuzzle**():**

- Let ‘ans’ be a 2-Dimensional integer array consisting of all possible valid chessboard configurations.
- Initialize a 2-Dimensional array of characters ‘boards’ of size (8 X 8).
- Iterate from ‘1’ to ‘8’ using variable ‘i’:
- Iterate from ‘1’ to ‘8’ using variable ‘j’:
- board[i][j] = ‘.’

- Iterate from ‘1’ to ‘8’ using variable ‘j’:
- validConfiguration(ans, board, 1) // Calling the function
- Return ‘ans’.

Similar problems

Can You Print

Easy

Posted: 14 Apr, 2022

Prime Digit Sum

Hard

Posted: 17 Apr, 2022

Prime Digit Sum

Hard

Posted: 17 Apr, 2022

Mario And His Princess

Moderate

Posted: 12 May, 2022

Combination Sum III

Moderate

Posted: 25 May, 2022

Combination Sum III

Moderate

Posted: 25 May, 2022

Combination Sum III

Moderate

Posted: 25 May, 2022

Generate All Strings

Moderate

Posted: 9 Jul, 2022