# 52. N-Queens II

題目：<https://leetcode.com/problems/n-queens-ii/>

解法：嘗試一列一列去擺放所有位置，如果發現下一列無法放皇后，就往回上一列嘗試其他位置。

Python3：

class Solution:
    def totalNQueens(self, n: int) -> int:
        if n == 1:
            return 1
        
        def check(x, y):
            for i in range(n):
                if board[i][y] == 1 or board[x][i] == 1:
                    return False
            for i, j in zip(range(x+1, n), range(y+1, n)):
                if board[i][j] == 1:
                    return False
            for i, j in zip(range(x-1, -1, -1), range(y-1, -1, -1)):
                if board[i][j] == 1:
                    return False
            for i, j in zip(range(x+1, n), range(y-1, -1, -1)):
                if board[i][j] == 1:
                    return False
            for i, j in zip(range(x-1, -1, -1), range(y+1, n)):
                if board[i][j] == 1:
                    return False
            return True
        
        def backtrack(x):
            nonlocal output
            if x == n:
                output += 1
                return
            for y in range(n):
                if check(x, y):
                    board[x][y] = 1
                    backtrack(x + 1)
                    board[x][y] = 0
        
        output = 0
        board = [[0 for i in range(n)] for j in range(n)]
        backtrack(0)
        return output

if __name__ == '__main__':
    n = 4

    ans = Solution().totalNQueens(n)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int totalNQueens(int n) {
    if (n == 1)
        return 1;
    
    int output = 0;
    int board[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j <n; j++)
            board[i][j] = 0;
    
    bool check(int x, int y) {
        for(int i = 0; i < n; i++)
            if (board[x][i] == 1 || board[i][y] == 1)
                return false;
        for(int i = 1; x+i < n && y+i < n; i++)
            if (board[x+i][y+i] == 1)
                return false;
        for(int i = 1; x-i >= 0 && y-i >= 0; i++)
            if (board[x-i][y-i] == 1)
                return false;
        for(int i = 1; x+i < n && y-i >= 0; i++)
            if (board[x+i][y-i] == 1)
                return false;
        for(int i = 1; x-i >= 0 && y+i < n; i++)
            if (board[x-i][y+i] == 1)
                return false;
        return true;
    }
    
    void backtrack(int x) {
        if (x == n) {
            output++;
            return;
        }
        for (int y = 0; y < n; y++) {
            if (check(x, y)) {
                board[x][y] = 1;
                backtrack(x + 1);
                board[x][y] = 0;
            }
        }
    }
    
    backtrack(0);
    return output;
}

int main()
{
    int n = 4;
    
    int ans = totalNQueens(n);
    printf("%d\n", ans);
    return 0;
}

###### tags: `leetcode` `backtracking`