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 & &Ŷ< = 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减1。之后y加1。这个过程会反弹回来，导致y值在无限循环中为-1和+1。