37. 解数独

这一题是回溯的思路，在做到网易的笔试的时候是这一题的进阶，先说一下这一题的两种思路

回溯

回溯的基本思路:

  1. 三个数组，分别存储行列宫中目前已有的元素
  2. 遍历当前数组，将已有的元素填入进去，三个数组初始化为存在该值为true
  3. 再次遍历数组，回溯的进行插入
    1. 对于每一个位置，有9种可选数据，我们的选择就是，试插
    2. 如果在插入某个数据破坏了不重复性的时候，回溯到3.a，再次试插
    3. 插入满了所有元素，那么就返回答案

填空类 - 图1
代码如下，使用到了三个小技巧：

  1. 宫的编码方式：let p_id = i/3 * 3 + j / 3;
  2. 位置的编码方式，或者说一个数字存储二维数组坐标: let i = n / 9;

let j = n % 9;

  1. 获取到数字的ASCII码：(0 as u8 + 0x30) as char

    1. /// 37. 解数独:一个9阶空缺数量高的树
    2. pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
    3.  // 三个数组存储信息
    4.  let mut line_used = vec![vec![false; 9]; 9];
    5.  let mut row_used = vec![vec![false; 9]; 9];
    6.  let mut palace_used = vec![vec![false; 9]; 9];
    8.  for i in 0..board.len() {
    9.      for j in 0..board[0].len() {
    10.          if board[i][j] == '.' {
    11.              continue;
    12.          }else {
    13.              // 注意我们实际存储的是0-8，对应1-9使用过的数
    14.              let num = (board[i][j] as usize) - ('1' as usize);
    15.              // 注意这一步对宫的编码：最后算出来就是0-9的宫编号
    16.              let p_id = i/3 * 3 + j / 3;
    17.              line_used[i][num] = true;
    18.              row_used[j][num] = true;
    19.              palace_used[p_id][num] = true;
    20.          }
    21.      }
    22.  }
    23.  Self::dfs_ss(board, &mut line_used, &mut row_used, &mut palace_used, 0);
    24. }
    25. fn dfs_ss(board: &mut Vec<Vec<char>>, line_used: &mut Vec<Vec<bool>>,
    26.        row_used: &mut Vec<Vec<bool>>, palace_used: &mut Vec<Vec<bool>>,
    27.        n: usize) -> bool
    28. {
    29.  if n == 81 {
    30.      return true;
    31.  }
    32.  // 这一步解码坐标信息很关键！！！
    33.  let i = n / 9;
    34.  let j = n % 9;
    35.  if board[i][j] != '.' {
    36.      return Self::dfs_ss(board, line_used, row_used, palace_used, n + 1);
    37.  }
    38.  let p_id = i/3 * 3 + j / 3;
    40.  // 高度n问题，找到了当前的空缺点：
    41.  for num in 0..9 {
    42.      // 高度n问题，num阶
    43.      if line_used[i][num] || row_used[j][num] || palace_used[p_id][num] {
    44.          continue
    45.      }
    46.      line_used[i][num] = true;
    47.      row_used[j][num] = true;
    48.      palace_used[p_id][num] = true;
    49.      // 转换的方法
    50.      board[i][j] = (num as u8 + 0x31) as char;
    51.      // 如果高度n+1问题，九种可能全部失败，则回溯重新找高度n问题
    52.      match Self::dfs_ss(board, line_used, row_used, palace_used, n + 1) {
    53.          true => { return true; }
    54.          false => {
    55.              line_used[i][num] = false;
    56.              row_used[j][num] = false;
    57.              palace_used[p_id][num] = false;
    58.              // board[i][j] = '.'; 不用在这里重置，因为此时在高度n问题，只是走到num+1阶
    59.          }
    60.      }
    61.  }
    62.  // 当运行到这里的时候，说明高度n问题9个阶都找过并失败了，因此需
    63.  // 要回溯上去，使得n-1问题选择下一个num，需要把此时的节点重新置
    64.  // 回.，否则会被高度n问题的判断给清除掉，这个点忽视了
    65.  board[i][j] = '.';
    66.  false
    67. }