Sudoku Solver

Q:


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...

T:
Typical branch and back-trace problem. We check each of the 81 positions recursively.

A:

class Solution {
public:
    bool solve(int pos, vector< vector< char > > &board) {
        if(pos == 81) {
            return true;
        }
        int i = pos/9;
        int j = pos%9;
        if(board[i][j] != '.') {
            return solve(pos+1, board);;
        }
        for(char c='1'; c<='9'; c++) {
            int stop = 0;
            for(int k=0; k<9; k++) {
                if(board[k][j] == c) {
                    stop = 1;
                    break;
                }
            }
            if(stop) {
                continue;
            }
            for(int k=0; k<9; k++) {
                if(board[i][k] == c) {
                    stop = 1;
                    break;
                }
            }
            if(stop) {
                continue;
            }
            for(int k=3*(i/3); k<3*(i/3)+3; k++) {
                for(int l=3*(j/3); l<3*(j/3)+3; l++) {
                    if(board[k][l] == c) {
                        stop = 1;
                        break;
                    }
                }
                if(stop) {
                    break;
                }
            }
            if(stop) {
                continue;
            }
            board[i][j] = c;
            if(solve(pos+1, board)) {
                return true;
            }
            board[i][j] = '.';
        }
    }
    void solveSudoku(vector< vector< char > > &board) {
        solve(0, board);
    }
};