J10 习题-2 简单数独

题目描述

给出含有 $N*N$ 个格子的正方形表格，要求每个格子都填上一个个位数（范围 $1 \sim N$ ），使得每行、每列以及同一斜线上的数字都不同。部分格子已经填好数字。

求满足题意的方案数。

注意：同一斜线上总是有 $n$ 个数字，也就是说不满 $n$ 个数字的斜线会在关于轴线另一端的斜线中选择那条与其互补的斜线来凑够 $n$ 个数字，从而作为一条斜线，如样例的加粗部分 $(2,4,1,3,5)$。

输入格式

第一行输入一个整数 $N$ 。 下来给出一个部分已经填好数字的正方形。总共N行，每行 $N$ 个字符，‘*’表示空白格子，还没有填数字。

输出格式

一个整数，为符合要求的方案数。

样例输入

5
54*21
3*154
*54*2
4*215
*1***

样例输出

1

样例分析

答案为

5 4 3 2 1
3 2 1 5 4
1 5 4 3 2
4 3 2 1 5
2 1 5 4 3

数据范围

对于 $100\%$ 的数据有：$1 \leq N \lt 10$ 。