Tuesday, November 18, 2014

[LeetCode] Valid Sudoku, Sudoku Solver

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.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.

思路:Valid Sudoku

依次检查每一行、每一列以及每一个九宫格的数字元素是否在1-9之间,并且是否没有重复。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        if(board.size()!=9 || board[0].size()!=9) return false;
        
        // check row
        for(int i=0; i<9; i++) {
            vector<bool> used(9,false);
            for(int j=0; j<9; j++) {
                if(!isdigit(board[i][j])) continue; 
                int k = board[i][j]-'0';
                if(k==0 || used[k-1]) return false;
                used[k-1] = true;
            }
        }
        
        //check col
        for(int j=0; j<9; j++) {
            vector<bool> used(9,false);
            for(int i=0; i<9; i++) {
                if(!isdigit(board[i][j])) continue;
                int k = board[i][j]-'0';
                if(k==0 || used[k-1]) return false;
                used[k-1] = true;
            }
        }
        
        // check subbox
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                int row = 3*i;
                int col = 3*j;
                vector<bool> used(9,false);
                for(int m=row; m<row+3; m++) {
                    for(int n=col; n<col+3; n++) {
                        if(!isdigit(board[m][n])) continue;
                        int k = board[m][n]-'0';
                        if(k==0 || used[k-1]) return false;
                        used[k-1]=true;
                    }
                }
            }
        }
        
        return true;
    }
};

思路:Sudoku Solver

和N-Queen思路基本一样。对每个需要填充的位置枚举1-9,对每个枚举判断是否符合所在行、列、九宫格。如果符合则进行下一层递归。终止条件为填写完了整个棋盘。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        if(board.size()<9 || board[0].size()<9) return;
        bool findSol = solSudoku(board, 0, 0);
    }
    
    bool solSudoku(vector<vector<char>> &board, int irow, int icol) {
        if(irow==9) return true;
        
        int irow2, icol2;
        if(icol==8) {
            irow2 = irow+1;
            icol2 = 0;
        }
        else {
            irow2 = irow;
            icol2 = icol+1;
        }
        
        if(board[irow][icol]!='.') {
            if(!isValid(board, irow, icol)) return false;
            return solSudoku(board, irow2, icol2);
        }
        
        for(int i=1; i<=9; i++) {
            board[irow][icol] = '0'+i;
            if(isValid(board, irow, icol) && solSudoku(board, irow2, icol2)) return true;
        }
        
        // reset grid 
        board[irow][icol] = '.';
        return false;
    }
    
    bool isValid(vector<vector<char>> &board, int irow, int icol) {
        char val = board[irow][icol];
        if(val-'0'<1 || val-'0'>9) return false;
        
        // check row & col
        for(int i=0; i<9; i++) {
            if(board[irow][i]==val && i!=icol) return false;
            if(board[i][icol]==val && i!=irow) return false;
        }
        
        //check 3x3 box
        int irow0 = irow/3*3;
        int icol0 = icol/3*3;
        for(int i=irow0; i<irow0+3; i++) {
            for(int j=icol0; j<icol0+3; j++) {
                if(board[i][j]==val && (i!=irow || j!=icol)) return false;
            }
        }
        
        return true;
    }
};

1 comment: