<Hard> N-Queens II (LeetCode : C#)

https://leetcode.com/problems/n-queens-ii/

📕 문제 설명

nxn 체스보드에 n개의 퀸을 둘 때 가능한 distinct한 solution 개수 반환

• Input
  정수 n
• Output
  distinct한 가능한 체스 보드 케이스의 수

예제

풀이

public class Solution {
    int answer = 0;
    int[] board;
    int boardLen;
    public int TotalNQueens(int n) {
        board = new int[n];
        boardLen = n;
        FillNQueens(0);
        return answer;
    }

    public void FillNQueens(int x)
    {
        if (x == boardLen)
        {
            
            answer++;
            return;
        }
        else
        {
            for (int i = 0; i < boardLen; i++)
            {
                board[x] = i; // x, i에 고정
                if (IsValid(x)) FillNQueens(x+1);
            }
        }
    }

    public bool IsValid(int x)
    {
        for (int i = 0; i < x; i++)
        {
            if (board[x] == board[i] || Math.Abs(board[x] - board[i]) == Math.Abs(x - i)) return false;
        }

        return true;
    }
}

결과