매번 임의의 셀과 무작위 값을 선택하는 스도쿠의 백 트랙킹 로직

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 블록)

내 논리에 결함이 표시되지 않습니다하지만 거기에있다!

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

이 발생하는 실제 문제가 무엇인가

이것은 C++ 코드는? table가 table[/*something*/][9]로 저장 2 차원 배열 인

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

때문에 Y 값을 포함 1-9에 걸릴 수 있기 때문에, 당신은 가능성이 배열의 범위를 벗어 메모리에 액세스하려고합니다 :

여기에 내가 발견 한 문제입니다 . C++은 인덱싱 된 메모리를 0으로 사용하므로 인덱스 0-8을 포함하여 인덱스에만 액세스해야합니다.

편집 : 후계자 용 수정 사항을 게시하기 만하면됩니다.

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