10027. Fast Sudoku

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

背景

不過,還想做得更好不過,還想做得更好

但這個世界卻要求神通廣大、無所不知,那不聰明的我又該何去何從 ...

題目描述

給一張 $9 \times 9$ 數獨,必須滿足每行每列的 1 到 9 的數字不重複,同時在九個 $3 \times 3$ 方格內的 1 到 9 數字也不重複。請計算可填入的方法數。

輸入格式

測資只有一筆,共有九行,每一行上有九個整數,第 $i$ 行上的第 $j$ 個整數表示 $\text{grid}\lbrack i]\lbrack j]$ 填入的數字,若 $\text{grid}\lbrack i]\lbrack j] = 0$ 表示尚未填入。

輸出格式

對於每一組測資輸出一行一個整數,表示數獨共有幾種填法。

範例輸入

0 6 0 0 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0

範例輸出

2

範例輸入 2

0 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

範例輸出 2

292

提示

平行廣度搜先搜尋

備註

  • 2016/02/17 增加平行程式設計 2015 課程中使用的測試資料,可用 OpenMP。

Discussion