CSES 1. Chessboard and Queens (1624)

출처: https://cses.fi/problemset/task/1624

---

문제 설명

Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.

How many possible ways are there to place the queens?

입력

The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*).

출력

Print one integer: the number of ways you can place the queens.

입력 예

........
........
..*.....
........
........
.....**.
...*....
........

출력 예

65

---

문제 풀이 

NxN보드에서 N개의 Queen을 서로 공격하지 않도록 배열하는 N-Queen 문제이다. 첫번째 열부터 퀸을 하나 배치하고, 공격 받을 수 있는 위치들을 표시하고 8번째 열에 도착하면 경우의 수를 기록한다.

프로그램 내용

/// n-th queen location check
int backtrack(vector<string> board, int nQueen )
{
	if(nQueen == 8)
        return 1;

	int ans=0;
	for (int i = 0; i < 8; ++i)
	{
		if(board[nQueen][i]=='.'){
			vector<string> n_board = board;
			for (int j = nQueen; j < 8; ++j) /// only check below rows
			{
				n_board[j][i]='*';
				if(i-j+nQueen>=0)
					n_board[j][i-(j-nQueen)]='*'; /// diagonal
				if(i+j-nQueen<8)
					n_board[j][i+(j-nQueen)]='*'; /// diagonal
			}
			ans += backtrack(n_board,nQueen+1);   /// updated board , next row
		}
	}
	return ans;
}

int main()
{
    vector <string> board;

    for (int i = 0; i < 8; i++)
    {
        string tmp;
        cin >> tmp;
        board.push_back(tmp);
    }

    int ways = backtrack(board, 0);

 

Introductory problems ( link )