回數邏輯數獨解決選擇隨機單元格和隨機值每次

Question

我想實現一個數獨（9x9網格），非常基本的回溯求解器。

僞邏輯：

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 

約束：在同一行和同一列中同一區域沒有類似的數字（區 - 3×3塊）

我看不出破綻在我的邏輯但它在那裏！

這是C++代碼：

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

什麼是您所遇到的實際問題？

這裏有一個問題，我發現：

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

因爲table存儲爲table[/*something*/][9]一個二維數組，你可能會嘗試訪問內存出數組的邊界，因爲y可以取的值1-9包。請記住，C++使用0索引內存，所以你應該只訪問包含0-8的索引。

編輯： 只是爲後代發佈修復。

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