目录
数独的要求是每一行,每一列,每一宫都包括1~9,但是不能有重复数字。
主流为深度优先搜索算法,如果使用数据结构,有舞蹈链算法,本篇介绍深度优先搜索算法。
我们的初始条件准备了5个,分别是row[N], col[N], cell[3][3],ones[M], map[M]。
N = 9;
M = 111111111(二进制),511(十进制);
- //设置9*9数独表
- const int N = 9;
- //设置mask长度 M的二进制:111111111,从右到左分别表示1 2 3 4 5 6 7 8 9
- const int M = 1 << N;
-
- //row、col、cell分别表示行、列、宫可填写数的编码
- //ones、map是一个映射关系,ones表示有多少个1,map表示9位二进制的1代表的数字
- int row[N], col[N], cell[3][3];
- int ones[M], map[M];
-
- //数独表
- int arr[9][9] = {
- 4,0,0,9,0,0,0,0,3,
- 0,8,0,0,0,1,0,9,0,
- 0,0,0,0,2,0,7,0,0,
- 0,3,0,0,0,0,0,0,4,
- 0,0,6,7,0,0,5,0,0,
- 2,0,0,0,0,0,0,6,0,
- 0,0,7,0,3,0,6,0,0,
- 0,5,0,6,0,0,0,0,0,
- 1,0,0,0,0,9,0,0,2
- };

那么M是用来干嘛的?
我使用了二进制来优化DFS算法,在下图中只有7不能填,因为mask为0。

map和ones是一个映射关系,下标(二进制)->值(十进制)
map[10] = 2,意思是二进制为10的数十进制为2
ones[11] = 2,意思是二进制为11的数十进制为2
下面初始化的意思是把所有位置都设置成所有数都可填的状态。
- //只需一次初始化的数组map、ones
- void _init()
- {
- //once设置成false后不再执行这个函数
- once = false;
-
- //map和ones是一个映射关系,下标(二进制)->值(十进制)
- //
- //map[10] = 2,意思是二进制为10的数十进制为2
- for (int i = 0; i < N; i++)
- {
- map[1 << i] = i + 1;
- }
-
- //ones[11] = 2,意思是二进制为11的数十进制为2
- for (int i = 0; i < M; i++)
- {
- for (int j = 0; j < N; j++)
- {
- ones[i] += i >> j & 1;
- }
- }
- }
-
- //初始化条件数组
- int init(int _arr[N][N])
- {
- //设置row,col为111111111,代表1`9都在可填写状态
- for (int i = 0; i < N; i++)
- {
- row[i] = col[i] = M - 1;
- }
-
- //在9个宫中设置值为111111111,代表1`9都在可填写状态
- for (int i = 0; i < 3; i++)
- {
- for (int j = 0; j < 3; j++)
- {
- cell[i][j] = M - 1;
- }
- }
-
- //只初始化一次
- if (once)
- {
- _init();
- }
-
- //填入数独表的已知数字,完成初始化工作。
- return fill(_arr);
- }
fill函数是干嘛的?请往下看
fill函数的作用是填入数独表中已知的数字,返回一个整形代表待填入数独表的空位。
我们利用空位作为DFS的制约条件。
- //将数组上已知数的位置、值信息做初始化记录,并记录需要填写的格子数
- int fill(int _arr[N][N])
- {
- //cnt为待填格子数
- int cnt = 0;
-
- //设置cnt,row、col、cell条件
- for (int i = 0; i < N; i++)
- {
- for (int j = 0; j < N; j++)
- {
- if (!_arr[i][j])
- {
- cnt++;
- }
- else
- {
- col[j] -= 1 << (_arr[i][j] - 1);
- row[i] -= 1 << (_arr[i][j] - 1);
- cell[i / 3][j / 3] -= 1 << (_arr[i][j] - 1);
- }
- }
- }
-
- return cnt;
- }
在行,列,宫对应的位置减去对应数的二进制码,这样可以把该数字在行、列、宫对应的二进制码设置为0,代表该数字在该行,该列,该宫已经不可以填写。

