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 for the N-Queens problem involves trying all combinations of queen placements. At each step, we need to ensure that the new queen does not conflict with all the previous queens. If a conflict occurs, we must find a new position for the queen.

This logic is well-suited for recursion. We start by creating an nxn array, queens, and call a recursive function from row 0. In the recursive function, we first check if the current row number is equal to n:

If it is, then all queens have been successfully placed and we can add the queens array to the result.
Otherwise, we iterate over all the positions in the current row and for each position, we check if it conflicts with the previously placed queens using a helper function:
- We first verify if there is a conflict in the same column by iterating over all previous rows. If a queen is found in the same column, we return false.
- Then, we verify if there is a conflict in the diagonals. This involves some coordinate conversion.
If there is no conflict, we can place the queen in the current position. After placing the new queen, we call the recursive function on the next row. It’s important to handle the return state after the recursion.

Code

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);
        }
    }

}

// OJ: https://leetcode.com/problems/n-queens/
// Time: O(N!)
// Space: O(N^2)
class Solution {
    vector<vector<string>> ans;
    vector<string> B;
    vector<bool> col, hill, dale;
    int n;
    void dfs(int i) {
        if (i == n) {
            ans.push_back(B);
            return;
        }
        for (int j = 0; j < n; ++j) {
            int h = i + j, d = i + n - 1 - j;
            if (col[j] || hill[h] || dale[d]) continue;
            col[j] = hill[h] = dale[d] = true;
            B[i][j] = 'Q';
            dfs(i + 1);
            B[i][j] = '.';
            col[j] = hill[h] = dale[d] = false;
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        B.assign(n, string(n, '.'));
        col.assign(n, false);
        hill.assign(2 * n - 1, false);
        dale.assign(2 * n - 1, false);
        dfs(0);
        return ans;
    }
};

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        g = [['.'] * n for _ in range(n)]
        col = [False] * n
        dg = [False] * (2 * n)
        udg = [False] * (2 * n)

        def dfs(u):
            if u == n:
                res.append([''.join(item) for item in g])
                return
            for i in range(n):
                if not col[i] and not dg[u + i] and not udg[n - u + i]:
                    g[u][i] = 'Q'
                    col[i] = dg[u + i] = udg[n - u + i] = True
                    dfs(u + 1)
                    g[u][i] = '.'
                    col[i] = dg[u + i] = udg[n - u + i] = False

        dfs(0)
        return res

############

class Solution(object):
  def solveNQueens(self, n):
    """
    :type n: int
    :rtype: List[List[str]]
    """
    ans = []

    def dfs(path, n, ans):
      if len(path) == n:
        ans.append(drawChess(path))
        return

      for i in range(n):
        if i not in path and isValidQueen(path, i):
          path.append(i)
          dfs(path, n, ans)
          path.pop()

    def isValidQueen(path, k):
      for i in range(len(path)):
        if abs(k - path[i]) == abs(len(path) - i):
          return False
      return True

    def drawChess(path):
      ret = []
      chess = [["."] * len(path) for _ in range(len(path))]
      for i in range(0, len(path)):
        chess[i][path[i]] = "Q"
      for chs in chess:
        ret.append("".join(chs))
      return ret

    dfs([], n, ans)
    return ans

51 - N-Queens

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions