J10 习题-1 靶型数独

题目描述

靶形数独的方格同普通数独一样，在 $9$ 格宽且 $9$ 格高的大九宫格中有 $9$ 个 $3$ 格宽且 $3$ 格高的小九宫格（用粗黑色线隔开的）。 在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 $1-9$ 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。 上图具体的分值分布是： 最里面一格（黄色区域）为 $10$ 分， 黄色区域外面的一圈（红色区域）每个格子为 $9$ 分， 再外面一圈（蓝色区域）每个格子为 $8$ 分， 蓝色区域外面一圈（棕色区域）每个格子为 $7$ 分， 最外面一圈（白色区域）每个格子为 $6$ 分，如上图所示。 比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法)，而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。 对于给定的靶形数独，请编程算出，能够得到的最高分数。

输入格式

一共 $9$ 行。 每行 $9$ 个整数（每个数都在 $0-9$ 的范围内），表示一个尚未填满的数独方格，未填的空格用0表示。每两个数字之间用一个空格隔开。

输出格式

一个整数，表示可以得到的靶形数独的最高分数。 如果这个数独无解，则输出整数 $-1$。

样例输入

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

样例输出

2829

样例分析

如上所述。

数据范围

对于$40\%$ 的数据，数独中非 $0$ 数的个数不少于 $30$。 对于$80\%$ 的数据，数独中非 $0$ 数的个数不少于 $26$。 对于$100\%$ 的数据，数独中非 $0$ 数的个数不少于 $24$。