Sudoku

DFS

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int map[9][9] = { 0 };
int flag = 0;
void dfs(int i, int j)
{
  if (flag)                             //填完毕直接返回
    return;
  if (j > 8)                            //一行结束
  {
    i++;                                //换行
    j = 0;                              //换行读取
    if (i > 8)                          //最后一行结束
    {
      flag = 1;                         //填完毕
      for (int m = 0; m < 9; m++)       //遍历输出
      {
        for (int n = 0; n < 9; n++) 
        {
          cout << map[m][n];
        }
        cout << endl;
      }
      return;
    }
  }
  if (map[i][j] == 0)                   //填空
  {
    int f[10] = { 0,0 };                //桶
    for (int k = 0; k < 9; k++)         //搜索整行
      f[map[i][k]]++;
    for (int k = 0; k < 9; k++)         //搜索整列
      f[map[k][j]]++;
    for (int k = i / 3 * 3; k < i / 3 * 3 + 3; k++)      //搜索子网格
      for (int l = j / 3 * 3; l < j / 3 * 3 + 3; l++)
        f[map[k][l]]++;
    for (int k = 1; k < 10; k++)         //遍历
      if (f[k] == 0)                     //找到空桶
      {
        map[i][j] = k;                   //放进数独
        dfs(i, j + 1);                   //递去
        map[i][j] = 0;                   //归来
      }
  }
  else {                                 //略过有数字的
    dfs(i, j + 1);
  }
  return;
}
int main()
{
  int c;
  cin >> c;                              //九宫格的次数
  char ch;
  for (int i = 0; i < c; i++)
  {
    flag = 0;
    for (int m = 0; m < 9; m++)          //写入九宫格的数独数字
      for (int n = 0; n < 9; n++)
      {
        cin >> ch;                       //逐个读取
        map[m][n]=ch-'0';                //ascii码
      }
    dfs(0, 0);
  }
}

笔记：数独从头开始自左向右，自上而下遍历寻找数字暴力搜索所有的可能，有重复的就回溯，重新填写数字，没有任何的剪枝和优化