今日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

以上為今日分享的內容，若有錯誤或是建議，請再隨時和我聯繫。