5ms solution ,C, DFS


  • 0
    R
    int flagr[100][10];
    int flagc[100][10];
    int flagb[100 / 3][100 / 3][10];
    int flagm[100][100];
    int row;
    int col;
    struct posibility{
        int val;
        int x;
        int y;
    }pos[100];
    int nodecount;
    
    int isok(int x,int y, int target){
        if (flagr[x][target] || flagc[y][target] || flagb[x / 3][y / 3][target])
            return false;
        return true;
    }
    
    void tryit(int x,int y, int target){
        flagr[x][target] = 1;
        flagc[y][target] = 1;
        flagb[x / 3][y / 3][target] = 1;
    }
    
    void untry(int x,int y, int target){
        flagr[x][target] = 0;
        flagc[y][target] = 0;
        flagb[x / 3][y / 3][target] = 0;
    }
    
    
    int dfs(char **board, int posNum){
    
        if (posNum >= nodecount)
            return true;
        int i,j;
        struct posibility * cur = pos + posNum;
        flagm[cur->x][cur->y] = 1;
        for (i = 1; i < 10; i++){
            if (isok(cur->x, cur->y, i)){
                tryit(cur->x, cur->y ,i);
                board[cur->x][cur->y] = i + '0';
                if(dfs(board, posNum + 1))
                    return 1;
                untry(cur->x, cur->y, i);
            }
        }
        flagm[cur->x][cur->y] = 0;
        return 0;
    
    }
    
    
    /*** count posibility and sort them **/
    int cmp(const void *a, const void *b){
        struct posibility * n1 = (struct posibility *)a;
        struct posibility * n2 = (struct posibility *)b;
        return n1->val - n2->val;
    }
    
    
    void calPosibility(char **board){
        int i,j, k;
        //printf("stratcal\n");
        for (i = 0 ; i <row; i++)
            for (j = 0 ; j < col ;j++){
            if (board[i][j] == '.'){
                pos[nodecount].x = i;
                pos[nodecount].y = j;
                for (k = 1; k< 10; k++){
                    if (isok(i,j,k))
                        pos[nodecount].val++;
                }
                nodecount++;
            }
        }
        qsort(pos, nodecount, sizeof(struct posibility), cmp);
    }
    
    
    void solveSudoku(char** board, int boardRowSize, int boardColSize) {
        row = boardRowSize;
       col = boardColSize;
        int i, j, val;
        memset(flagr, 0 ,sizeof (flagr));
        memset(flagc, 0 ,sizeof (flagc));
        memset(flagb, 0 ,sizeof (flagb));
        memset(flagm, 0 ,sizeof (flagm));
        nodecount = 0;
         /**  some work befor..... **/
        for (i = 0 ; i < boardRowSize; i++)
            for (j = 0 ; j <  boardColSize; j++){
                if (board[i][j] != '.'){
                   val = board[i][j] - '0';
                    flagr[i][val] = 1;
                    flagc[j][val] = 1;
                    flagb[i / 3][j / 3][val] = 1;
                    flagm[i][j] = 1;
                }
            }
        calPosibility(board);
        //start
        dfs(board, 0);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.