欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一天一大 lee(解数独)难度:困难-Day20200915

程序员文章站 2022-05-08 14:34:41
...

一天一大 lee(解数独)难度:困难-Day20200915

题目:

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

一天一大 lee(解数独)难度:困难-Day20200915

一个数独。

一天一大 lee(解数独)难度:困难-Day20200915

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

抛砖引玉

一天一大 lee(解数独)难度:困难-Day20200915

思路

  • 对应任意一个字符 '.'填充的单元格,记录他所在行、列、3X3 子块传下过的数组
  • 对其填充可能是数组,并且递归继续向后填充:
    • 如果填充完所有符号’.'则直接结束
    • 如果未填充完则说明填充错误,需要重置填充状态重新填充

填充数记录:

  • 行:9X9 的矩阵 line[i][k],
    • i 为行索引;
    • k 是行内出现过的数字(恢复到 board 内元素需要+1);
    • 值是否出现,出现过 true
  • 列:9X9 的矩阵 column[i][k],
    • i 为列索引;
    • k 是行内出现过的数字(恢复到 board 内元素需要+1);
    • 值是否出现,出现过 true
  • 子块:3X3 的矩阵,内存放长度为 9 的数组 block[i][j][k],
    • i 为行索引;
    • j 为列索引;
    • k 是行内出现过的数字(恢复到 board 内元素需要+1);
    • 值是否出现,出现过 true
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
  let line = Array.from({ length: 9 }, () => Array(9)),
    column = Array.from({ length: 9 }, () => Array(9)),
    // 3x3  宫
    block = Array.from({ length: 3 }, () => Array(3)),
    // 任意一种组合满足要求,终止递归
    isEnd = false,
    // 待填充的坐标
    spaces = []
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      block[i][j] = Array(9)
    }
  }
  // 初始化行、列、子块数据
  for (let i = 0; i < 9; ++i) {
    for (let j = 0; j < 9; ++j) {
      if (board[i][j] == '.') {
        spaces.push([i, j])
      } else {
        // 注意:数字是1-9,校验的行、列、子块数据索引是0-8,所以标记时值需要-1
        let k = board[i][j] - 1,
          // 子块坐标
          x = parseInt(i / 3, 10),
          y = parseInt(j / 3, 10)
        line[i][k] = true
        column[j][k] = true
        block[x][y][k] = true
      }
    }
  }

  dfs(board, 0)

  function dfs(board, index) {
    if (index == spaces.length) {
      isEnd = true
      return
    }
    // 递归这个填充board中的字符 '.'
    let [i, j] = spaces[index]
    for (let k = 0; k < 9 && !isEnd; ++k) {
      let x = parseInt(i / 3, 10),
        y = parseInt(j / 3, 10)
      // 行内、列内、子块内无当前枚举数字则填充
      if (!line[i][k] && !column[j][k] && !block[x][y][k]) {
        line[i][k] = true
        column[j][k] = true
        block[x][y][k] = true
        board[i][j] = k + 1
        // 递归填充下一个,如果递归为遇到终止逻辑则说明本地填充错误
        dfs(board, index + 1)
        // 将填充状态恢复到未填充
        line[i][k] = false
        column[j][k] = false
        block[x][y][k] = false
      }
    }
  }
}

博客: 小书童博客

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言

一天一大 lee(解数独)难度:困难-Day20200915