36、有效的数独

;(function () {
  /**
     * 36. 有效的数独
     * 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
     * 注意：
        一个有效的数独（部分已被填充）不一定是可解的。
        只需要根据以上规则，验证已经填入的数字是否有效即可。
        空白格用 '.' 表示。
     * ------------------------------------------------
     * 输入：board = 
        [["5","3",".",".","7",".",".",".","."]
        ,["6",".",".","1","9","5",".",".","."]
        ,[".","9","8",".",".",".",".","6","."]
        ,["8",".",".",".","6",".",".",".","3"]
        ,["4",".",".","8",".","3",".",".","1"]
        ,["7",".",".",".","2",".",".",".","6"]
        ,[".","6",".",".",".",".","2","8","."]
        ,[".",".",".","4","1","9",".",".","5"]
        ,[".",".",".",".","8",".",".","7","9"]]
     * 输出: true
     * 
     * 输入：board = 
        [["8","3",".",".","7",".",".",".","."]
        ,["6",".",".","1","9","5",".",".","."]
        ,[".","9","8",".",".",".",".","6","."]
        ,["8",".",".",".","6",".",".",".","3"]
        ,["4",".",".","8",".","3",".",".","1"]
        ,["7",".",".",".","2",".",".",".","6"]
        ,[".","6",".",".",".",".","2","8","."]
        ,[".",".",".","4","1","9",".",".","5"]
        ,[".",".",".",".","8",".",".","7","9"]]
     * 输出: false
     * ----------------------------------------
     * 提示：
        board.length == 9
        board[i].length == 9
        board[i][j] 是一位数字（1-9）或者 '.'

        行：row
        列：column
     */
  function isValidSudoku(board: string[][]): boolean {
    // 方法一
    // let bool = true
    // // 临时数组：保存三个来源的数组数据（1. 原 board 的每行；2. 原 board 的每列；3.原 board 的 3x3 宫内数据组成的数组）
    // let tempBoards: string[][] = [];
    // // 1. 插入每行数据
    // board.forEach(x => {
    //     tempBoards.push([...x])
    // })
    // // 2. 插入每列数据
    // // 旋转矩阵
    // let rotateBoard = Array.from(board);
    // let length = rotateBoard.length;
    // for (let i = 0; i < length; ++i) {
    //     for (let j = i + 1; j < length; ++j) {
    //         let temp = rotateBoard[i][j];
    //         rotateBoard[i][j] = rotateBoard[j][i];
    //         rotateBoard[j][i] = temp;
    //     }
    // }
    // rotateBoard.forEach(x => {
    //     tempBoards.push(x)
    // })
    // // 3. 插入3x3 宫内数据
    // let temp3x3BoardBase: number[][] = [];
    // let temp3x3Board: string[][] = new Array(9).fill(0).map(() => new Array());
    // board.forEach((arr, k) => {
    //     arr.forEach((item, index) => {
    //         // 找到 3x3 的基点（即每个九宫格的原点位置）
    //         k % 3 === 0 && index % 3 === 0 ? temp3x3BoardBase.push([k, index]) : null;
    //     })
    // })
    // temp3x3BoardBase.forEach((x, k) => {
    //     let r = x[0];
    //     let c = x[1];
    //     for(let i = r; i < r + 3; i++) {
    //         for(let j = c; j < c + 3; j++) {
    //             temp3x3Board[k].push(board[i][j])
    //         }
    //     }
    // })
    // temp3x3Board.forEach(x => {
    //     tempBoards.push(x)
    // })
    // // 核心： 判断数独
    // tempBoards.forEach(x => {
    //     let nums = x.filter(item => item !== '.');
    //     let len = nums.length;
    //     let numsAfterSet = [...Array.from(new Set(nums))];
    //     let newLen = numsAfterSet.length;
    //     // 相等，说明没有重复的数字
    //     len === newLen ? null : bool = false;
    // })
    // return bool

    // 方法二：官方方法
    const rows = new Array(9).fill(0).map(() => new Array(9).fill(0))
    const columns = new Array(9).fill(0).map(() => new Array(9).fill(0))
    const subboxes = new Array(3)
      .fill(0)
      .map(() => new Array(3).fill(0).map(() => new Array(9).fill(0)))
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        const c = board[i][j]
        if (c !== '.') {
          const index = +c - 1
          rows[i][index]++
          columns[j][index]++
          subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index]++
          if (
            rows[i][index] > 1 ||
            columns[j][index] > 1 ||
            subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index] > 1
          ) {
            return false
          }
        }
      }
    }
    return true

    // 方法三
    // todo...
  }
  const boardArr = [
    ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
    ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
    ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
    ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
    ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
    ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
    ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
    ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
    ['.', '.', '.', '.', '8', '.', '.', '7', '9']
  ]
  const boardArr2 = [
    ['7', '.', '.', '.', '4', '.', '.', '.', '.'],
    ['.', '.', '.', '8', '6', '5', '.', '.', '.'],
    ['.', '1', '.', '2', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '9', '.', '.', '.'],
    ['.', '.', '.', '.', '5', '.', '5', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '2', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.', '.']
  ]
  // console.log(isValidSudoku(boardArr))
  console.log(isValidSudoku(boardArr2))
})()