灯的个人博客

forever young,forever weeping.

0%

有效的数独

发表于 更新于 分类于

题目

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
    数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。

题解

  • 暴力解法，用set存数据看是否有重复的
  • 难点在于 方块3*3的计算公式，不知道怎么推导出来的。
  • 自己写的话，需要花好长的时间去慢慢试出来这个公式
  • Math.floor(Math.floor(Math.floor(i / 3) * 3) + Math.floor(j / 3));
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    function isValidSudoku(board: string[][]): boolean {
      for (let i = 0; i < 9; i++) {
        let rowSet = new Set();
        let colSet = new Set();
        let squareSet = new Set();
        for (let j = 0; j < 9; j++) {
          if (board[i][j] != "." && rowSet.has(board[i][j])) {
            return false;
          }
          rowSet.add(board[i][j]);
          if (board[j][i] != "." && colSet.has(board[j][i])) {
            return false;
          }
          colSet.add(board[j][i]);
          let a = Math.floor(Math.floor(Math.floor(i / 3) * 3) + Math.floor(j / 3));
          let b = Math.floor((i % 3) * 3 + (j % 3));
          if (board[a][b] != "." && squareSet.has(board[a][b])) {
            return false;
          }
          squareSet.add(board[a][b]);
        }
      }
      return true;
    }

参考链接