回溯算法和解数独

    //每一个数字与所能代表的字母的映射关系
    vectorstring> list = {
        "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
    };

        
    vectorstring> res;

    void func(const string & digits , int index , const string& s){
        //设置终止条件
        if(index == digits.size()){
            res.push_back(s); //保存一种组合
            return ;
        }

        char c =digits[index];
        string letters = list[c - ‘2‘]; 

        for(int i = 0 ;i i){　　　　
           func(digits , index + 1 , s + letters[i]);　　
 　　　　　　}   
}

    vectorint>> res;
    void func(const vectorint>& nums , int  index ,vectorint>& one_res , vectorbool>& mark){
        //设置终止条件
        if(index == nums.size())  {
            res.push_back(one_res);
            return;
        }
        
        for(int i = 0 ; i i){
            if(!mark[i]){ //如果i没有被使用
                one_res.push_back(nums[i]);
                mark[i] = true;     //标记          
                func(nums , index+1 , one_res , mark);
                one_res.pop_back();
                mark[i] = false;   //回溯
            }
        }
    }

    vectorint>> res;

    void func( const int& n , const  int& k , int start , vectorint>& p){
        if(p.size() == k){
            res.push_back(p);
            return ;
        }

        //start=i，此时还需要k-p.size()个元素完成操作，从i到N的闭区间中选择k-p.size()个元素
        //i最大为n-(k-p.size())+1
        //i从start开始，因为包含start之前数字的解已经包含在res中了，比如[1,4]和[4,1]就是同一个解，避免重复
        for(int i = start  ; i 1; ++i){
            p.push_back(i);
            func(n , k , i + 1 , p);
            p.pop_back();
        }
    }

class Solution {

    vectorstring>> res;
    vectorbool> col;
    vectorbool> diag1;
    vectorbool> diag2;

    vectorstring> transteranswer(int n ,vectorint>& row){
        vectorstring> oneway (n,string(n,‘.‘));

        for(int i = 0 ; i i){
            oneway[i][row[i]] = ‘Q‘;
        }

        return oneway;
    }

    void func(int n ,int index, vectorint>& row){
        if(index == n){
            res.push_back(transteranswer(n,row));
            return ;                
        }

        for(int i = 0 ;i i){
            if(!col[i] && !diag1[index+i] && !diag2[index-i+n-1]){//判断是否可以放置皇后
                col[i] = true;
                diag1[index+i] = true;
                diag2[index-i+n-1] = true;  //这三步是标记，表明这一列和两条斜对角线都占用
                row.push_back(i);
                func(n , index+1 , row);
                col[i] = false;
                diag1[index+i] = false;
                diag2[index-i+n-1] = false;
                row.pop_back(); //这三步是表示选择错误，回溯
            }
        }

        return ;
    }
public:
    vectorstring>> solveNQueens(int n) {
        if(n == 0 ) return res;
        col=vectorbool>(n,false);
        diag1 = vectorbool>(2*n-1,false);
        diag2 = vectorbool>(2*n-1,false);
        vectorint> row;

        func(n,0,row);

        return res;

    }
};

class Solution {

    char list[9] = {‘1‘,‘2‘,‘3‘,‘4‘,‘5‘,‘6‘,‘7‘,‘8‘,‘9‘};

    bool check(vectorchar>>& board, int x, int y ,char ch){
        //检查第x行中无重复
        for(int i = 0 ; i 9 ; i++){
            if(board[x][i] == ch){
                return false;
            }
        }

        //检查第y行中无重复
        for(int i = 0 ; i 9 ; i++){
            if(board[i][y] == ch){
                return false;
            }
        }

        //检查坐标(x,y)所位于的3*3中无重复
        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(board[i][j]==ch){
                    return false;
                }
            }
        }

        return true;
    }

    bool func(vectorchar>>& board,  int num ){
        if(num == 81) return true ;
      
        int i = num / 9;    //当前行数
        int j = num % 9;    //当前列数

        if(board[i][j] != ‘.‘){
            if(func(board , num+1)) return true;                
        }else{
            for(int k = 0 ; k 9; k ++){
                if(check(board, i , j , list[k])){
                    board[i][j] = list[k] ;
                    if(func(board , num+1 )) return true;
                    board[i][j] =‘.‘;
                }
            }
        }

        return false;

    }

public:
    void solveSudoku(vectorchar>>& board) {
        func(board , 0);
    }
};