Sodoku 역 추적 알고리즘

Question

역 추적 방법을 사용하여 Java의 빈 그리드에서 Sudoku를 생성하는 코드를 작성했습니다. 내가 프로그램을

public class SodokuGenerator { 

int[][] puzzle=new int[9][9]; 
int num_givens=0; 

public static int get_random_value(int high, int low) 
{ 
    //Returns a random value between the given maximum and minimum values(both  inclusive) 
    Random r=new Random(); 
    return (r.nextInt(high+1-low) + low); 
} 

    public boolean check_column(int x, int y, int curr_value) 
{ 
    for (int i=0;i<9;i++) 
    { 
     if (this.puzzle[i][y]==curr_value) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

public boolean check_row(int x, int y, int curr_value) 
{ 
    for (int j=0;j<9;j++) 
    { 
     if (this.puzzle[x][j]==curr_value) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

public boolean check_block(int x, int y, int curr_value) 
{ 
    int block_row_start=0, block_row_end=0,block_col_start=0, block_col_end=0; 

    if (x==0 || x==3 || x==6) 
    { 
     block_row_start=x; 
     block_row_end=x+3-1; 
    } 
    else if (x==2 || x==5 || x==8)//At the end of a block 
    { 
     block_row_start=x-3+1; //both bounds are inclusive 
     block_row_end=x; 
    } 
    else if (x==1 || x==4 || x==7) //Neither multiples of 2 nor 3. 
    { 
     block_row_start=x-1; 
     block_row_end=x+1; 
    } 

    if (y==0 || y==3 || y==6) 
    { 
     block_col_start=y; 
     block_col_end=y+3-1; 
    } 
    else if (y==2 || y==5 || y==8)//At the end of a block 
    { 
     block_col_start=y-3+1; //both bounds are inclusive 
     block_col_end=y; 
    } 
    else if (y==1 || y==4 || y==7) //Neither multiples of 2 nor 3. 
    { 
     block_col_start=y-1; 
     block_col_end=y+1; 
    } 
    //Established the bounds of the block based on the current position 
    //System.out.println("block_row_start="+block_row_start); 
    //System.out.println("block_row_end= "+block_row_end); 
    for (int i=block_row_start;i<=block_row_end;i++) 
    { 
     for (int j=block_col_start;j<=block_col_end;j++) 
     { 
      //System.out.println("i="+i); 
      //System.out.println("j="+j); 
      if (this.puzzle[i][j]==curr_value) 
      { 
       return false; 
      } 
     } 
    } 
    return true; 
} 



public void create_puzzle() 
{ 
    int curr_value=0; 
    int index=0; 
    int[] possible_values={1,2,3,4,5,6,7,8,9}; 

    this.puzzle[0][0]=get_random_value(9,1); 
    int x=0,y=1; //Holds the coordinates of the current position in the puzzle 


    while (x<=8 && y<=8) 
    { 
     this.puzzle[x][y]=0; 
     curr_value= get_random_value(9,1); 
     if (this.check_block(x,y, curr_value) && this.check_row(x,y,curr_value) 
     && this.check_column(x,y,curr_value)) 
     { 
      this.puzzle[x][y]=curr_value; 
     } 
     else //If there is a conflict with another element 
     { 
      index=-1; 
      //Checks for a conflict using all possible values 
      do //Using a do-while loop prevents a repeated computation 
      { 
       index++; 
       curr_value=possible_values[index]; 
      } 
      while (index<8 && (this.check_block(x,y, curr_value)==false || 
        this.check_row(x,y,curr_value)==false 
        || this.check_column(x,y,curr_value)==false)); 


      if (index==8)//This means that no possible solution was found 
      { 
       //BACKTRACKING 
       if (y==0 && x!=0) 
       { 
        y=8; 
        x--; 
       } 
       else 
       { 
        y--; 
       } 

       continue; 
      } 
      else //If a possible solution was found 
      { 
       this.puzzle[x][y]=curr_value; 
      } 
     } 

     //Advancing the current position coordinates to the next position 
     if (y==8) 
     { 
      y=0; 
      x++; 
     } 
     else 
     { 
      y++; 
     } 
     } 
} 

을 실행에는 출력을 얻을 그러나 나는 그러나 그들은 정말 me.Debugging 플레이에서 무한 루프가 있음을 알려줍니다 도움이되지 않았다이 포럼에 비슷한 질문을보고했다. 누구든지 올바른 방향으로 나를 가리켜 주시겠습니까? 나는 그것을 대단히 감사 할 것입니다. 고맙습니다.

Answer 1

동안 (X = 8 < & & < Y = 8)

그 루프는 무한하다. 루프 내에서 값을 화면에 인쇄 해보십시오.

System.out.println ("X :"+ x + ""+ y);

나는 깊이있는 코드를 검사하지 않았다 ...하지만 난 여기에 문제를 의심 :

 if (index==8)//This means that no possible solution was found 
     { 
      //BACKTRACKING 
      if (y==0 && x!=0) 
      { 
       y=8; 
       x--; 
      } 
      else 
      { 
       y--; 
      } 

      continue; 
     } 

및

if (y==8) //This if statement only runs once. Y always gets subtracted back to 7 in the code above. 
    { 
     y=0; 
     x++; 
    } 
    else 
    { 
     y++; 
    } 
    } 

지수가 8에 도달하면

, 함수가 갈 것입니다 else에 y를 하나 뺍니다. 이후에 y가 하나씩 추가됩니다. 이 프로세스는 y와 -1을 무한 루프로 반복하여 앞뒤로 바운스합니다.