BM59 N皇後問題

内容介紹

• 1 題目
• 2 解析

1 題目

2 解析

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int ret = 0;
    public int Nqueen (int n) {
        // write code here
        char[][] chessboard = new char[n][n];
        for(int i = 0; i < chessboard.length; i++){
            for(int j = 0; j < chessboard[0].length; j++){
                chessboard[i][j] = '.';
            }
        }
        backTracing(0, n, chessboard);
        return ret;
    }
    public void backTracing(int row, int n, char[][] chessboard){
        // 當棋子能走到n行說明目前解法有效,否則走不到最後一行就會進行回退
        if(row == n){
            ret++;
            return;
        }
        for(int col = 0; col < n; col++){
            // 隻有目前位置有效才會繼續往下遞歸
            if(vaild(row, col, n, chessboard)){
                chessboard[row][col] = 'Q';
                backTracing(row + 1, n, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    public boolean vaild(int row, int col, int n, char[][] chessboard){
        // 若該位置上方或者左上或者右上有皇後了就傳回false
        for(int i = 0; i < row; i++){
            if(chessboard[i][col] == 'Q'){
                return false;
            }
        }
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if(chessboard[i][j] == 'Q'){
                return false;
            }
        }
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(chessboard[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
}
           

在本回溯中

橫向相當于是每一行下棋的位置,縱向(遞歸深度)就是下的哪一行.