c++ - 使用堆栈的数独无限循环

Question

我是新手，已经五年多没有编写 C++ 代码了。我在一门关于数独解算器的类(class)中有一个项目。它工作(在大多数情况下)，除非它回溯(当它找不到一个可能的值放入框中时)，它要么一直回溯到开头，要么无法退出循环。帮助？代码如下

Address::Address(int row, int col) //This class is for the addresses of each block of of the 9x9 grid
{
    this->row=row;
    this->col=col;
}//finds the locations of each block

Puzzle::Puzzle(const char grid[][9])
{
}

void Puzzle::solve(char grid[][9])
{
stack <Address> locations; //creates stack of locations
for(int row=0; row<9;row++)
{
    for (int col=0; col<9; col++)
    {
        if (grid[row][col]=='*') //checks for an empty block
        {
            Possibles possibles(grid,Address(row,col)); //creates an array of possible values for that specific block
            int possvalue = possibles.GetNextPossible(0); //gets the next possible value from the array of possible values
            while(possvalue == -1) //checks if there's no possible values for the block 
            {
                if(locations.empty())
                {
                    cout << "Puzzle Unsolvable" << endl;
                    return;
                }
                cout<<"PossValue before: "<< possvalue <<endl;
                Address previouslocation = locations.top(); //stores the previous location from the stack
                Possibles previouspossible(grid,previouslocation); //creates a new array of new possibles
                previouspossible.array[grid[previouslocation.row][previouslocation.col]-'0'] = false;
                grid[previouslocation.row][previouslocation.col] = '*'; //changes the previous location back to empty
                possvalue = previouspossible.GetNextPossible(grid[previouslocation.row][previouslocation.col]-'0'); //gets the new possible value from new possibles
                locations.pop();


                cout<<"PossValue after: "<< possvalue<<endl;
                cout<<"row: "<< row<<endl;
                cout<<"col: "<< col<<endl;
                cout<<"previouslocation.row: "<< previouslocation.row<<endl;
                cout<<"previouslocation.col: "<< previouslocation.col<<endl;
                cout<<"previousvalue" << grid[previouslocation.row][previouslocation.col] << endl;
                cout<<"grid[previouslocation.row][previouslocation.col]: "<< grid[previouslocation.row][previouslocation.col]<<endl;
                cout << locations.size() << endl;
                cout<<endl;

                row = previouslocation.row; //changes the row where we're trying to solve
                col = previouslocation.col; //changes the column where we're trying to solve
            }

            grid[row][col] = (char) ( ((int)'0') + possvalue); //puts the "good" value on the grid
            locations.push (Address(row,col)); // pushes the location of the box into the stack
            /*for(int i = 0; i< 9; i++)
            {
                for(int j = 0; j< 9; j++)
                    cout << grid[i][j];

                    cout << endl;
            }*/ // for row
            cout << endl;
        }
    }
}

}//solves sudoku

Possibles::Possibles(char grid[][9], Address currentAddress) //makes an array for each block for the number of possibles
{
for (int i=0; i<10; i++)
{
        array[i] = true; //setting a boolean array of size 9 to true
}

for (int row=0; row<9;row++)
{
array[grid[row][currentAddress.col]-'0'] = false; //checks for repeated values on the row 
}
for(int col=0; col<9; col++)
{
    array[grid[currentAddress.row][col]-'0'] = false; //checks for repeated values on the column
}
for(int row=currentAddress.row-(currentAddress.row%3); row < (currentAddress.row-(currentAddress.row%3))+3 ; row++) 
{
    for(int col=currentAddress.col-(currentAddress.col%3); col < (currentAddress.col-(currentAddress.col%3))+3 ; col++)
    {
        array[grid[row][col]-'0'] = false; //checks for repeated values in the box
    }
}

}//this function returns an array of "possibles" which is a boolean array for every value from 1-9. This determines whether the value is a possibility for that block.

int Possibles::GetNextPossible(int nextpossible) //determines the next "possible" array
{
for(int i=nextpossible+1; i<10; i++)
{
    if (array[i] == true)
        {
            return i; //if the boolean array returns true, then return the value of that boolean array.
        }
}
return -1; // if there is no "true" in the boolean array, then returns "NULL"
}

谢谢大家的帮助!感谢任何输入。

Answer 1

我真的无法理解你的代码，但如果你打算回溯(你必须解决数独)，你真的应该正在使用递归。没有它，你必须模拟它；最多重要的是，您将无法使用 for 循环，因为在次，你将不得不减少。

另一点:我想你会发现它更简单(尤其是如果你不使用递归)如果你代表数独板作为一个简单的线性数组，char [81] 或类似的东西。如果你这样做，你将有一个单一的当前位置索引，你可以递减和递增，不用担心的行和列。

所以，递归:

void
Puzzle::solve( int currentPosition = 0 )
{
    if ( currentPosition >= 81 ) {
        solved = true;
    } else if ( board[ currentPosition ] != empty ) {
        solve( currentPosition + 1 );
    } else {
        for ( int newValue = 1; ! solved && newValue <= 9; ++ newValue ) {
            if ( isLegal( currentPosition, newValue ) ) {
                set( currentPosition, newValue );
                solve( currentPosition + 1 );
                if ( ! solved ) {
                    unset( currentPosition );
                }
            }
        }
    }
}

这假设棋盘本身是 Puzzle 的成员，并且该 Puzzle 还包含一个标志，告诉您何时找到一个解决方案。