[LeetCode] 36. Valid Sudoku

轉自LeetCode

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

<Solution>

這題不是要解速讀，而是去檢查目前速讀上的數字是否符合規則

• 每個 row，要有 1 - 9，不能有重複

• 每個 col，要有 1 - 9，不能有重複

• 每個 3x3 的小方塊，要有 1 - 9，不能有重複

因為題目只是要問目前填上去的數字，是否符合規則，沒問可不可以解

所以只要檢查是否有重複就可以了

基本想法就是用個二階矩陣，去看是否某個數字已經用過了

例如 : row[9][9]，代表每個 row 可以放 1 - 9 的數字，有用過就設為 true

現在在 row = 0 檢查到 8 這個數字，如果 row[0][7] = true，代表重複，反之就是可以用

比較要注意的是小方塊的檢查，該怎麼做 indexing

首先，有九個小方塊，每個小方塊裡面有九個小格

所以其實也是可以看成一個 9x9 的矩陣

row 的 index 算法是，3 * (row / 3) + (col / 3)  => 因為小方塊是 3x3，row 和 col 每三個一組

col 的 index 就是 0 - 8

然後在討論區看到一個神解，其實不用用到二階矩陣

想法如下

• row、col、小方塊都用一個長度為 9 的 int array 來檢查是否重複，初始值是 0

• 每個 int 的前9個 bit 就拿來當做 true / false 用 => 所以不用二階矩陣

• 所以是用 bit operation 來檢查是否用過 => 速度也快

code 如下

c++

kotlin