算法自由之路

36. 有效的数独

难度： 中等
数组
哈希表
矩阵

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

  • 数字  1-9  在每一行只能出现一次。
  • 数字  1-9  在每一列只能出现一次。
  • 数字  1-9  在每一个以粗实线分隔的  3x3  宫内只能出现一次。（请参考示例图）

注意：

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

示例

解法

分别需要判断每一行/每一列/每一个 3*3 的粗线单元格数字没有重复的数字。

每一行， 使用 row 每一列， 使用 col 每一个 3*3 的粗线单元格， 使用 box

没有重复，使用数组去重后的长度与原始长度对比

整个数独分为 9 个粗线单元格， 下标 0-9

let boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  const row = [];
  const col = {};
  const box = {};

  for (let i = 0; i < board.length; i++) {
    row[i] = row[i] || [];

    for (let j = 0; j < board[i].length; j++) {
      col[j] = col[j] || [];

      if (board[i][j] !== ".") {
        col[j].push(board[i][j]);
        row[i].push(board[i][j]);
        let boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
        box[boxIndex] = box[boxIndex] || [];
        box[boxIndex].push(board[i][j]);
      }
    }
  }

  const hasRepeat = (data) => {
    return Object.values(data).find(
      (item) => [...new Set(item)].length !== item.length
    );
  };

  if (hasRepeat(row) || hasRepeat(col) || hasRepeat(box)) {
    return false;
  }

  return true;
};