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

Have you been asked this question in an interview?

首先leetcode只要求9*9的输入，所以不可能出现时间和空间不够用的问题。
基本思路是回溯，回溯类似就是DFS，不同的是某层失败后要回到上一层，失败的一层要恢复原样。
另外，回溯也要使用递归，递归需要有收敛条件，就是要有一段code，不会调用自身而返回。
在我写的code里面，就是

if(i==n*m)
            return true;

int n,m;
    bool check(int k, vector<vector<char> > &board){
        int x=k/n;
        int y=k%m;
        for (int i = 0; i < n; i++)
            if (i != x && board[i][y] == board[x][y])
                return false;
        for (int j = 0; j < m; j++)
            if (j != y && board[x][j] == board[x][y])
                return false;
        for (int i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
            for (int j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
                if (i != x && j != y && board[i][j] == board[x][y])
                    return false;
        return true;
    }
    bool f(int i, vector<vector<char> > &board){
        if(i==n*m)
            return true;
        if(board[i/n][i%m]=='.'){
            for(int k=1;k<=9;k++){
                board[i/n][i%m]=k+'0';
                    if(true==check(i,board))
                        if(true==f(i+1,board))
                            return true;
            }
            board[i/n][i%m]='.';
            return false;
        }
        else
            return f(i+1,board);
    }
    void solveSudoku(vector<vector<char> > &board) {
        n=board.size();
        m=board[0].size();
        f(0,board);
    }