leetcode 36. Valid Sudoku | 37. Sudoku Solver（数独）

刺骨的言语ヽ痛彻心扉 2022-09-07 06:14 266阅读 0赞

36. Valid Sudoku

https://leetcode.com/problems/valid-sudoku/
在这里插入图片描述

题解

  1. class Solution { 
  2.     public boolean isValidSudoku(char[][] board) { 
  3.         boolean[][] rows = new boolean[9][9];
  4.         boolean[][] cols = new boolean[9][9];
  5.         boolean[][] grids = new boolean[9][9];
  6.         for (int i = 0; i < 9; i++) { 
  7.             for (int j = 0; j < 9; j++) { 
  8.                 if (board[i][j] == '.') continue;
  9.                 int n = board[i][j] - '1';
  10.                 int g = 3 * (i / 3) + (j / 3);
  11.                 if (rows[i][n] || cols[j][n] || grids[g][n]) return false;
  12.                 rows[i][n] = true;
  13.                 cols[j][n] = true;
  14.                 grids[g][n] = true;
  15.             }
  16.         }
  17.         return true;
  18.     }
  19. }

37. Sudoku Solver

https://leetcode.com/problems/sudoku-solver/
在这里插入图片描述

题解

思路是：暴力 DFS 无任何记忆，每走到下一个空闲格子，遍历放进 1 ~ 9 看是否可行。如果 1 ~ 9 都不行，回溯返回上一级。

  1. class Solution { 
  2.     public void solveSudoku(char[][] board) { 
  3.         boolean[][] rows = new boolean[9][9];
  4.         boolean[][] cols = new boolean[9][9];
  5.         boolean[][] grids = new boolean[9][9];
  6.         int filled = 0;
  7.         for (int i = 0; i < 9; i++) { 
  8.             for (int j = 0; j < 9; j++) { 
  9.                 if (board[i][j] != '.') { 
  10.                     int n = board[i][j] - '1';
  11.                     int g = 3 * (i / 3) + (j / 3);
  12.                     rows[i][n] = true;
  13.                     cols[j][n] = true;
  14.                     grids[g][n] = true;
  15.                     filled++;
  16.                 }
  17.             }
  18.         }
  20.         for (int i = 0; i < 9; i++) { 
  21.             for (int j = 0; j < 9; j++) { 
  22.                 if (board[i][j] == '.') { 
  23.                     for (int num = 1; num <= 9; num++) { 
  24.                         if (tryFill(board, i, j, num, rows, cols, grids, filled)) return;
  25.                     }
  26.                 }
  27.             }
  28.         }
  29.     }
  31.     public boolean tryFill(char[][] board, int i, int j, int value, boolean[][] rows, boolean[][] cols, boolean[][] grids, int filled) { 
  32.         int n = value - 1;
  33.         int g = 3 * (i / 3) + (j / 3); // 九宫格的index
  34.         if (rows[i][n] || cols[j][n] || grids[g][n]) {  // 当前数字冲突
  35.             return false;
  36.         } else {  // 当前数字有效
  37.             board[i][j] = (char) ('0' + value);
  38.             rows[i][n] = true;
  39.             cols[j][n] = true;
  40.             grids[g][n] = true;
  41.             if (++filled == 9 * 9) return true;
  42.             // 填充下一个位置
  43.             for (int ii = 0; ii < 9; ii++) { 
  44.                 for (int jj = 0; jj < 9; jj++) { 
  45.                     if (board[ii][jj] == '.') {  // 首个下一个位置
  46.                         for (int v = 1; v <= 9; v++) { 
  47.                             if (tryFill(board, ii, jj, v, rows, cols, grids, filled)) return true;
  48.                         }
  49.                         // value=1~9都不能填充下一个位置，直接返回
  50.                         board[i][j] = '.';
  51.                         rows[i][n] = false;
  52.                         cols[j][n] = false;
  53.                         grids[g][n] = false;
  54.                         return false;
  55.                     }
  56.                 }
  57.             }
  58.         }
  59.         return false;
  60.     }
  61. }

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，266人围观）

还没有评论，来说两句吧...

相关阅读