题解 | #Sudoku#

Sudoku

http://www.nowcoder.com/practice/78a1a4ebe8a34c93aac006c44f6bf8a1

#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;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
陆续:不可思议 竟然没那就话 那就我来吧 :你是我在牛客见到的最美的女孩
点赞 评论 收藏
分享
昨天 15:12
门头沟学院 运营
面向对象的火龙果很爱...:去吃一顿炸鸡就走
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务