Backtracking logic for sudoku solving choosing random cell and random value each time

Question

I'm trying to implement a backtracking solver for sudoku (9x9 grid), very basic.

Pseudocode logic:

backtrack():
choose random **empty** cell

generate random value (1 ....9)

check if it fits(or is good for - row,column,region):
               if yes - occupy this cell , recurse

               if no -  put the cell value to zero

Constraints: no similar numbers in SAME ROW AND SAME COLUMN AND SAME REGION.(region - 3x3 block)

I don't see the flaw in my logic but it is there!

This is the c++ code:

bool basic_sudoku_with_random_picking( int table[][9] ){

    if(find_empty_cell(table) == false ) return true ;// no empty cells? success!
    int row = -1 ;
    int column = -1 ;           
    int x, y ;     
    x = 1 + rand() % 9 ;//generate random x
    y = 1 + rand() % 9 ;//gen random y

    if( table[x][y] == 0){// see if the cell is zero (zero - free)
        row = x ;
        column = y ;              
        int try_num = 1 + rand()% 9 ;// found empty cell - try  random number on it!
        if( is_good(table, row,column, try_num) ){
            table[row][column] = try_num ;                               
            return ( basic_sudoku_with_random_picking(table) ) ;
        }
        else{ table[row][column] = 0 ;                               
            return false ;

        }                                  
    }                    
    else return basic_sudoku_with_random_picking(table) ;

}


//check row 
bool is_row_good(int table[][9], int row , int num){
    for(int column = 0  ; column < 9 ; column++ ){
        if (table[row][column] == num ){
            return false ;}                         
    }

    return true ;
}
//check column
bool is_column_good(int table[][9], int column , int num){
    for(int row = 0  ; row < 9 ; row++ ){
        if (table[row][column] == num ){
            return false ;}                         

    }
    return true ;
}
//check block- region
bool check_region(int table[][9], int x1, int y1, int x2, int y2, int check){
    for(int i = x1; i <= x2 ;i++){
        for(int j = y1 ; j <=y2 ;j++){
            if(table[i][j] == check){

                return false ;}

        }
        cout <<endl ;
    }
    return true ;
}
bool is_block_good(int table[][9], int i, int j , int num){

    if(i >= 0 && i <=2){
        if( j <= 2 )      check_region(table,0,0,2,2, num) ;// 1 region
        if(j >= 3 && j<=5)check_region(table,0,3,2,5, num) ;//2 region
        if(j >=6  && j<=8)check_region(table,0,6,2,8, num) ;//3 region
    }           

    if(i >=3 && i <=5){
        if(j <=2 )        check_region(table,3,0,5,2, num) ;//4 block
        if(j >= 3 && j<=5)check_region(table,3,3,5,5, num) ;//5 block
        if(j >= 6 && j<=8)check_region(table,3,6,5,8, num) ;//6 block

    }

    if( i >=6 && i <=8){
        if(j<= 2)         check_region(table,6,0,8,2, num) ;//7 block
        if(j >= 3 && j<=5)check_region(table,6,3,8,5, num) ;// 8 block
        if(j >= 6 && j<=8)check_region(table,6,6,8,8, num) ;//9 block 
    }
}

//check all 3 constraints
bool is_good(int table[][9], int i, int j, int try_num){
    //cout << "CHECKING CELL in general" <<endl ;
    return (is_row_good   (table, i, try_num) &&
            is_column_good(table, j, try_num) && 
            is_block_good (table, i , j,try_num) ) ;                            
}

bool find_empty_cell(int table[][9]){
    for(int i = 0 ; i  < 9 ; i++){
        for(int j = 0 ; j < 9 ; j++){                          
            if( table[i][j] == EMPTY_CELL){// found empty cell
                return true ;
            }
        }
    }
    return false ;
} 

Answer 1

What is the actual problem you're having?

Here's one problem I found:

x = 1 + rand() % 9 ;//generate random x
y = 1 + rand() % 9 ;//gen random y
   if( table[x][y] == 0){
      ...

Because table is a 2d array stored as table[/*something*/][9], you will likely try to access memory out of bounds of the array because y can take on values 1-9 inclusive. Remember that C++ uses 0 indexed memory, so you should only be accessing indices 0-8 inclusive.

Edit: Just to post the fix for posterity.

x = rand() % 9 ;//generate random x
y = rand() % 9 ;//gen random y