本篇同步發布於Blog:[解題] LeetCode - 36 Valid Sudoku

平台：

LeetCode

題號：

36 - Valid Sudoku

題目連結：

https://leetcode.com/problems/valid-sudoku/

題目說明：

        給一個數獨9*9的矩陣，檢查此數獨填的值是否符合數獨的規則。數獨規則有3：

1. 每一列出現1~9的數字只能各1次
2. 每一行出現1~9的數字只能各1次
3. 每3*3的小矩陣出現1~9的數字只能各1次

解題方法：

   　 將前述的三種規則，分別寫成3個函式，是否有重複出現的數字，可以用HashSet來記錄。

接著從每一行、每一列、每3*3矩陣分別呼叫對應的函式做檢查。

難度為Medium

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
private:
    bool checkRowValid(vector<vector<char>>& board, int row){
        unordered_set<char> repeat;
        for(int i = 0 ; i < 9;++i){
            if(board[row][i] != '.'){
                if(repeat.count(board[row][i])){
                    return false;
                }
                repeat.insert(board[row][i]);
            }
        }
        return true;
    }
    
    bool checkColValid(vector<vector<char>>& board, int col){
        unordered_set<char> repeat;
        for(int i = 0 ; i < 9;++i){
            if(board[i][col] != '.'){
                if(repeat.count(board[i][col])){
                    return false;
                }
                repeat.insert(board[i][col]);
            }
        }
        return true;
    }
    
    bool checkSquareValid(vector<vector<char>>& board, int leftTopRow, int leftTopCol){
        unordered_set<char> repeat;
        for(int i = leftTopRow ; i < leftTopRow + 3;++i){
            for(int j = leftTopCol; j < leftTopCol + 3;++j){
                if(board[i][j] != '.'){
                    if(repeat.count(board[i][j])){
                        return false;
                    }
                    repeat.insert(board[i][j]);
                }
            }
        }
        return true;
    }
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool result = true;
        for(int i = 0;i < 9;++i){
            result = checkRowValid(board, i);
            if(!result){
                return result;
            }
        }
        
        for(int i = 0;i < 9;++i){
            result = checkColValid(board, i);
            if(!result){
                return result;
            }
        }
        
        for(int i = 0;i < 9;i+=3){
            for(int j = 0 ; j < 9; j+=3){
                result = checkSquareValid(board, i, j);
                if(!result){
                    return result;
                }
            }
        }
        
        return true;
    }
};

int main()
{
    Solution sol;
	vector<vector<char>> 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'}};
    bool result = sol.isValidSudoku(board);
    cout << result << endl;
    return 0;
}

using System;
using System.Collections.Generic;

namespace LeetCode36
{
    public class Solution {
		private bool CheckRowValid(char[][] board, int row){
			HashSet<char> repeat = new HashSet<char>();
			for(int i = 0 ; i < 9;++i){
				if(board[row][i] != '.'){
					if(repeat.Contains(board[row][i])){
						return false;
					}
					repeat.Add(board[row][i]);
				}
			}
			return true;
		}
		
		private bool CheckColValid(char[][] board, int col){
			HashSet<char> repeat = new HashSet<char>();
			for(int i = 0 ; i < 9;++i){
				if(board[i][col] != '.'){
					if(repeat.Contains(board[i][col])){
						return false;
					}
					repeat.Add(board[i][col]);
				}
			}
			return true;
		}
		
		private bool CheckSquareValid(char[][] board, int leftTopRow, int leftTopCol){
			HashSet<char> repeat = new HashSet<char>();
			for(int i = leftTopRow ; i < leftTopRow + 3;++i){
				for(int j = leftTopCol; j < leftTopCol + 3;++j){
					if(board[i][j] != '.'){
						if(repeat.Contains(board[i][j])){
							return false;
						}
						repeat.Add(board[i][j]);
					}
				}
			}
			return true;
		}
		public bool IsValidSudoku(char[][] board) {
			bool result = true;
			for(int i = 0;i < 9;++i){
				result = CheckRowValid(board, i);
				if(!result){
					return result;
				}
			}
			
			for(int i = 0;i < 9;++i){
				result = CheckColValid(board, i);
				if(!result){
					return result;
				}
			}
			
			for(int i = 0;i < 9;i+=3){
				for(int j = 0 ; j < 9; j+=3){
					result = CheckSquareValid(board, i, j);
					if(!result){
						return result;
					}
				}
			}
			
			return true;
		}
	}
	
    class Program
    {
        static void Main(string[] args)
        {
            Solution sol = new Solution();
            char[][] board = new char[9][];
			board[0] = new char[]{'5','3','.','.','7','.','.','.','.'};
			board[1] = new char[]{'6','.','.','1','9','5','.','.','.'};
			board[2] = new char[]{'.','9','8','.','.','.','.','6','.'};
			board[3] = new char[]{'8','.','.','.','6','.','.','.','3'};
			board[4] = new char[]{'4','.','.','8','.','3','.','.','1'};
			board[5] = new char[]{'7','.','.','.','2','.','.','.','6'};
			board[6] = new char[]{'.','6','.','.','.','.','2','8','.'};
			board[7] = new char[]{'.','.','.','4','1','9','.','.','5'};
			board[8] = new char[]{'.','.','.','.','8','.','.','7','9'};
            bool result = sol.IsValidSudoku(board);
            Console.Write(result);
            Console.Read();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/1-99/36.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/1-99/36.cs