Sodoku回溯算法

Question

我已经编写了使用回溯方法从Java中的空白网格生成数独的代码。但是，我在运行程序时没有得到任何输出

 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

while (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++;
    }
    }

一旦index达到8，该函数将进入else，将y减去1。然后y加1。此过程反复循环，导致y值在无限循环中为-1和+1。