[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++

	class Solution {
	public:
	bool isValidSudoku(vector<vector<char>>& board) {
	const int boardLen = 9;
	int rowFlag[boardLen] = {0};
	int colFlag[boardLen] = {0};
	int cubeFlag[boardLen] = {0};
	for(int r = 0; r < boardLen; r++) {
	for(int c = 0; c < boardLen; c++) {
	if(board[r][c] != '.') {
	int num = 1 << static_cast<int>(board[r][c] - '1');
	//> check duplicated or not
	if(rowFlag[r] & num ||
	colFlag[c] & num ||
	cubeFlag[3 * (r / 3) + (c / 3)] & num) {
	return false;
	}
	//> mark used
	rowFlag[r] |= num;
	colFlag[c] |= num;
	cubeFlag[3 * (r / 3) + (c / 3)] |= num;
	}
	}
	}
	return true;
	}
	};

view raw validSudoku.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun isValidSudoku(board: Array<CharArray>): Boolean {
	val len = 9
	val rowFlags = IntArray(len) { 0 }
	val colFlags = IntArray(len) { 0 }
	val cubeFlags = IntArray(len) { 0 }
	var num = 0
	var cubeIndex = 0
	for(r in 0 until len) {
	for(c in 0 until len) {
	if(board[r][c] != '.') {
	num = 1 shl (board[r][c] - '1').toInt()
	cubeIndex = 3*(r/3) + (c/3)
	if(
	rowFlags[r] and num != 0
	|| colFlags[c] and num != 0
	|| cubeFlags[cubeIndex] and num != 0
	) {
	return false
	}
	rowFlags[r] = rowFlags[r] or num
	colFlags[c] = colFlags[c] or num
	cubeFlags[cubeIndex] = cubeFlags[cubeIndex] or num
	}
	}
	}
	return true
	}
	}

view raw valid_sudoku.kt hosted with ❤ by GitHub