LeetCode之Valid Sudoku

【题目】

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.

【题意】

假设一个数独是有效的，则它符合数独游戏 规则（点击打开链接）。

数独游戏 规则：

（1）每一行都必须在1-9的范围内，且只出现一次。

（2）每一列都必须在1-9的范围内，且只出现一次。

（3）数字1-9在每个子宫格中只出现一次。

数独宫格可以部分填充，其中空单元格都充满了字符'.'。

例如：

部分填充的有效数独

【分析】

细节分析题

（1）检查行

（2）检查列

（3）检查9个子宫格

【代码】

/*********************************
*   日期：2014-01-20
*   作者：SJF0115
*   题号: Valid Sudoku
*   来源：http://oj.leetcode.com/problems/valid-sudoku/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        int i,j,k;
        //判断1-9是否已用
        bool used[9];
        for(i = 0;i < 9;i++){
            //检查行
            memset(used,false,9);
            for(j = 0;j < 9;j++){
                //不符合规则
                if(!check(board[i][j],used)){
                    return false;
                }//if
            }//for
            //检查列
            memset(used,false,9);
            for(j = 0;j < 9;j++){
                //不符合规则
                if(!check(board[j][i],used)){
                    return false;
                }//if
            }//for
        }//for
        //检查9个子宫格
        for(k = 0;k < 3;k++){
            memset(used,false,9);
            for(i = k*3;i < 3*k + 3;i++){
                for(j = 0;j < 3;j++){
                    //不符合规则
                    if(!check(board[i][j],used)){
                        return false;
                    }//if
                }//for
            }//for
            memset(used,false,9);
            for(i = k*3;i < 3*k + 3;i++){
                for(j = 3;j < 6;j++){
                    //不符合规则
                    if(!check(board[i][j],used)){
                        return false;
                    }//if
                }//for
            }//for
            memset(used,false,9);
            for(i = k*3;i < 3*k + 3;i++){
                for(j = 6;j < 9;j++){
                    //不符合规则
                    if(!check(board[i][j],used)){
                        return false;
                    }//if
                }//for
            }//for
        }//for
        return true;
    }
private:
    bool check(char c,bool used[9]){
        if(c == '.'){
            return true;
        }
        //字符c 已用
        if(used[c - '1']){
            return false;
        }
        //字符c 未用
        else{
            used[c - '1'] = true;
            return true;
        }
    }
};
int main() {
    Solution solution;
    bool result;
    vector<vector<char>> board;

    char value[9] = {'5','3','.','.','7','.','.','.','.'};
    vector<char> subBoard(value,value + 9);
    board.push_back(subBoard);

    value = {'6','.','.','1','9','5','.','.','.'};
    vector<char> subBoard1(value,value + 9);
    board.push_back(subBoard1);

    value = {'.','9','8','.','.','.','.','6','.'};
    vector<char> subBoard2(value,value + 9);
    board.push_back(subBoard2);

    value = {'8','.','.','.','6','.','.','.','3'};
    vector<char> subBoard3(value,value + 9);
    board.push_back(subBoard3);

    value = {'4','.','.','8','.','3','.','.','1'};
    vector<char> subBoard4(value,value + 9);
    board.push_back(subBoard4);

    value = {'7','.','.','.','2','.','.','.','6'};
    vector<char> subBoard5(value,value + 9);
    board.push_back(subBoard5);

    value = {'.','6','.','.','.','.','2','8','.'};
    vector<char> subBoard6(value,value + 9);
    board.push_back(subBoard6);

    value = {'.','.','.','4','1','9','.','.','5'};
    vector<char> subBoard7(value,value + 9);
    board.push_back(subBoard7);

    value = {'.','.','.','.','8','.','.','7','9'};
    vector<char> subBoard8(value,value + 9);
    board.push_back(subBoard8);

    result = solution.isValidSudoku(board);
    cout<<result<<endl;
    return 0;
}

【代码2】

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool used[9];
        for (int i = 0; i < 9; ++i) {
            fill(used, used + 9, false);
            // 检查行
            for (int j = 0; j < 9; ++j){
                if (!check(board[i][j], used)){
                    return false;
                }//if
            }//for
            fill(used, used + 9, false);
            // 检查列
            for (int j = 0; j < 9; ++j) {
                if (!check(board[j][i], used)){
                    return false;
                }//if
            }//for
        }//for
        // 检查 9 个子格子
        for (int r = 0; r < 3; ++r) {
            for (int c = 0; c < 3; ++c) {
                fill(used, used + 9, false);
                for (int i = r * 3; i < r * 3 + 3; ++i){
                    for (int j = c * 3; j < c * 3 + 3; ++j){
                        if (!check(board[i][j], used)){
                            return false;
                        }
                    }//for
                }//for
            }//for
        }//for
        return true;
    }
    bool check(char ch, bool used[9]) {
        if (ch == '.') return true;
        if (used[ch - '1']) return false;
        used[ch - '1'] = true;
        return true;
    }
};