可举例填写4和6,三个条件的变化,等式右边为二进制码。
前置有3个功能函数。
这里说一下getmask,
因为&的特点,col & row & cell运算,如果这三个其中一个的二进制码的某个位置上为0,那么返回的计算结果的那个位置的二进制码也为0。
draw是我们递归的灵魂,他的功能是在数组上填数,然后根据填的数修改row、col、cell。
- //获得可填数的编码位(截断到最靠右的1) 例如10110 lowbit后得到10
- inline int lowbit(int x)
- {
- return x & -x;
- }
-
-
- //获取可填数据 col,row,cell经过位运算可得到一串二进制数字,二进制的1代表可以填进数独的数字
- int getmask(int x, int y)
- {
- //printBinary(row[x]);
- //std::cout << " ";
-
- //printBinary(col[y]);
- //std::cout << " ";
-
- //printBinary(cell[x/3][y/3] );
- //std::cout << " ";
-
- //printBinary(col[y] & row[x] & cell[x / 3][y / 3]);
-
- return col[y] & row[x] & cell[x / 3][y / 3];
- }
-
-
- //填数字
- void draw(int _arr[9][9], int x, int y, int num, bool is_set)
- {
- //如果这个位置已经被填过,那么消除这个位置上的数字
- //如果没有,就设置成num
- if (is_set)
- {
- _arr[x][y] = 0;
- }
- else
- {
- _arr[x][y] = num;
- }
-
- //将数字num转化成二进制码
- int v = 1 << (num - 1);
-
- //根据这个位置是否有数字,修改 + - 的逻辑
- if (is_set)
- {
- v = -v;
- }
-
- // -v 代表此位置行,列,宫的可填数num已经填入,该行,列,宫不可再填num
- row[x] -= v;
- col[y] -= v;
- cell[x / 3][y / 3] -= v;
- }
我们 按照标题2. 的逻辑对数独表和三个条件进行增、改,然后搜索。
t_ret表示解的数量。max_ret表示最大解。
位置优化:通过两层循环,找出可填数最少的位置。
- //填数独
- bool dfs(int _arr[9][9], int cnt, int& t_ret)
- {
- //如果可填数为0,则代表已经完成数独
- if (!cnt)
- {
- return true;
- }
-
- //找出最小可选位置,x、y表示坐标,minv代表可填数
- int minv = 10;
- int x, y;
-
- //每一个为0的位置都可以通过getmask(x,y)找到一个9位的二进制数,每一个位置上的1都代表对应数字可填
- for (int i = 0; i < N; i++)
- {
- for (int j = 0; j < N; j++)
- {
- //如果状态码state中的1比minv小,则记录下该位置的xy坐标,并记录下最小可填值minv
- if (!_arr[i][j])
- {
- int state = getmask(i, j);
- if (ones[state] < minv)
- {
- minv = ones[state];
- x = i, y = j;
- //std::cout << std::endl;
- //printBinary(state);
- }
- }
- }
- }
-
- //拿到状态码
- int state = getmask(x, y);
-
- //lowbit取到可填数(从小到大),填了就从状态码中消除对应位置上的1
- for (int i = state; i; i -= lowbit(i))
- {
- //拿到二进制对应的十进制数字num
- int num = map[lowbit(i)];
- //填入num
- draw(_arr, x, y, num, false);
- //开始填数,如果已经填完数独,则打印,并记录解的数量t_ret,最大解max_ret
- if (dfs(_arr, cnt - 1, t_ret))
- {
- //print_arr(_arr);
-
- t_ret++;
- max_ret = t_ret > max_ret ? t_ret : max_ret;
- }
- //撤销填入的num
- draw(_arr, x, y, num, true);
- }
-
- //如果 i = state 的值是0,那么就代表没有数字可以填的,返回失败,并消除上一位的数字
- return false;
- }
函数的逻辑是删除两个数,然后进行DFS,再然后把删除的数填回去,继续删除。
DFS进行之前,我们都初始化row,col,cell三个条件,这样能保证正常递归。
这里我们使用vector和pair(C++),也就是数组和键值对的数据结构。
first代表x坐标,second代表y坐标。
- //得到所有的数组,并记录下数独的最大解
- int _getallarr(int tmp[9][9], int& time)
- {
- //将每一个已知数字的x,y坐标记录到vii
- std::vector
int, int>> vii; - for (int i = 0; i < 9; i++)
- {
- for (int j = 0; j < 9; j++)
- {
- if (arr[i][j])
- {
- vii.push_back({ i,j });
- }
- }
- }
-
- //tmp1.tmp2存要删掉的两个数
- int tmp1, tmp2;
- //记录删除的数的坐标
- int max_ret_tmp = max_ret;
- //vpii的每一个元素都是一对坐标,我们只保留2对坐标
- std::vector
int, int>> vpii; - //依次删除两个数,为了保护源数独,把数据传入到tmp中
- for (int i = 0; i < vii.size(); i++)
- {
- for (int j = i + 1; j < vii.size() - 1; j++)
- {
- //存下要删掉的数,搜索完还原。
- tmp1 = tmp[vii[i].first][vii[i].second];
- tmp[vii[i].first][vii[i].second] = 0;
-
- tmp2 = tmp[vii[j].first][vii[j].second];
- tmp[vii[j].first][vii[j].second] = 0;
-
-
- //计算最大解
- int t_ret = 0;
- int cnt = init(tmp);
- dfs(tmp, cnt, t_ret);
-
- //如果最大解的数值发生变化,那么记录下该点的坐标。
- if (max_ret > max_ret_tmp)
- {
- //此处还可做优化,比如说把2改成time,删time个数的最大解是哪三个?
- max_ret_tmp = max_ret;
- if (vpii.size() == 2)
- {
- vpii.erase(vpii.begin(), vpii.end());
- }
- vpii.push_back(vii[i]);
- vpii.push_back(vii[j]);
- }
-
- //还原删除的数
- tmp[vii[i].first][vii[i].second] = tmp1;
- tmp[vii[j].first][vii[j].second] = tmp2;
- }
- }
-
- std::cout << "删除的坐标是:(" << vpii[0].first << vpii[0].second << ") && (" << vpii[1].first << vpii[1].second << ")" << std::endl;
- return max_ret;
- }
-
- //计算最大解
- int getMaxRet()
- {
- //time为要删的数的个数
- int time = 2;
- //tmp为临时数组
- int tmp[9][9] = { 0 };
- copy_arr(tmp);
-
- //
- return _getallarr(tmp, time);
- }
- //设置9*9数独表
- const int N = 9;
- //设置mask长度 M的二进制:111111111,从右到左分别表示1 2 3 4 5 6 7 8 9
- const int M = 1 << N;
-
- //row、col、cell分别表示行、列、宫可填写数的编码
- //ones、map是一个映射关系,ones表示有多少个1,map表示9位二进制的1代表的数字
- //max_ret表示数独的最大解
- //once 卡关,ones和map数组只需初始化一次
- int row[N], col[N], cell[3][3];
- int ones[M], map[M];
- int max_ret;
- bool once = true;
-
- //数独表
- int arr[9][9] = {
- 4,0,0,9,0,0,0,0,3,
- 0,8,0,0,0,1,0,9,0,
- 0,0,0,0,2,0,7,0,0,
- 0,3,0,0,0,0,0,0,4,
- 0,0,6,7,0,0,5,0,0,
- 2,0,0,0,0,0,0,6,0,
- 0,0,7,0,3,0,6,0,0,
- 0,5,0,6,0,0,0,0,0,
- 1,0,0,0,0,9,0,0,2
- };
-
- //打印二进制格式(调试用)
- void printBinary(int num)
- {
- if (num == 0) {
- std::cout << "0";
- return;
- }
-
- int binary[32];
- int i = 0;
-
- while (num > 0) {
- binary[i] = num % 2;
- num /= 2;
- i++;
- }
-
- for (int j = i - 1; j >= 0; j--) {
- std::cout << binary[j];
- }
- }
-
- //获得可填数的编码位(截断到最靠右的1) 例如10110 lowbit后得到10
- inline int lowbit(int x)
- {
- return x & -x;
- }
-
- //打印数独表
- void print_arr(int _arr[9][9])
- {
- for (int i = 0; i < N; i++)
- {
- for (int j = 0; j < N; j++)
- {
- std::cout << _arr[i][j];
- }
- std::cout << std::endl;
- }
-
- std::cout << std::endl;
- }
-
- //复制数独表到tmp
- void copy_arr(int tmp[][9])
- {
- for (int i = 0; i < N; i++)
- {
- for (int j = 0; j < N; j++)
- {
- tmp[i][j] = arr[i][j];
- }
- }
-
- std::cout << std::endl;
- }
-
-
-
- //获取可填数据 col,row,cell经过位运算可得到一串二进制数字,二进制的1代表可以填进数独的数字
- int getmask(int x, int y)
- {
- //printBinary(row[x]);
- //std::cout << " ";
-
- //printBinary(col[y]);
- //std::cout << " ";
-
- //printBinary(cell[x/3][y/3] );
- //std::cout << " ";
-
- //printBinary(col[y] & row[x] & cell[x / 3][y / 3]);
-
- return col[y] & row[x] & cell[x / 3][y / 3];
- }
-
- //填数字
- void draw(int _arr[9][9], int x, int y, int num, bool is_set)
- {
- //如果这个位置已经被填过,那么消除这个位置上的数字
- //如果没有,就设置成num
- if (is_set)
- {
- _arr[x][y] = 0;
- }
- else
- {
- _arr[x][y] = num;
- }
-
- //将数字num转化成二进制码
- int v = 1 << (num - 1);
-
- //根据这个位置是否有数字,修改 + - 的逻辑
- if (is_set)
- {
- v = -v;
- }
-
- // -v 代表此位置行,列,宫的可填数num已经填入,该行,列,宫不可再填num
- row[x] -= v;
- col[y] -= v;
- cell[x / 3][y / 3] -= v;
- }
-
- //将数组上已知数的位置、值信息做初始化记录,并记录需要填写的格子数
- int fill(int _arr[N][N])
- {
- //cnt为待填格子数
- int cnt = 0;
-
- //设置cnt,row、col、cell条件
- for (int i = 0; i < N; i++)
- {
- for (int j = 0; j < N; j++)
- {
- if (!_arr[i][j])
- {
- cnt++;
- }
- else
- {
- col[j] -= 1 << (_arr[i][j] - 1);
- row[i] -= 1 << (_arr[i][j] - 1);
- cell[i / 3][j / 3] -= 1 << (_arr[i][j] - 1);
- }
- }
- }
-
- return cnt;
- }
-
- //只需一次初始化的数组map、ones
- void _init()
- {
- //once设置成false后不再执行这个函数
- once = false;
-
- //map和ones是一个映射关系,下标(二进制)->值(十进制)
- //
- //map[10] = 2,意思是二进制为10的数十进制为2
- for (int i = 0; i < N; i++)
- {
- map[1 << i] = i + 1;
- }
-
- //ones[11] = 2,意思是二进制为11的数十进制为2
- for (int i = 0; i < M; i++)
- {
- for (int j = 0; j < N; j++)
- {
- ones[i] += i >> j & 1;
- }
- }
- }
-
- //初始化条件数组
- int init(int _arr[N][N])
- {
- //设置row,col为111111111,代表1`9都在可填写状态
- for (int i = 0; i < N; i++)
- {
- row[i] = col[i] = M - 1;
- }
-
- //在9个宫中设置值为111111111,代表1`9都在可填写状态
- for (int i = 0; i < 3; i++)
- {
- for (int j = 0; j < 3; j++)
- {
- cell[i][j] = M - 1;
- }
- }
-
- //只初始化一次
- if (once)
- {
- _init();
- }
-
- //填入数独表的已知数字,完成初始化工作。
- return fill(_arr);
- }
-
-
-
- //填数独
- bool dfs(int _arr[9][9], int cnt, int& t_ret)
- {
- //如果可填数为0,则代表已经完成数独
- if (!cnt)
- {
- return true;
- }
-
- //找出最小可选位置,x、y表示坐标,minv代表可填数
- int minv = 10;
- int x, y;
-
- //每一个为0的位置都可以通过getmask(x,y)找到一个9位的二进制数,每一个位置上的1都代表对应数字可填
- for (int i = 0; i < N; i++)
- {
- for (int j = 0; j < N; j++)
- {
- //如果状态码state中的1比minv小,则记录下该位置的xy坐标,并记录下最小可填值minv
- if (!_arr[i][j])
- {
- int state = getmask(i, j);
- if (ones[state] < minv)
- {
- minv = ones[state];
- x = i, y = j;
- //std::cout << std::endl;
- //printBinary(state);
- }
- }
- }
- }
-
- //拿到状态码
- int state = getmask(x, y);
-
- //lowbit取到可填数(从小到大),填了就从状态码中消除对应位置上的1
- for (int i = state; i; i -= lowbit(i))
- {
- //拿到二进制对应的十进制数字num
- int num = map[lowbit(i)];
- //填入num
- draw(_arr, x, y, num, false);
- //开始填数,如果已经填完数独,则打印,并记录解的数量t_ret,最大解max_ret
- if (dfs(_arr, cnt - 1, t_ret))
- {
- //print_arr(_arr);
-
- t_ret++;
- max_ret = t_ret > max_ret ? t_ret : max_ret;
- }
- //撤销填入的num
- draw(_arr, x, y, num, true);
- }
-
- //如果 i = state 的值是0,那么就代表没有数字可以填的,返回失败,并消除上一位的数字
- return false;
- }
-
- //得到所有的数组,并记录下数独的最大解
- int _getallarr(int tmp[9][9], int& time)
- {
- //将每一个已知数字的x,y坐标记录到vii
- std::vector
int, int>> vii; - for (int i = 0; i < 9; i++)
- {
- for (int j = 0; j < 9; j++)
- {
- if (arr[i][j])
- {
- vii.push_back({ i,j });
- }
- }
- }
-
- //tmp1.tmp2存要删掉的两个数
- int tmp1, tmp2;
- //记录删除的数的坐标
- int max_ret_tmp = max_ret;
- std::vector
int, int>> vpii; - //依次删除两个数,为了保护源数独,把数据传入到tmp中
- for (int i = 0; i < vii.size(); i++)
- {
- for (int j = i + 1; j < vii.size() - 1; j++)
- {
- tmp1 = tmp[vii[i].first][vii[i].second];
- tmp[vii[i].first][vii[i].second] = 0;
-
- tmp2 = tmp[vii[j].first][vii[j].second];
- tmp[vii[j].first][vii[j].second] = 0;
-
-
- //计算最大解
- int t_ret = 0;
- int cnt = init(tmp);
- dfs(tmp, cnt, t_ret);
-
- if (max_ret > max_ret_tmp)
- {
- max_ret_tmp = max_ret;
- if (vpii.size() == 2)
- {
- vpii.erase(vpii.begin(), vpii.end());
- }
- vpii.push_back(vii[i]);
- vpii.push_back(vii[j]);
- }
-
- //还原删除的数
- tmp[vii[i].first][vii[i].second] = tmp1;
- tmp[vii[j].first][vii[j].second] = tmp2;
- }
- }
-
- std::cout << "删除的坐标是:(" << vpii[0].first << vpii[0].second << ") && (" << vpii[1].first << vpii[1].second << ")" << std::endl;
- return max_ret;
- }
-
- //计算最大解
- int getMaxRet()
- {
- //time为要删的数的个数
- int time = 2;
- //tmp为临时数组
- int tmp[9][9] = { 0 };
- copy_arr(tmp);
-
- //
- return _getallarr(tmp, time);
- }
-
- int main()
- {
- int t_ret = 0;
- int cnt = init(arr);
- dfs(arr,cnt, t_ret);
- std::cout << max_ret;
- std::cout << getMaxRet();
-
- return 0;
- }
觉得写的不错的话给个三连加关注吧~