37. 解数独

题目:https://leetcode-cn.com/problems/sudoku-solver/

代码:

折叠复制代码
  1. class Solution {
  2. /**
  3. * 空白格
  4. */
  5. private static final char BLANK = '.';
  6. /**
  7. * 零
  8. */
  9. private static final char ZERO = '0';
  10. public void solveSudoku(char[][] board) {
  11. this.solve(board, 0, 0);
  12. }
  13. /**
  14. * 从ij位置开始寻找下一个空格的位置,并且尝试填数字
  15. *
  16. * @param board
  17. * @param i
  18. * @param j
  19. * @return
  20. */
  21. private boolean solve(char[][] board, int i, int j) {
  22. //保存上一次填写数字的位置
  23. int oi = i;
  24. int oj = j;
  25. //计算下一个需要填写数字的位置
  26. while (board[i][j] != BLANK) {
  27. j++;
  28. if (j >= 9) {
  29. //从左往右本行已经到头了,换下一行
  30. i++;
  31. j = 0;
  32. }
  33. if (i >= 9) {
  34. //已经超过总行数,证明数独已经解答出来了
  35. return true;
  36. }
  37. }
  38. //尝试填入1-9的数字
  39. for (int n = 1; n <= 9; n++) {
  40. if (this.isValid(board, i, j, n)) {
  41. //有效,继续填下一位
  42. board[i][j] = (char) (ZERO + n);
  43. if (this.solve(board, i, j)) {
  44. return true;
  45. }
  46. }
  47. }
  48. //1-9都不是正确解,回滚上一位
  49. board[oi][oj] = BLANK;
  50. return false;
  51. }
  52. /**
  53. * 判断填写的数字是否有效
  54. *
  55. * @param board
  56. * @param i
  57. * @param j
  58. * @param n
  59. * @return
  60. */
  61. private boolean isValid(char[][] board, int i, int j, int n) {
  62. char cn = (char) (ZERO + n);
  63. //通过i和j计算ij所在九宫格第一位的位置
  64. int fi = i - i % 3;
  65. int fj = j - j % 3;
  66. //判断
  67. for (int k = 0; k < 9; k++) {
  68. //行
  69. if (board[i][k] == cn) {
  70. return false;
  71. }
  72. //列
  73. if (board[k][j] == cn) {
  74. return false;
  75. }
  76. //九宫格
  77. if (board[fi + k / 3][fj + k % 3] == cn) {
  78. return false;
  79. }
  80. }
  81. return true;
  82. }
  83. /**
  84. * 打印
  85. *
  86. * @param board
  87. */
  88. public void print(char[][] board) {
  89. System.out.println(" -----------------------");
  90. for (int i = 0; i < 9; i++) {
  91. System.out.print("| ");
  92. for (int j = 0; j < 9; j++) {
  93. System.out.print(board[i][j] + " ");
  94. if (j % 3 == 2) {
  95. System.out.print("| ");
  96. }
  97. }
  98. if (i % 3 == 2) {
  99. System.out.println("\n -----------------------");
  100. } else {
  101. System.out.println();
  102. }
  103. }
  104. System.out.println();
  105. }
  106. }

为了方便本地调试,上述代码中增加print方法供打印棋盘board,另附赠一个测试用例:

  1. char[][] board = new char[][]{{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

解题思路:跟51. N 皇后有点类似,也是使用递归+回溯的办法解决。

如图箭头所示,从左往右,从上往下的顺序,寻找每一个空格,并在每一个空格所在位置填入1-9的数字,通过isValid方法判断是否有效,如果有效则填入并继续解答下一个空格,否则继续尝试,都无效的情况下,表达这种情况无解,则回退上一次填入的数字即回溯。

完整的过程参考上方代码,可以本地调试并在需要的位置使用print方法打印出来直观理解。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