10202. Fast N-Queens Basic (OpenMP)

I'm a slow walker, but I never walk backwards.

題目描述

相信 N-Queens 問題對每個研究 backtracking 的人來講都不陌生,這個問題是要在一個 $N \times N$ 大小的棋盤上擺 $N$ 個皇后,讓她們不會互相攻擊到。為了讓這個問題更難一點,我們設計了一些障礙物在棋盤上,在這些點上不能放皇后。請留意這些障礙物並不會防止皇后被攻擊。

在傳統的 8-Queen 問題中,旋轉與鏡射被視為不同解法,因此我們有 92 種可能的方式來放置皇后。

Note

You may use collapse clause to get better parallelism and performance. OpenMP 3.0 collapse is showed in the link.

輸入格式

輸入的資料最多包含 3 筆測試個案,每個測試個案的第一行會有一個整數 $N$ ($3 \lt N \leq 18$),接下來的 $N$ 行代表棋盤資料,點號 '.' 代表空的盤格,星號 '*' 代表放有障礙物的盤格。

輸出格式

對每筆測試個案,輸出這是第幾個 case 以及這個 case 有幾種可能的放置方式。

範例輸入

8
........
........
........
........
........
........
........
........
4
.*..
....
....
....

範例輸出

Case 1: 92
Case 2: 1

Discussion