今日kata

原始题目如下:(4kyu)
Write a function validSolution/ValidateSolution/validsolution() that accepts a 2D array representing a Sudoku board, and returns true if it is a valid solution, or false otherwise. The cells of the sudoku board may also contain 0's, which will represent empty cells. Boards containing one or more zeroes are considered to be invalid solutions.
The board is always 9 cells by 9 cells, and every cell only contains integers from 0 to 9.

翻译:
写一个数独验证，检查array中的元素是否符合数独规则。

范例:

validSolution([
  [5, 3, 4, 6, 7, 8, 9, 1, 2],
  [6, 7, 2, 1, 9, 5, 3, 4, 8],
  [1, 9, 8, 3, 4, 2, 5, 6, 7],
  [8, 5, 9, 7, 6, 1, 4, 2, 3],
  [4, 2, 6, 8, 5, 3, 7, 9, 1],
  [7, 1, 3, 9, 2, 4, 8, 5, 6],
  [9, 6, 1, 5, 3, 7, 2, 8, 4],
  [2, 8, 7, 4, 1, 9, 6, 3, 5],
  [3, 4, 5, 2, 8, 6, 1, 7, 9]
]); // => true

validSolution([
  [5, 3, 4, 6, 7, 8, 9, 1, 2], 
  [6, 7, 2, 1, 9, 0, 3, 4, 8],
  [1, 0, 0, 3, 4, 2, 5, 6, 0],
  [8, 5, 9, 7, 6, 1, 0, 2, 0],
  [4, 2, 6, 8, 5, 3, 7, 9, 1],
  [7, 1, 3, 9, 2, 4, 8, 5, 6],
  [9, 0, 1, 5, 3, 7, 2, 1, 4],
  [2, 8, 7, 4, 1, 9, 6, 3, 5],
  [3, 0, 0, 4, 8, 1, 1, 7, 9]
]); // => false

构想&解法

function validSolution(board) {
  let n = board.length
  let result = [...board]
  for (let j = 0; j < n; j++) {
    let column = []
    for (let i = 0; i < n; i++) {
      column.push(board[i][j])
    }
    result.push(column)
  }

  for (let j = 0; j < n; j += 3) {
    let square = []
    for (let i = 0; i < n; i++) {
      square.push(...board[i].slice(j, j + 3))

      if (square.length === 9) {
        result.push(square)
        square = []
      }
    }

  }
  const reg = /123456789/
  for (let arr of result) {
    if (reg.test(arr.sort().join('')) == false) return false
  }
  return true
}

每一横列、每一直行、每一个3x3的九宫格，都要包含1~9的数字，每一个数字只能出现一次!

在9x9的方格中，共要检查9个横列、9个直行以及9个九宫格。

要把这『27个阵列』挑出来，将阵列其中的元素做排列，比对是否等於『123456789』

其它解法观摩

function validSolution(board){
  var validSet = s => s.size == 9 && !s.has(0);
  var rowSet = i => board[i].reduce((s,v) => s.add(v), new Set());
  var columnSet = i => board.reduce((s,v) => s.add(v[i]), new Set());
  var boxSet = ([r,c]) => board.slice(r,r+3).reduce((s,v) => v.slice(c,c+3).reduce((s,v) => s.add(v), s), new Set());
  var boxCorner = i => [Math.floor(i / 3) * 3,(i % 3) * 3];
  for (var i = 0; i < 9; i++)
    if ( !validSet(rowSet(i)) || !validSet(columnSet(i)) || !validSet(boxSet(boxCorner(i))) )
      return false;
  return true;
}

分成rowSet、columnSet和boxSet三个function，使用reduce()回传set，利用Set不重复的特性，将元素放入Set中。最後由validSet验证set。

由for loop一一遍历

• rowSet
  • board[0]~board[8]取出每一横列，用reduce()累加rowSet
• columnSet
  • 用reduce()遍历board每一横列，再分别累加每一列的[0]~[8]
• boxSet
  • boxCorner为每一个九宫格的左上角方格的位置，ex: [0,0]、[0,3]、[0,6]、[3,0]、[6,0]。boxCorner依序传入0~8，[Math.floor(i / 3) * 3,(i % 3) * 3]结果依序回传[0,0]、[0,3]...等。
    -　将boxCorner传入boxSet，搭配slice()，加总『三个横列及三个直行』范围内的元素。

Set的基本Method参考先前的Sum of pairs

以上为今日分享的内容，若有错误或是建议，请再随时和我联系。