DFS+回溯

LeetCode 36 判断给出的数独是否有效
https://www.cnblogs.com/ganganloveu/p/4170632.html
难点：九个3x3方块的坐标表示

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        for(int i = 0; i < 9; i ++)
        {
            unordered_map<char, bool> m1;   //check i_th row
            unordered_map<char, bool> m2;   //check i_th column
            unordered_map<char, bool> m3;   //check i_th subgrid
            for(int j = 0; j < 9; j ++)
            {
                if(board[i][j] != '.')
                {
                    if(m1[board[i][j]] == true)
                        return false;
                    m1[board[i][j]] = true;
                }
                if(board[j][i] != '.')
                {
                    if(m2[board[j][i]] == true)
                        return false;
                    m2[board[j][i]] = true;
                }
                if(board[i/3*3+j/3][i%3*3+j%3] != '.')
                {
                    if(m3[board[i/3*3+j/3][i%3*3+j%3]] == true)
                        return false;
                    m3[board[i/3*3+j/3][i%3*3+j%3]] = true;
                }
            }
        }
        return true;
    }
};

LeetCode 51 N-Queens
http://www.cnblogs.com/ganganloveu/p/4020488.html

回溯法尝试所有可能性，将可行解的保存起来。

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        return convert(solve(n), n);
    }
    vector<vector<int> > solve(int n)
    {
        vector<vector<int> > ret;
        vector<int> cur;
        Helper(ret, cur, 0, n);
        return ret;
    }
    void Helper(vector<vector<int> >& ret, vector<int> cur, int pos, int n)
    {
        if(pos == n)
            ret.push_back(cur);
        else
        {
            for(int i = 0; i < n; i ++)
            {
                cur.push_back(i);
                if(check(cur))
                    Helper(ret, cur, pos+1, n);
                cur.pop_back();
            }
        }
    }
    bool check(vector<int> cur)
    {
        int size = cur.size();
        int loc = cur[size-1];
        for(int i = 0; i < size-1; i ++)
        {
            if(cur[i] == loc)
                return false;
            else if(abs(cur[i]-loc) == abs(i-size+1))
                return false;
        }
        return true;
    }
    vector<vector<string> > convert(vector<vector<int> > ret, int n)
    {
        vector<vector<string> > retStr;
        for(int i = 0; i < ret.size(); i ++)
        {
            vector<string> curStr;
            for(int j = 0; j < n; j ++)
            {
                string loc(n, '.');
                loc[ret[i][j]] = 'Q';
                curStr.push_back(loc);
            }
            retStr.push_back(curStr);
        }
        return retStr;
    }
};

LeetCode 37. Sudoku Solver 解数独
https://blog.csdn.net/feliciafay/article/details/44558851

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        solve(board, 0);
    }
    bool solve(vector<vector<char> > &board, int position)
    {
        if(position == 81)
            return true;

        int row = position / 9;
        int col = position % 9;
        if(board[row][col] == '.')
        {
            for(int i = 1; i <= 9; i ++)
            {//try each digit
                board[row][col] = i + '0';
                if(check(board, position))
                    if(solve(board, position + 1))
                    //only return valid filling
                        return true;
                board[row][col] = '.';
            }
        }
        else
        {
            if(solve(board, position + 1))
            //only return valid filling
                return true;
        }
        return false;
    }
    bool check(vector<vector<char> > &board, int position)
    {
        int row = position / 9;
        int col = position % 9;
        int gid;
        if(row >= 0 && row <= 2)
        {
            if(col >= 0 && col <= 2)
                gid = 0;
            else if(col >= 3 && col <= 5)
                gid = 1;
            else
                gid = 2;
        }
        else if(row >= 3 && row <= 5)
        {
            if(col >= 0 && col <= 2)
                gid = 3;
            else if(col >= 3 && col <= 5)
                gid = 4;
            else
                gid = 5;
        }
        else
        {
            if(col >= 0 && col <= 2)
                gid = 6;
            else if(col >= 3 && col <= 5)
                gid = 7;
            else
                gid = 8;
        }

        //check row, col, subgrid
        for(int i = 0; i < 9; i ++)
        {
            //check row
            if(i != col && board[row][i] == board[row][col])
                return false;
            
            //check col
            if(i != row && board[i][col] == board[row][col])
                return false;
            
            //check subgrid
            int r = gid/3*3+i/3;
            int c = gid%3*3+i%3;
            if((r != row || c != col) && board[r][c] == board[row][col])
                return false;
        }
        return true;
    }
};