c++ - 生成数独谜题所需的时间

标签 c++ performance debugging sudoku

<分区>

我正在编写一个数独谜题生成器,但当我编译和运行该程序时,我看到的只是一个空白的控制台终端。我已经等了 1 小时,但它仍然是一个空白的控制台终端。我想知道它是因为任何逻辑错误还是因为它仍在处理中。请注意,我的整个代码超长。如果它是性能问题,我该如何优化它

谢谢

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>

using namespace std;
bool checkrow(int row,int value,int array[][9]);

void producearray(int array[][9]);

bool checksquare(int row,int col,int value,int array[][9]);
bool checkcol(int col,int value,int array[][9]);
void populatearray(int array[][9]);

void printarray(int array[][9]);


int main()
{
int array[9][9];
populatearray( array);
producearray(array);
printarray(array);


system("PAUSE");





}

bool checkrow(int row,int value,int array[][9])// checks the entire row, returns false if any two numbers in the row are the same
{
for (int j=0;j<9;j++)
{
    if (value==array[row][j])
    {
        return false;


    }


}

return true;



}

bool checkcol(int col,int value,int array[][9]) // check if any two numbers in the same column are the same
{
for (int j=0;j<9;j++)
{
    if (value==array[j][col])
    {
        return false;


    }


}

return true;

bool checksquare(int row,int col,int value,int array[][9]) //checks if the number within the same square are the same
{
if  ( ( row>=0 &&  row<=2) && (col>=0 && col<=2) )
{
    for (int i=0;i<=2;i++)
    {
        for (int j=0;j<=2;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;


}

 else if  ( ( row>=0 &&  row<=2) && (col>=3 && col<=5) )
{
    for (int i=0;i<=2;i++)
    {
        for (int j=3;j<=5;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;



}

else if  ( ( row>=0 &&  row<=2) && (col>=6 && col<=8) )
{
    for (int i=0;i<=2;i++)
    {
        for (int j=6;j<=8;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;



}


 else if  ( ( row>=3 &&  row<=5) && (col>=0 && col<=2) )
{
    for (int i=3;i<=5;i++)
    {
        for (int j=0;j<=2;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;



}

else if  ( ( row>=3 &&  row<=5) && (col>=3 && col<=5) )
{
    for (int i=3;i<=5;i++)
    {
        for (int j=3;j<=5;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;



}

 else if  ( ( row>=3 &&  row<=5) && (col>=6 && col<=8) )
{
    for (int i=3;i<=5;i++)
    {
        for (int j=6;j<=8;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;



}

else if  ( ( row>=6 &&  row<=8) && (col>=0 && col<=2) )
{
    for (int i=6;i<=8;i++)
    {
        for (int j=0;j<=2;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;



}

 else if  ( ( row>=6 &&  row<=8) && (col>=3 && col<=5) )
{
    for (int i=6;i<=8;i++)
    {
        for (int j=3;j<=5;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;
}

 else if  ( ( row>=6 &&  row<=8) && (col>=6 && col<=8) )
{
    for (int i=6;i<=8;i++)
    {
        for (int j=6;j<=8;j++)
        {
            if (array[i][j]== value)
            {
                return false;

            }

        }


    }

    return true;
}






}

void producearray(int array[9][9]) //produces the array
{
bool isrow;
bool iscol;
bool issquare;

for (int i=0;i<9;i++)
{
    for (int j=0;j<9;j++)
    {
        do
        {
        array[i][j]=rand()%9+1;
         isrow=checkrow(i,array[i][j],array);
         iscol=checkcol(j,array[i][j],array);
         issquare=checksquare(i,j,array[i][j],array);




        }
           while(isrow==false || iscol==false || issquare==false);

    }



}

void populatearray(int array[][9]) // populate the arary
{
for (int i=0;i<9;i++)
{

    for (int j=0;j<9;j++)
    {
        array[i][j]=0;


    }


}




}

void printarray(int array[][9]) //prints the array
{
for (int i=0;i<9;i++)
{

    for (int j=0;j<9;j++)
    {
        cout<<array[i][j]
            <<"\t";


    }
    cout<<endl;


}



}

最佳答案

您做错了。您的代码试图通过随机化每个字段来生成有效的数独,一个一个地检查是否存在冲突。这很可能会导致这样的问题,即当数独的一部分已经填满时,就没有有效的解决方案了。这样的死锁一直在发生。现有的数字不冲突,但没有办法填补其余部分。只需从报纸上拿一个数独,然后随机填写几个字段,这样它们就不会立即发生冲突。很可能,您将无法再完成数独游戏。

这个问题使数独成为一个难题,而您的程序会忽略它 - 所以它一定会失败(除非随机生成器今天真的,真的真的幸运).

生成数独的更好方法是从已知的有效数独开始,而不是交换行和列(始终在 3 行/列 block 内),以及三行/列的整个 block ,以及交换数字(例如将每 3 替换为 7,同时将每 7 替换为 3),以便每次交换都保持整个数独有效。

关于c++ - 生成数独谜题所需的时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13800801/

相关文章:

python - 在 python 2.7 中有效的循环

android - Android应用程序调试的瓶颈是什么?

c++ - 生成不同的随机数

c++ - 增长 managed_shared_memory 段后出现段错误

c++ - 比较c++中的两个数组并根据元素的匹配或不匹配返回值

python - 将嵌套循环计算转换为 Numpy 以加快速度

c++ - 常量和全局

java - 有或没有临时变量交换数字的性能差异

.net - 如何检测是否已连接调试器*以及*是否已设置或命中断点?

java - Eclipse 不使用圆圈指示断点