提示: 欢迎访问OurACM平台。
Problem 1228 数独游戏问题

Accept: 23    Submit: 238
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

数独游戏最早由18 世纪后期的瑞士数学家欧拉发明,称做“拉丁方块”,但当时没有受到世人的重视。20 多年前美国益智游戏杂志Dell Puzzle Magazines开始刊载该游戏并改名为“数字拼图”,但也只是众多拼图游戏中的一种,依然默默无闻。最近日本,香港,英国等地纷纷报道越来越引人注目的数独游戏,并迅速在英国成为全民运动。老少咸宜的数独热已跨过大西洋传到纽约,可能重演80 年代全球人手一个魔方的盛况。在一般情况下,数独游戏中的小正方形由n×n方格阵列组成,大正方形由n×n小正方形阵列组成。开始游戏时,若干小方格里已填上1~ n2的不同数字,要求玩家填满其余空格,使大正方形的每一行和每一列以及每个小正方形包括1~ n2的每一个数字。例如,当n=3 时,数独游戏的一个初始状态如图1 中(a)所示,其惟一解如图1(b)所示。

对于给定的正整数n和数独游戏的初始状态,计算数独游戏的所有解。

Input

第1 行中的数为正整数n(1<n<6)。接下来的n2行,每行有n2个数字,表示已填入方格的数字。当相应数字为0时,表示方格是空的。

处理到文件末尾。

Output

数独游戏解的个数。

Sample Input

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

Sample Output

1

Source

FJ CFCS 2007

Submit  Back  Status  Discuss