Welcome to Subscribe On Youtube

Question

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

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

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

 

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 9

Algorithm

In fact, I think the order of the two Queens-question should be reversed. The previous question is a little more complicated than this one. There is no difference in essence between the two. Both have to be solved by backtracking. If you understand the previous question The idea of the question, this question only needs to make a small change, no need to ask for the specific queen’s pendulum, just need to increase the counter by one every time a solution is generated.

Code

• Java
• C++
• Python
• Go

• 
  public class N_Queens_II {
  
  	// just simply return list.size(), seems costly if only count is needed
  
  	public class Solution {
  
  		List<List<String>> list = new ArrayList<List<String>>();
  
  		public int totalNQueens(int n) {
  
  			if (n <= 0)
  				return 0;
  
  			// index is row-number, place[index] is position of queen on that
  			// row
  			int[] place = new int[n];
  
  			dfs(n, 0, place);
  
  			return list.size();
  		}
  
  		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
  						|| currentRow - i == (int) Math.abs(place[i] - currentRowPosition))
  					return false;
  			}
  
  			return true;
  		}
  
  		public void saveToList(int[] place) {
  
  			int len = place.length;
  			List<String> one = new ArrayList<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
  				one.add(row.substring(0, rowPosition) + "Q"
  						+ row.substring(rowPosition + 1));
  			}
  
  			list.add(one);
  		}
  	}
  
  }
  
  

• // OJ: https://leetcode.com/problems/n-queens-ii/
  // Time: O(N!)
  // Space: O(N)
  class Solution {
  public:
      int totalNQueens(int n) {
          vector<bool> col(n), hill(2 * n - 1), dale(2 * n - 1);
          function<int(int)> dfs = [&](int i) { // for each i-th row
              if (i == n) return 1;
              int ans = 0;
              for (int j = 0; j < n; ++j) { // try putting on the j-th column
                  int h = i + j, d = i + n - 1 - j;
                  if (col[j] || hill[h] || dale[d]) continue;
                  col[j] = hill[h] = dale[d] = true;
                  ans += dfs(i + 1);
                  col[j] = hill[h] = dale[d] = false;
              }
              return ans;
          };
          return dfs(0);
      }
  };
  

• class Solution:
      def totalNQueens(self, n: int) -> int:
          def dfs(i):
              if i == n:
                  nonlocal ans
                  ans += 1
                  return
              for j in range(n):
                  a, b = i + j, i - j + n
                  if cols[j] or dg[a] or udg[b]:
                      continue
                  cols[j] = dg[a] = udg[b] = True
                  dfs(i + 1)
                  cols[j] = dg[a] = udg[b] = False
  
          cols = [False] * 10
          dg = [False] * 20
          udg = [False] * 20
          ans = 0
          dfs(0)
          return ans
  
  ############
  
  class Solution(object):
    def totalNQueens(self, n):
      """
      :type n: int
      :rtype: int
      """
  
      def dfs(path, n):
        if len(path) == n:
          return 1
        res = 0
        for i in range(n):
          if i not in path and isValidQueen(path, i):
            path.append(i)
            res += dfs(path, n)
            path.pop()
        return res
  
      def isValidQueen(path, k):
        for i in range(len(path)):
          if abs(k - path[i]) == abs(len(path) - i):
            return False
        return True
  
      return dfs([], n)
  
  

• func totalNQueens(n int) (ans int) {
  	cols := [10]bool{}
  	dg := [20]bool{}
  	udg := [20]bool{}
  	var dfs func(int)
  	dfs = func(i int) {
  		if i == n {
  			ans++
  			return
  		}
  		for j := 0; j < n; j++ {
  			a, b := i+j, i-j+n
  			if cols[j] || dg[a] || udg[b] {
  				continue
  			}
  			cols[j], dg[a], udg[b] = true, true, true
  			dfs(i + 1)
  			cols[j], dg[a], udg[b] = false, false, false
  		}
  	}
  	dfs(0)
  	return
  }
  

All Problems

All Solutions