题解 | #Sudoku#

#include <stdio.h>
#include <string.h>
//坑爹没看清题目,还要求每个九宫格数字都唯一
//DFS如果匹配到继续匹配下一个直到pos==count 
//如果下一个匹配不到那么回溯当前值,为当前位置匹配新的数
//如果当前位置每一个数都匹配不到,返回0给上层DFS,上层DFS收到后判断下个位置无论什么
//数字都无法匹配说明当前位置这个数值有问题,回溯当前数值,为当前位置匹配新的数
//如果DFS返回1说明之后有一种情况匹配到了那么保留当前值直接return回上一层=>直到最
//开始并返回1;

int count = 0; //填空数量
int open_x[81];
int open_y[81];
int DFS(int map[][9], int pos);
int islegal(int map[][9], int x, int y);
int main()
{

  int map[9][9];
  for (int i = 0; i < 9; i++)
    for (int j = 0; j < 9; j++)
    {
      scanf("%d", &map[i][j]);
      if (!map[i][j])
      {
        open_x[count] = i;
        open_y[count] = j;
        count++;
      }
    }

  int pos = 0;
  if (DFS(map, pos))
  {
    for (int i = 0; i < 9; i++)
    {
      for (int j = 0; j < 9; j++)
        printf("%d ", map[i][j]);
      printf("\n");
    }
  }
  return 0;
}
//pos给第pos个缺位匹配数值   pos 0 - count-1
int DFS(int map[][9], int pos)
{
  if (pos == count)
    return 1;

  int x, y;
  x = open_x[pos], y = open_y[pos];

  for (int i = 1; i <= 9; i++)
  {
    map[x][y] = i;
    if (islegal(map, x, y))
    {
      map[x][y] = i;

      if (DFS(map, pos + 1) == 0)
        map[x][y] = 0;
      else
        return 1;
    }
  }

  map[x][y] = 0;
  return 0;
}

int islegal(int map[][9], int x, int y)
{
  int ret = 1;

  for (int i = 0; i < 9; i++)
  {
    if (i != x && map[x][y] == map[i][y])
    {
      ret = 0;
      break;
    }
  }
  for (int j = 0; j < 9; j++)
  {
    if (j != y && map[x][y] == map[x][j])
    {
      ret = 0;
      break;
    }
  }

  int cx = x / 3, cy = y / 3;

  for (int i = cx * 3; i < cx * 3 + 3; i++)
  {
    for (int j = cy * 3; j < cy * 3 + 3; j++)
    {
      if ((i != x || j != y) && map[x][y] == map[i][j])
      {
        ret = 0;
        break;
      }
    }
  }

  return ret;
}