• 【C语言】求解数独 求数独的解的个数 多解数独算法


    目录

    什么是数独? 

    数独的解法?

    数独DFS算法详解

    1. 初始化条件

    2. 填入已初始化的数独表

    3. 填数独

     4. 拓展问题

    请问删掉数独中的哪两个数可以使得数独的解最大?

     删除的是哪两个数?

     最终代码

     main函数(如何执行这些代码) 


    什么是数独? 

    数独的要求是每一行,每一列,每一宫都包括1~9,但是不能有重复数字。


    数独的解法?

    主流为深度优先搜索算法,如果使用数据结构,有舞蹈链算法,本篇介绍深度优先搜索算法。


    数独DFS算法详解

    1. 初始化条件

    我们的初始条件准备了5个,分别是row[N], col[N], cell[3][3],ones[M], map[M]

    N = 9;

    M = 111111111(二进制),511(十进制);

    1. //设置9*9数独表
    2. const int N = 9;
    3. //设置mask长度 M的二进制:111111111,从右到左分别表示1 2 3 4 5 6 7 8 9
    4. const int M = 1 << N;
    5. //row、col、cell分别表示行、列、宫可填写数的编码
    6. //ones、map是一个映射关系,ones表示有多少个1,map表示9位二进制的1代表的数字
    7. int row[N], col[N], cell[3][3];
    8. int ones[M], map[M];
    9. //数独表
    10. int arr[9][9] = {
    11. 4,0,0,9,0,0,0,0,3,
    12. 0,8,0,0,0,1,0,9,0,
    13. 0,0,0,0,2,0,7,0,0,
    14. 0,3,0,0,0,0,0,0,4,
    15. 0,0,6,7,0,0,5,0,0,
    16. 2,0,0,0,0,0,0,6,0,
    17. 0,0,7,0,3,0,6,0,0,
    18. 0,5,0,6,0,0,0,0,0,
    19. 1,0,0,0,0,9,0,0,2
    20. };

    那么M是用来干嘛的?

    我使用了二进制来优化DFS算法,在下图中只有7不能填,因为mask为0。

        map和ones是一个映射关系,下标(二进制)->值(十进制)
        
        map[10] = 2,意思是二进制为10的数十进制为2 

        ones[11] = 2,意思是二进制为11的数十进制为2

    下面初始化的意思是把所有位置都设置成所有数都可填的状态。

    1. //只需一次初始化的数组map、ones
    2. void _init()
    3. {
    4. //once设置成false后不再执行这个函数
    5. once = false;
    6. //map和ones是一个映射关系,下标(二进制)->值(十进制)
    7. //
    8. //map[10] = 2,意思是二进制为10的数十进制为2
    9. for (int i = 0; i < N; i++)
    10. {
    11. map[1 << i] = i + 1;
    12. }
    13. //ones[11] = 2,意思是二进制为11的数十进制为2
    14. for (int i = 0; i < M; i++)
    15. {
    16. for (int j = 0; j < N; j++)
    17. {
    18. ones[i] += i >> j & 1;
    19. }
    20. }
    21. }
    22. //初始化条件数组
    23. int init(int _arr[N][N])
    24. {
    25. //设置row,col为111111111,代表1`9都在可填写状态
    26. for (int i = 0; i < N; i++)
    27. {
    28. row[i] = col[i] = M - 1;
    29. }
    30. //在9个宫中设置值为111111111,代表1`9都在可填写状态
    31. for (int i = 0; i < 3; i++)
    32. {
    33. for (int j = 0; j < 3; j++)
    34. {
    35. cell[i][j] = M - 1;
    36. }
    37. }
    38. //只初始化一次
    39. if (once)
    40. {
    41. _init();
    42. }
    43. //填入数独表的已知数字,完成初始化工作。
    44. return fill(_arr);
    45. }

     fill函数是干嘛的?请往下看


    2. 填入已初始化的数独表

    fill函数的作用是填入数独表中已知的数字,返回一个整形代表待填入数独表的空位。

    我们利用空位作为DFS的制约条件。

    1. //将数组上已知数的位置、值信息做初始化记录,并记录需要填写的格子数
    2. int fill(int _arr[N][N])
    3. {
    4. //cnt为待填格子数
    5. int cnt = 0;
    6. //设置cnt,row、col、cell条件
    7. for (int i = 0; i < N; i++)
    8. {
    9. for (int j = 0; j < N; j++)
    10. {
    11. if (!_arr[i][j])
    12. {
    13. cnt++;
    14. }
    15. else
    16. {
    17. col[j] -= 1 << (_arr[i][j] - 1);
    18. row[i] -= 1 << (_arr[i][j] - 1);
    19. cell[i / 3][j / 3] -= 1 << (_arr[i][j] - 1);
    20. }
    21. }
    22. }
    23. return cnt;
    24. }

     在行,列,宫对应的位置减去对应数的二进制码,这样可以把该数字在行、列、宫对应的二进制码设置为0,代表该数字在该行,该列,该宫已经不可以填写。

    可举例填写4和6,三个条件的变化,等式右边为二进制码。 

    3. 填数独

    前置有3个功能函数。

    这里说一下getmask

    因为&的特点,col & row & cell运算,如果这三个其中一个的二进制码的某个位置上为0,那么返回的计算结果的那个位置的二进制码也为0。

    draw是我们递归的灵魂,他的功能是在数组上填数,然后根据填的数修改row、col、cell。

    1. //获得可填数的编码位(截断到最靠右的1) 例如10110 lowbit后得到10
    2. inline int lowbit(int x)
    3. {
    4. return x & -x;
    5. }
    6. //获取可填数据 col,row,cell经过位运算可得到一串二进制数字,二进制的1代表可以填进数独的数字
    7. int getmask(int x, int y)
    8. {
    9. //printBinary(row[x]);
    10. //std::cout << " ";
    11. //printBinary(col[y]);
    12. //std::cout << " ";
    13. //printBinary(cell[x/3][y/3] );
    14. //std::cout << " ";
    15. //printBinary(col[y] & row[x] & cell[x / 3][y / 3]);
    16. return col[y] & row[x] & cell[x / 3][y / 3];
    17. }
    18. //填数字
    19. void draw(int _arr[9][9], int x, int y, int num, bool is_set)
    20. {
    21. //如果这个位置已经被填过,那么消除这个位置上的数字
    22. //如果没有,就设置成num
    23. if (is_set)
    24. {
    25. _arr[x][y] = 0;
    26. }
    27. else
    28. {
    29. _arr[x][y] = num;
    30. }
    31. //将数字num转化成二进制码
    32. int v = 1 << (num - 1);
    33. //根据这个位置是否有数字,修改 + - 的逻辑
    34. if (is_set)
    35. {
    36. v = -v;
    37. }
    38. // -v 代表此位置行,列,宫的可填数num已经填入,该行,列,宫不可再填num
    39. row[x] -= v;
    40. col[y] -= v;
    41. cell[x / 3][y / 3] -= v;
    42. }

    我们 按照标题2. 的逻辑对数独表和三个条件进行增、改,然后搜索。

    t_ret表示解的数量。max_ret表示最大解。

    位置优化:通过两层循环,找出可填数最少的位置。

    1. //填数独
    2. bool dfs(int _arr[9][9], int cnt, int& t_ret)
    3. {
    4. //如果可填数为0,则代表已经完成数独
    5. if (!cnt)
    6. {
    7. return true;
    8. }
    9. //找出最小可选位置,x、y表示坐标,minv代表可填数
    10. int minv = 10;
    11. int x, y;
    12. //每一个为0的位置都可以通过getmask(x,y)找到一个9位的二进制数,每一个位置上的1都代表对应数字可填
    13. for (int i = 0; i < N; i++)
    14. {
    15. for (int j = 0; j < N; j++)
    16. {
    17. //如果状态码state中的1比minv小,则记录下该位置的xy坐标,并记录下最小可填值minv
    18. if (!_arr[i][j])
    19. {
    20. int state = getmask(i, j);
    21. if (ones[state] < minv)
    22. {
    23. minv = ones[state];
    24. x = i, y = j;
    25. //std::cout << std::endl;
    26. //printBinary(state);
    27. }
    28. }
    29. }
    30. }
    31. //拿到状态码
    32. int state = getmask(x, y);
    33. //lowbit取到可填数(从小到大),填了就从状态码中消除对应位置上的1
    34. for (int i = state; i; i -= lowbit(i))
    35. {
    36. //拿到二进制对应的十进制数字num
    37. int num = map[lowbit(i)];
    38. //填入num
    39. draw(_arr, x, y, num, false);
    40. //开始填数,如果已经填完数独,则打印,并记录解的数量t_ret,最大解max_ret
    41. if (dfs(_arr, cnt - 1, t_ret))
    42. {
    43. //print_arr(_arr);
    44. t_ret++;
    45. max_ret = t_ret > max_ret ? t_ret : max_ret;
    46. }
    47. //撤销填入的num
    48. draw(_arr, x, y, num, true);
    49. }
    50. //如果 i = state 的值是0,那么就代表没有数字可以填的,返回失败,并消除上一位的数字
    51. return false;
    52. }

     4. 拓展问题

    请问删掉数独中的哪两个数可以使得数独的解最大?

     删除的是哪两个数?

    函数的逻辑是删除两个数,然后进行DFS,再然后把删除的数填回去,继续删除。

    DFS进行之前,我们都初始化row,col,cell三个条件,这样能保证正常递归。

     这里我们使用vector和pair(C++),也就是数组和键值对的数据结构。

    first代表x坐标,second代表y坐标。

    1. //得到所有的数组,并记录下数独的最大解
    2. int _getallarr(int tmp[9][9], int& time)
    3. {
    4. //将每一个已知数字的x,y坐标记录到vii
    5. std::vectorint, int>> vii;
    6. for (int i = 0; i < 9; i++)
    7. {
    8. for (int j = 0; j < 9; j++)
    9. {
    10. if (arr[i][j])
    11. {
    12. vii.push_back({ i,j });
    13. }
    14. }
    15. }
    16. //tmp1.tmp2存要删掉的两个数
    17. int tmp1, tmp2;
    18. //记录删除的数的坐标
    19. int max_ret_tmp = max_ret;
    20. //vpii的每一个元素都是一对坐标,我们只保留2对坐标
    21. std::vectorint, int>> vpii;
    22. //依次删除两个数,为了保护源数独,把数据传入到tmp中
    23. for (int i = 0; i < vii.size(); i++)
    24. {
    25. for (int j = i + 1; j < vii.size() - 1; j++)
    26. {
    27. //存下要删掉的数,搜索完还原。
    28. tmp1 = tmp[vii[i].first][vii[i].second];
    29. tmp[vii[i].first][vii[i].second] = 0;
    30. tmp2 = tmp[vii[j].first][vii[j].second];
    31. tmp[vii[j].first][vii[j].second] = 0;
    32. //计算最大解
    33. int t_ret = 0;
    34. int cnt = init(tmp);
    35. dfs(tmp, cnt, t_ret);
    36. //如果最大解的数值发生变化,那么记录下该点的坐标。
    37. if (max_ret > max_ret_tmp)
    38. {
    39. //此处还可做优化,比如说把2改成time,删time个数的最大解是哪三个?
    40. max_ret_tmp = max_ret;
    41. if (vpii.size() == 2)
    42. {
    43. vpii.erase(vpii.begin(), vpii.end());
    44. }
    45. vpii.push_back(vii[i]);
    46. vpii.push_back(vii[j]);
    47. }
    48. //还原删除的数
    49. tmp[vii[i].first][vii[i].second] = tmp1;
    50. tmp[vii[j].first][vii[j].second] = tmp2;
    51. }
    52. }
    53. std::cout << "删除的坐标是:(" << vpii[0].first << vpii[0].second << ") && (" << vpii[1].first << vpii[1].second << ")" << std::endl;
    54. return max_ret;
    55. }
    56. //计算最大解
    57. int getMaxRet()
    58. {
    59. //time为要删的数的个数
    60. int time = 2;
    61. //tmp为临时数组
    62. int tmp[9][9] = { 0 };
    63. copy_arr(tmp);
    64. //
    65. return _getallarr(tmp, time);
    66. }

     最终代码

    1. //设置9*9数独表
    2. const int N = 9;
    3. //设置mask长度 M的二进制:111111111,从右到左分别表示1 2 3 4 5 6 7 8 9
    4. const int M = 1 << N;
    5. //row、col、cell分别表示行、列、宫可填写数的编码
    6. //ones、map是一个映射关系,ones表示有多少个1,map表示9位二进制的1代表的数字
    7. //max_ret表示数独的最大解
    8. //once 卡关,ones和map数组只需初始化一次
    9. int row[N], col[N], cell[3][3];
    10. int ones[M], map[M];
    11. int max_ret;
    12. bool once = true;
    13. //数独表
    14. int arr[9][9] = {
    15. 4,0,0,9,0,0,0,0,3,
    16. 0,8,0,0,0,1,0,9,0,
    17. 0,0,0,0,2,0,7,0,0,
    18. 0,3,0,0,0,0,0,0,4,
    19. 0,0,6,7,0,0,5,0,0,
    20. 2,0,0,0,0,0,0,6,0,
    21. 0,0,7,0,3,0,6,0,0,
    22. 0,5,0,6,0,0,0,0,0,
    23. 1,0,0,0,0,9,0,0,2
    24. };
    25. //打印二进制格式(调试用)
    26. void printBinary(int num)
    27. {
    28. if (num == 0) {
    29. std::cout << "0";
    30. return;
    31. }
    32. int binary[32];
    33. int i = 0;
    34. while (num > 0) {
    35. binary[i] = num % 2;
    36. num /= 2;
    37. i++;
    38. }
    39. for (int j = i - 1; j >= 0; j--) {
    40. std::cout << binary[j];
    41. }
    42. }
    43. //获得可填数的编码位(截断到最靠右的1) 例如10110 lowbit后得到10
    44. inline int lowbit(int x)
    45. {
    46. return x & -x;
    47. }
    48. //打印数独表
    49. void print_arr(int _arr[9][9])
    50. {
    51. for (int i = 0; i < N; i++)
    52. {
    53. for (int j = 0; j < N; j++)
    54. {
    55. std::cout << _arr[i][j];
    56. }
    57. std::cout << std::endl;
    58. }
    59. std::cout << std::endl;
    60. }
    61. //复制数独表到tmp
    62. void copy_arr(int tmp[][9])
    63. {
    64. for (int i = 0; i < N; i++)
    65. {
    66. for (int j = 0; j < N; j++)
    67. {
    68. tmp[i][j] = arr[i][j];
    69. }
    70. }
    71. std::cout << std::endl;
    72. }
    73. //获取可填数据 col,row,cell经过位运算可得到一串二进制数字,二进制的1代表可以填进数独的数字
    74. int getmask(int x, int y)
    75. {
    76. //printBinary(row[x]);
    77. //std::cout << " ";
    78. //printBinary(col[y]);
    79. //std::cout << " ";
    80. //printBinary(cell[x/3][y/3] );
    81. //std::cout << " ";
    82. //printBinary(col[y] & row[x] & cell[x / 3][y / 3]);
    83. return col[y] & row[x] & cell[x / 3][y / 3];
    84. }
    85. //填数字
    86. void draw(int _arr[9][9], int x, int y, int num, bool is_set)
    87. {
    88. //如果这个位置已经被填过,那么消除这个位置上的数字
    89. //如果没有,就设置成num
    90. if (is_set)
    91. {
    92. _arr[x][y] = 0;
    93. }
    94. else
    95. {
    96. _arr[x][y] = num;
    97. }
    98. //将数字num转化成二进制码
    99. int v = 1 << (num - 1);
    100. //根据这个位置是否有数字,修改 + - 的逻辑
    101. if (is_set)
    102. {
    103. v = -v;
    104. }
    105. // -v 代表此位置行,列,宫的可填数num已经填入,该行,列,宫不可再填num
    106. row[x] -= v;
    107. col[y] -= v;
    108. cell[x / 3][y / 3] -= v;
    109. }
    110. //将数组上已知数的位置、值信息做初始化记录,并记录需要填写的格子数
    111. int fill(int _arr[N][N])
    112. {
    113. //cnt为待填格子数
    114. int cnt = 0;
    115. //设置cnt,row、col、cell条件
    116. for (int i = 0; i < N; i++)
    117. {
    118. for (int j = 0; j < N; j++)
    119. {
    120. if (!_arr[i][j])
    121. {
    122. cnt++;
    123. }
    124. else
    125. {
    126. col[j] -= 1 << (_arr[i][j] - 1);
    127. row[i] -= 1 << (_arr[i][j] - 1);
    128. cell[i / 3][j / 3] -= 1 << (_arr[i][j] - 1);
    129. }
    130. }
    131. }
    132. return cnt;
    133. }
    134. //只需一次初始化的数组map、ones
    135. void _init()
    136. {
    137. //once设置成false后不再执行这个函数
    138. once = false;
    139. //map和ones是一个映射关系,下标(二进制)->值(十进制)
    140. //
    141. //map[10] = 2,意思是二进制为10的数十进制为2
    142. for (int i = 0; i < N; i++)
    143. {
    144. map[1 << i] = i + 1;
    145. }
    146. //ones[11] = 2,意思是二进制为11的数十进制为2
    147. for (int i = 0; i < M; i++)
    148. {
    149. for (int j = 0; j < N; j++)
    150. {
    151. ones[i] += i >> j & 1;
    152. }
    153. }
    154. }
    155. //初始化条件数组
    156. int init(int _arr[N][N])
    157. {
    158. //设置row,col为111111111,代表1`9都在可填写状态
    159. for (int i = 0; i < N; i++)
    160. {
    161. row[i] = col[i] = M - 1;
    162. }
    163. //在9个宫中设置值为111111111,代表1`9都在可填写状态
    164. for (int i = 0; i < 3; i++)
    165. {
    166. for (int j = 0; j < 3; j++)
    167. {
    168. cell[i][j] = M - 1;
    169. }
    170. }
    171. //只初始化一次
    172. if (once)
    173. {
    174. _init();
    175. }
    176. //填入数独表的已知数字,完成初始化工作。
    177. return fill(_arr);
    178. }
    179. //填数独
    180. bool dfs(int _arr[9][9], int cnt, int& t_ret)
    181. {
    182. //如果可填数为0,则代表已经完成数独
    183. if (!cnt)
    184. {
    185. return true;
    186. }
    187. //找出最小可选位置,x、y表示坐标,minv代表可填数
    188. int minv = 10;
    189. int x, y;
    190. //每一个为0的位置都可以通过getmask(x,y)找到一个9位的二进制数,每一个位置上的1都代表对应数字可填
    191. for (int i = 0; i < N; i++)
    192. {
    193. for (int j = 0; j < N; j++)
    194. {
    195. //如果状态码state中的1比minv小,则记录下该位置的xy坐标,并记录下最小可填值minv
    196. if (!_arr[i][j])
    197. {
    198. int state = getmask(i, j);
    199. if (ones[state] < minv)
    200. {
    201. minv = ones[state];
    202. x = i, y = j;
    203. //std::cout << std::endl;
    204. //printBinary(state);
    205. }
    206. }
    207. }
    208. }
    209. //拿到状态码
    210. int state = getmask(x, y);
    211. //lowbit取到可填数(从小到大),填了就从状态码中消除对应位置上的1
    212. for (int i = state; i; i -= lowbit(i))
    213. {
    214. //拿到二进制对应的十进制数字num
    215. int num = map[lowbit(i)];
    216. //填入num
    217. draw(_arr, x, y, num, false);
    218. //开始填数,如果已经填完数独,则打印,并记录解的数量t_ret,最大解max_ret
    219. if (dfs(_arr, cnt - 1, t_ret))
    220. {
    221. //print_arr(_arr);
    222. t_ret++;
    223. max_ret = t_ret > max_ret ? t_ret : max_ret;
    224. }
    225. //撤销填入的num
    226. draw(_arr, x, y, num, true);
    227. }
    228. //如果 i = state 的值是0,那么就代表没有数字可以填的,返回失败,并消除上一位的数字
    229. return false;
    230. }
    231. //得到所有的数组,并记录下数独的最大解
    232. int _getallarr(int tmp[9][9], int& time)
    233. {
    234. //将每一个已知数字的x,y坐标记录到vii
    235. std::vectorint, int>> vii;
    236. for (int i = 0; i < 9; i++)
    237. {
    238. for (int j = 0; j < 9; j++)
    239. {
    240. if (arr[i][j])
    241. {
    242. vii.push_back({ i,j });
    243. }
    244. }
    245. }
    246. //tmp1.tmp2存要删掉的两个数
    247. int tmp1, tmp2;
    248. //记录删除的数的坐标
    249. int max_ret_tmp = max_ret;
    250. std::vectorint, int>> vpii;
    251. //依次删除两个数,为了保护源数独,把数据传入到tmp中
    252. for (int i = 0; i < vii.size(); i++)
    253. {
    254. for (int j = i + 1; j < vii.size() - 1; j++)
    255. {
    256. tmp1 = tmp[vii[i].first][vii[i].second];
    257. tmp[vii[i].first][vii[i].second] = 0;
    258. tmp2 = tmp[vii[j].first][vii[j].second];
    259. tmp[vii[j].first][vii[j].second] = 0;
    260. //计算最大解
    261. int t_ret = 0;
    262. int cnt = init(tmp);
    263. dfs(tmp, cnt, t_ret);
    264. if (max_ret > max_ret_tmp)
    265. {
    266. max_ret_tmp = max_ret;
    267. if (vpii.size() == 2)
    268. {
    269. vpii.erase(vpii.begin(), vpii.end());
    270. }
    271. vpii.push_back(vii[i]);
    272. vpii.push_back(vii[j]);
    273. }
    274. //还原删除的数
    275. tmp[vii[i].first][vii[i].second] = tmp1;
    276. tmp[vii[j].first][vii[j].second] = tmp2;
    277. }
    278. }
    279. std::cout << "删除的坐标是:(" << vpii[0].first << vpii[0].second << ") && (" << vpii[1].first << vpii[1].second << ")" << std::endl;
    280. return max_ret;
    281. }
    282. //计算最大解
    283. int getMaxRet()
    284. {
    285. //time为要删的数的个数
    286. int time = 2;
    287. //tmp为临时数组
    288. int tmp[9][9] = { 0 };
    289. copy_arr(tmp);
    290. //
    291. return _getallarr(tmp, time);
    292. }

     main函数(如何执行这些代码) 

    1. int main()
    2. {
    3. int t_ret = 0;
    4. int cnt = init(arr);
    5. dfs(arr,cnt, t_ret);
    6. std::cout << max_ret;
    7. std::cout << getMaxRet();
    8. return 0;
    9. }

    觉得写的不错的话给个三连加关注吧~

  • 相关阅读:
    React技术栈 --》组件对比和评论列表案例 ## Day4
    CSDN竞赛第四期季军 解题思路及参赛经历分享
    神经网络和深度学习-均方误差Mean Square Error
    排序——交换排序
    Centos修改系统时间
    【Kafka】——Producer
    Oracle:常用函数CASE WHEN,DECODE,NVL,SUBSTR,listagg,instr,to_char,to_number
    anaconda安装python 3.11
    RustGUI学习(iced)之小部件(二):如何使用滑动条部件
    【Vue基础四】Vue检测数据改变的原理
  • 原文地址:https://blog.csdn.net/GMfengyi/article/details/133760088