N-Queens II

N-Queens II

问题：

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions

思路：

　　典型的DFS方法+回溯，回溯在于不成功就清楚原先标记

我的代码：

public class Solution {
    public int totalNQueens(int n) {
        if(n <= 0)  return 0;
        char [][]board = new char[n+1][n+1];
        for(int i = 0; i <= n; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                board[i][j] = '.';
            }
        }
        testQueens(1,board, n);
        return num;
    }
    private int num = 0;
    public boolean testQueens(int curRow,char[][] board, int n)
    {
        if(curRow == n + 1) 
        {
            num ++;
            return true;
        }
        for(int y = 1; y <= n ; y++)
        {
             if(canPut(board, curRow , y, n))
             {
                board[curRow][y] = 'Q';
                if(!testQueens(curRow + 1, board, n))
                {
                     board[curRow][y] = '.';
                }
             }
            
        }
        return false;
    }
    public boolean canPut(char [][]board, int x, int y, int n)
    {
        for(int row = 0; row <= x - 1; row++)
        {
            for(int col = 0; col <= n; col++)
            {
                char c = board[row][col];
                if(c == '.') continue;
                else
                {
                    if(y == col) return false;
                    if(col + row == y + x) return false;
                    if(col - row == y - x) return false;
                }
            }
        }
        return true;
    }
}

我的代码可修改之处：

public void testQueens(int curRow,char[][] board, int n)
    {
        if(curRow == n + 1) 
        {
            num ++;
            return ;
        }
        for(int y = 1; y <= n ; y++)
        {
             if(canPut(board, curRow , y, n))
             {
                board[curRow][y] = 'Q';
                testQueens(curRow + 1, board, n);
                board[curRow][y] = '.';
             }
            
        }
        return ;
    }

他人代码：

public class Solution {
    public static int sum;
    public int totalNQueens(int n) {
        sum = 0;
        int[] usedColumns = new int[n];
        placeQueen(usedColumns, 0);
        return sum;
    }
    public void placeQueen(int[] usedColumns, int row) {
        int n = usedColumns.length;
        
        if (row == n) {
            sum ++;
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (isValid(usedColumns, row, i)) {
                usedColumns[row] = i;
                placeQueen(usedColumns, row + 1);
            }
        }
    }
    public boolean isValid(int[] usedColumns, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (usedColumns[i] == col) {
                return false;
            }
            if ((row - i) == Math.abs(col-usedColumns[i])) {
                return false;
            }
        }
        return true;
    }
}

学习之处：

• 显然命名之处 placeQueen 要比 testQueen更贴切 isValid 要比 canPut更加贴切一点
• 我的代码里面 testQueens返回true代表一次成功的尝试，返回false代表这一次所有的情况的都尝试过了（尝试过程中有成功的也有失败的案例）
• 由于testQueen 中true 和 false代表的事件非互斥，所以他人代码中干脆就没有进行判断true false 只有尝试一遍就可以了 故出现了我的代码可修改之处的代码
• 他人的代码，只用一个数组记录测试了哪一列，更加简洁，越简洁，错误越少

private int queenNum = 0;
public int totalQueenNum(int n){
if(n <= 0) return 0;
int[][] queenMark = new int[n+1][n+1];
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
queenMark[i][j] = 0;
}
}

}
void testQueue(int row, int[][] queenMark, int n){
if(row == n+1){
queenNum ++;
return;
}
for(int col=1; col<=n; col++){
if(isValid(queenMark, row, col,n)){
queenMark[row][col] = 1;
testQueue(row+1, queenMark, n);
queenMark[row][col] = 0;
}
}
}

boolean isValid(int[][] queenMark, int x, int y, int n){
for(int i=0; i<=x-1; i++){
for(int j=0; j<=n; j++){
if(queenMark[i][j] == 0) continue;
if(j == y) return false;
if((x+y) == (i+j)) return false;
if((x-y) == (i-j)) return false;
}
}
return true;
}