[LeetCode 51&52] N-Queens I & II (N皇後問題)

題目連結：n-queens

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 
		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.."]
		]
 *
 */

public class NQueens {

	
//	9 / 9 test cases passed.
//	Status: Accepted
//	Runtime: 217 ms
//	Submitted: 0 minutes ago
	//回溯法
	//時間複雜度O(n!) 空間複雜度O(n)
	public int[] columns;		//存儲已放置的皇後占據的列， 		0 未占， 1已占
	public int[] main_diag;		//存儲已放置的皇後占據的主對角線， 0 未占， 1已占
	public int[] anti_diag;		//存儲已放置的皇後占據的副對角線， 0 未占， 1已占
	public String[] st_str;
	public List<String[]> nQueens = new ArrayList<String[]>();
	
	public void init(int n) {
        columns = new int[n];
        main_diag = new int[2 * n];
        anti_diag = new int[2 * n];
        Arrays.fill(columns, 0);
        Arrays.fill(main_diag, 0);
        Arrays.fill(anti_diag, 0);
    	createString(n);
	}
	
	public void createString (int n) {
		st_str = new String[n];
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(".");
		}
		for (int i = 0; i < n; i++) {
			sb.replace(i, i + 1, "Q");
			st_str[i] = sb.toString();
			sb.replace(i, i + 1, ".");
		}
	}	
	
    public List<String[]> solveNQueens(int n) {
    	//初始化各狀态變量
    	init(n);
    	
    	int[] C = new int[n];
    	Arrays.fill(C, 0);
    	
    	dfs(C, 0);
    	return nQueens;
    }
    
    public void dfs(int[] C, int row) {
    	int N = C.length;
    	//表示找到一個可行解
    	if(row == N) {
    		String[] nQueen = new String[N];
    		for (int i = 0; i < N; i++) {
				nQueen[i] = st_str[C[i]];
			}
    		nQueens.add(nQueen);
    		return;
    	}
    	
    	for (int i = 0; i < N; i++) {
			
    		//如果不合法，這跳過目前循環
    		if(!(columns[i] == 0
				&& main_diag[i + row] == 0
				&& anti_diag[N - i + row] == 0)) continue;
			
    		//執行
			C[row] = i;
			columns[i] = 1;
			main_diag[i + row] = 1;
			anti_diag[N - i + row] = 1;
			
			dfs(C, row + 1);
			
			//撤銷
			C[row] = 0;
			columns[i] = 0;
			main_diag[i + row] = 0;
			anti_diag[N - i + row] = 0;			
		}   	
    }
        
	public static void main(String[] args) {
		NQueens queens = new NQueens();
		List<String[]> result = queens.solveNQueens(8);
		System.out.println(result.size());
//		for (int i = 0; i < result.size(); i++) {
//			for (int j = 0; j < result.get(i).length; j++) {
//				System.out.println(result.get(i)[j]);
//			}
//			System.out.println();
//		}
	}

}
           

題目連結：n-queens-ii

import java.util.Arrays;

/**
 * 
	Follow up for N-Queens problem.
	
	Now, instead outputting board configurations, return the total number of distinct solutions.
 *
 */

public class NQueensII {

	
//	9 / 9 test cases passed.
//	Status: Accepted
//	Runtime: 231 ms
//	Submitted: 0 minutes ago

	
	//回溯法
	//時間複雜度O(n!) 空間複雜度O(n)
	public int[] columns;		//存儲已放置的皇後占據的列， 		0 未占， 1已占
	public int[] main_diag;		//存儲已放置的皇後占據的主對角線， 0 未占， 1已占
	public int[] anti_diag;		//存儲已放置的皇後占據的副對角線， 0 未占， 1已占
	public int total;
	
	public void init(int n) {
        columns = new int[n];
        main_diag = new int[2 * n];
        anti_diag = new int[2 * n];
        Arrays.fill(columns, 0);
        Arrays.fill(main_diag, 0);
        Arrays.fill(anti_diag, 0);
   
        total = 0;				//計數
	}
		
    public int totalNQueens(int n) {
    	//初始化各狀态變量
    	init(n);
    	
    	int[] C = new int[n];
    	Arrays.fill(C, 0);
    	
    	dfs(C, 0);
    	return total;
    }
    
    public void dfs(int[] C, int row) {
    	int N = C.length;
    	//表示找到一個可行解
    	if(row == N) {
    		total ++;
    		return;
    	}
    	
    	for (int i = 0; i < N; i++) {
			
    		//如果不合法，這跳過目前循環
    		if(!(columns[i] == 0
				&& main_diag[i + row] == 0
				&& anti_diag[N - i + row] == 0)) continue;
			
    		//執行
			C[row] = i;
			columns[i] = 1;
			main_diag[i + row] = 1;
			anti_diag[N - i + row] = 1;
			
			dfs(C, row + 1);
			
			//撤銷
			C[row] = 0;
			columns[i] = 0;
			main_diag[i + row] = 0;
			anti_diag[N - i + row] = 0;			
		}   	
    }
        
	public static void main(String[] args) {
		NQueensII queens = new NQueensII();

		for (int i = 0; i < 16; i++) {
			System.out.println(i + "- 皇後有 " + queens.totalNQueens(i) + " 種解法");
		}
	}
}

//output
//0- 皇後有 1 種解法
//1- 皇後有 1 種解法
//2- 皇後有 0 種解法
//3- 皇後有 0 種解法
//4- 皇後有 2 種解法
//5- 皇後有 10 種解法
//6- 皇後有 4 種解法
//7- 皇後有 40 種解法
//8- 皇後有 92 種解法
//9- 皇後有 352 種解法
//10- 皇後有 724 種解法
//11- 皇後有 2680 種解法
//12- 皇後有 14200 種解法
//13- 皇後有 73712 種解法
//14- 皇後有 365596 種解法
//15- 皇後有 2279184 種解法