靶形数独

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100;
int map[maxn][maxn], vis[4][maxn][maxn],result,b[maxn],a[maxn][maxn];
int ans=0,flag=0;
struct Row
{
  int zeroNum, lineIndex;
}row[10];
bool cmp(Row a, Row b) {                    //排序规则：每行的未填空格数量从低到高排列
  return a.zeroNum < b.zeroNum;
}
int which(int i, int j)                     //九个子网格
{
  if (i <= 3)
  {
    if (j <= 3) return 1;
    else if (j <= 6) return 2;
    else return 3;
  }
  else if (i <= 6)
  {
    if (j <= 3) return 4;
    else if (j <= 6) return 5;
    else return 6;
  }
  else
  {
    if (j <= 3) return 7;
    else if (j <= 6) return 8;
    else return 9;
  }
}

int point(int i, int j)                           //靶向系数
{
  if (i == 1 || j == 1 || i == 9 || j == 9) return 6;
  if (i == 2 || j == 2 || i == 8 || j == 8) return 7;
  if (i == 3 || j == 3 || i == 7 || j == 7) return 8;
  if (i == 4 || j == 4 || i == 6 || j == 6) return 9;
  return 10;
}
void DFS(int count, int sum) {                    //九宫格一维数组，总数
  if (count == 82) {                              //所有的空格填完
    flag = 1;                                     //填完毕
    result = max(result, sum);                    //取最大值
    return;
  }
  int x = b[count] / 9 + 1;                       //行 ——
  int y = b[count] % 9;                           //列 |
  if (y == 0) {                                   //特例：y=0说明搜索到列数为9的方格，改变x和y的值。
    x = b[count] / 9; 
    y = 9;
  }
  if (!map[x][y]) {
    for (int i = 1; i <= 9; i++) {
      int g = which(x, y);
      if(!vis[1][x][i] && !vis[2][y][i] && !vis[3][g][i]) {                                  //行、列、子网格都没有重复数字
        vis[1][x][i] = vis[2][y][i] = vis[3][g][i] = 1;                                      //标记
        DFS(count + 1, sum + i*point(x,y));                                                  //修改总分数
        vis[1][x][i] = vis[2][y][i] = vis[3][g][i] = 0;                                      //回溯
      }
    }
  }
  else {
    DFS(count + 1, sum);
  }
}
int main() {
  for (int i = 1; i <= 9; i++) {                                                              //输入待填空的数独
    for (int j = 1; j <= 9; j++) {
      cin >> map[i][j];
      if (map[i][j] == 0) {                       //未填空格
        row[i].zeroNum ++;                        //一行的未填空格数量
        row[i].lineIndex = i;                     //行编号
      }
      else {
        vis[1][i][map[i][j]] = vis[2][j][map[i][j]] = vis[3][which(i, j)][map[i][j]] = 1;     //行、列、子网格都填写1
      }
      ans += map[i][j]*point(i,j);               //计算起始的分数
    }
  }
  int num = 0;
  sort(row + 1, row + 1 + 9, cmp);               //排序：先编辑未填空格速度会更快
  for (int i = 1; i <= 9; i ++) {                //行
    for (int j = 1; j <= 9; j ++) {              //列
      int x = row[i].lineIndex;                  //未填空格的行
      int y = j;                                 //遍历列
      b[++num] = (x - 1) * 9 + y;                //将排序后的点放入一维数组中
    }
  }
  DFS(1, ans);
  if (flag) {
    cout << result << endl;
  }
  else {
    cout << -1 << endl;                          //无解
  }
}

笔记：而后上一题的类型是一样的，这道题再上一道题的基础上优化了很多。排序后先填写空白少的行数，把行、列还有子网格用三维数组查重，将二维数组的九宫格压缩成一维数组