Question

Formatted question description: https://leetcode.ca/all/51.html

51	N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement,
where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Algorithm

The exhaustive method is to try all combinations. Every time a new queen is placed, it must be ensured that it does not conflict with all the previous queens. If a conflict occurs, it means that the current position cannot be placed, and a new place must be found.

This logic is very suitable for recursion. We first create an array queens of length nxn that is full of points, and then call recursion from line 0. In the recursive function, we first judge whether the current number of rows is already n,

  • if yes, it means that all the queens have been successfully placed, so we only need to add the queens array to the result.
  • Otherwise, we traverse the position of all the columns of the row, and after the positions of the row and column are determined, we need to verify whether the current position will conflict, then we need to use a sub-function to judge,
    • first verify whether the column has a conflict, it traverses all the previous rows, if there is a queen in the same column in a certain row, the conflict returns false;
    • then verify whether the two diagonals conflict, which is some coordinate conversion, mainly don’t write it wrong,
  • if there is no conflict, then the conflict You can put the queen in the position. After you put the new queen, you can call recursion on the next line. Pay attention to the return state after the recursion.

Code

Java

public class N_Queens {

    public class Solution {

        List<String[]> list = new ArrayList<String[]>();

        public List<String[]> solveNQueens(int n) {

            if (n <= 0)     return list;

            // index is row-number, place[index] is position of queen on that row
            int[] place = new int[n];

            dfs(n, 0, place);

            return list;
        }

        public void dfs(int n, int currentRow, int[] place) {
            if (currentRow == n) {
                // save to list
                saveToList(place);
                return;
            }

            for (int i = 0; i < n; i++) {

                if (isValid(i, currentRow, place)) {
                    place[currentRow] = i; // 1 meaning place queen
                    dfs(n, currentRow + 1, place);
                    place[currentRow] = i; // undo place queen
                }
            }
        }

        public boolean isValid(int currentRowPosition, int currentRow, int[] place) {
            // check all previous rows
            for (int i = 0; i < currentRow; i++) {
                // if (place[i] == currentRowPosition || Math.abs(currentRow - i) == Math.abs(place[i] - currentRowPosition))
                if (place[i] == currentRowPosition || currentRow - i == (int)Math.abs(place[i] - currentRowPosition))
                    return false;
            }

            return true;
        }

        public void saveToList(int[] place) {

            int len = place.length;
            String[] array = new String[len];

            // construct string of n dots...
            String row = "";
            for(int i = 0; i < len; i++) {
                row += ".";
            }

            for(int i = 0; i < len; i++) {
                int rowPosition = place[i]; // at position place[i] on row i
                array[i] = row.substring(0, rowPosition) + "Q" + row.substring(rowPosition + 1);
            }

            list.add(array);
        }
    }

}

All Problems

All Solutions