(Hard) N-Queens (LeetCode : C#)

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

📕 문제 설명

nxn 체스보드에 서로 공격할 수 없도록 n개의 queen 배치하기 (모든 가능한 distinct한 케이스들 반환하기)

'Q' : 퀸 놓인 자리
'.' : 빈 칸

• Input
  정수 n
• Output
  퀸이 서로 공격하지 않는 distinct한 보드 상태들

예제

풀이

재귀, 완전 탐색 (시간 초과)

public class Solution {
    public int boardLen = 0;
    public List<IList<string>> answerList = new List<IList<string>>();
    public IList<IList<string>> SolveNQueens(int n) {
        char[,] chessBoard = new char[n,n];
        
        boardLen = n;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                chessBoard[i, j] = '.';
            }
        }

        FillNQueens(chessBoard, n);

        return answerList;
    }

    public bool FillNQueens(char[,] board, int n)
    {
        for (int i = boardLen - n; i < boardLen; i++)
        {
            for (int j = 0; j < boardLen; j++)
            {
                // 현재 i j 확인하기 
                if (IsValid(board, i, j))
                {
                    board[i,j] = 'Q';
                    n--;
                    if (n == 0)
                    {
                        List<string> tempList = new List<string>();
                        // board 리스트로 변환 
                        for (int ti = 0; ti < boardLen; ti++)
                        {
                            string cur = "";
                            for (int tj = 0; tj < boardLen; tj++)
                            {
                                cur += board[ti,tj].ToString();
                            }
                            tempList.Add(cur);
                        }
                        answerList.Add(tempList);
                    }
                    if (FillNQueens(board, n)) return true;
                    else 
                    {
                        board[i,j] = '.';
                        n++;
                    }
                }
            }
        }

        return false;
    }

    public bool IsValid(char[,] board, int row, int col)
    {
        for (int i = 0; i < boardLen; i++)
        {
            if (board[i, col] == 'Q') return false;
            if (board[row, i] == 'Q') return false;
            if (row + i < boardLen && col + i < boardLen && board[row + i, col + i] == 'Q') return false;
            if (row - i >= 0 && col - i >= 0 && board[row - i, col - i] == 'Q') return false;
            if (row + i < boardLen && col - i >= 0 && board[row + i, col - i] == 'Q') return false;
            if (row - i >= 0 && col + i < boardLen && board[row - i, col + i] == 'Q') return false;
        }

        return true;
    }
}

public class Solution {
    List<string[]> result = new List<string[]>();
    int boardLen;
    int[] board;
    public IList<IList<string>> SolveNQueens(int n) {
        board = new int[n];
        boardLen = n;
        FillNQueens(0);
        return result.ToArray();
    }

    public void FillNQueens(int x)
    {
        if(x == boardLen) // n개 놓기 가능한 경우
        {
            string[] res = new string[boardLen];
            for (int i = 0; i < boardLen; i++)
            {
                string temp = "";
                for (int j = 0; j < boardLen; j++)
                {
                    if (j == board[i]) temp += "Q";
                    else temp += ".";
                }
                res[i] = temp;
            }
            result.Add(res);
            return;
        }
        else
        {
            for(int i = 0; i < boardLen; i++)  // x 고정 후 해당 줄 쫙 놓아보기
            {
                board[x] = i; // (x,i 에 놓기) 
                if(IsValid(x))
                {
                    FillNQueens(x+1); // 다른 줄로 넘어가서 반복
                }
            }
        }
    }

    public bool IsValid(int x)
    {
    	// 위에 row부터 차례차례결정하므로 그 전 row들 보기 ( i < x)
        for(int i = 0; i < x; i++)
        { // board[x] = i -> (x,i)에 배치 
            // board[i] = i -> (i,i) 줄이 겹쳐서 못 놓는 경우임 
            // x좌표랑 y좌표 차 절대값 같으면 대각선
            if(board[x] == board[i] || Math.Abs(board[x] - board[i]) == Math.Abs(x - i))
            {
                return false;
            }
        } 
        return true;
    }
}

결과