題目描述
相信 N-Queens 問題對每個研究 backtracking 的人來講都不陌生,這個問題是要在一個 $N \times N$ 大小的棋盤上擺 $N$ 個皇后,讓她們不會互相攻擊到。為了讓這個問題更難一點,我們設計了一些障礙物在棋盤上,在這些點上不能放皇后。請留意這些障礙物並不會防止皇后被攻擊。
在傳統的 8-Queen 問題中,旋轉與鏡射被視為不同解法,因此我們有 92 種可能的方式來放置皇后。
輸入格式
輸入的資料最多包含 10 筆測試個案,每個測試個案的第一行會有一個整數 $N$ ($3 \lt N \lt 20$),接下來的 $N$ 行代表棋盤資料,點號 '.'
代表空的盤格,星號 '*'
代表放有障礙物的盤格。
輸出格式
對每筆測試個案,輸出這是第幾個 case 以及這個 case 有幾種可能的放置方式。
範例輸入
8
........
........
........
........
........
........
........
........
4
.*..
....
....
....
範例輸出
Case 1: 92
Case 2: 1
備註
- 2016/02/29 增加強迫平行的測試資料。