C++ 利用回顾算法算数独出错，求解答

2013-01-28

C++ 利用回溯算法算数独出错，求解答小弟是新手，要做一个数独的游戏，参照了一个求解数独的经典代码。但发现

C++ 利用回溯算法算数独出错，求解答
小弟是新手，要做一个数独的游戏，参照了一个求解数独的经典代码。但发现必须在debug里输入元素才能求解，我尝试把pu[9][9]变成pu[9][9]={{}}（里面的数字省略了，绝对是正确的数独）后。发现无法在debug里显示任何东西，请问是怎么回事。
#include <iostream>
#include <stdio.h>
using namespace std;
static int pu[9][9];
int isvalid(const int i, const int j)
{
const int n = pu[i][j];
const static int query[] = {0, 0, 0, 3, 3, 3, 6, 6, 6};
int t, u;

for (t = 0; t < 9; t++)
  if (t != i && pu[t][j] == n || t != j && pu[i][t] == n)

   return 0;

  for (t = query[i]; t < query[i] + 3; t++)
   for (u = query[j]; u < query[j] + 3; u++)
    if ((t != i || u != j) && pu[t][u] == n)
     return 0;

    return 1;
}
void output(void)
{
static int n;

printf("Solution is:\n");

for (int i = 0; i < 9; i++) {
  for (int j = 0; j < 9; j++)
   cout<< pu[i][j] << " ";
  cout << endl;
}

cout << endl;
}

void Try(const int n)
{
if (n == 81)
  {output();
  return;
}

const int i = n / 9, j = n % 9;

if (pu[i][j] != 0)
{
  Try(n + 1);
  return;
}

for (int k = 0; k < 9; k++) {
  pu[i][j]++;
  if (isvalid(i, j))
   Try(n + 1);
}

  pu[i][j] = 0;
}
int main(void)
{
int i,j;
for (i=0;i<9;i++)
{
  for (j=0;j<9;j++)
  {
  cin>>pu[i][j];
  }
}
  Try(0);
  return 0;
}（这是原程序）
我把这程序改成了：
#include <iostream>
#include <stdio.h>
using namespace std;
static int pu[9][9]={{0,1,4,0,5,0,0,0,3},{6,0,0,0,0,9,4,2,0},{8,0,0,1,0,0,0,9,0},{0,0,5,0,9,0,0,4,0},{4,0,0,7,0,8,0,5,2},{0,7,0,0,2,0,6,0,0},{0,9,0,0,0,1,0,0,5},{0,2,8,3,0,0,0,0,4},
{5,0,0,0,6,0,7,1,0}};
int isvalid(const int i, const int j)
{
const int n = pu[i][j];
const static int query[] = {0, 0, 0, 3, 3, 3, 6, 6, 6};
int t, u;

for (t = 0; t < 9; t++)
  if (t != i && pu[t][j] == n || t != j && pu[i][t] == n)

   return 0;

  for (t = query[i]; t < query[i] + 3; t++)

   for (u = query[j]; u < query[j] + 3; u++)
    if ((t != i || u != j) && pu[t][u] == n)
     return 0;

    return 1;
}
void output(void)
{
static int n;

printf("Solution is:\n");

for (int i = 0; i < 9; i++) {
  for (int j = 0; j < 9; j++)
   cout<< pu[i][j] << " ";
  cout << endl;
}

cout << endl;
}

void Try(const int n)
{
if (n == 81)
  {output();
  return;
}

const int i = n / 9, j = n % 9;

if (pu[i][j] != 0)
{
  Try(n + 1);
  return;
}

for (int k = 0; k < 9; k++) {
  pu[i][j]++;
  if (isvalid(i, j))
   Try(n + 1);
}

  pu[i][j] = 0;
}
int main(void)
{
int pu[9][9]={{0,1,4,0,5,0,0,0,3},{6,0,0,0,0,9,4,2,0},{8,0,0,1,0,0,0,9,0},{0,0,5,0,9,0,0,4,0},{4,0,0,7,0,8,0,5,2},{0,7,0,0,2,0,6,0,0},{0,9,0,0,0,1,0,0,5},{0,2,8,3,0,0,0,0,4},
{5,0,0,0,6,0,7,1,0}};


  Try(0);
  return 0;
}
后果就是debug里面什么都没有，请问是怎么一回事
[解决办法]
把main改成这样试试：


int main(void)
{
    int m_pu[9][9] =
    {
        {0,1,4,0,5,0,0,0,3},
        {6,0,0,0,0,9,4,2,0},
        {8,0,0,1,0,0,0,9,0},
        {0,0,5,0,9,0,0,4,0},
        {4,0,0,7,0,8,0,5,2},
        {0,7,0,0,2,0,6,0,0},
        {0,9,0,0,0,1,0,0,5},
        {0,2,8,3,0,0,0,0,4},
        {5,0,0,0,6,0,7,1,0}
    };
    for (int i = 0; i < 9; ++i)
    {
        for (int j = 0; j < 9; ++j)
        {
            pu[i][j] = m_pu[i][j];
        }
    }
    Try(0);
    return 0;
}

数独，在回溯过程中，应用一些“余数法”，比如：显式唯一余数、隐式唯一余数、对数法、宫格删除法等，可以把计算效率提升很多的（是减少了很多的尝试）。
我算了一下，你这个数独有唯一解：
9 1 4 2 5 6 8 7 3
6 5 7 8 3 9 4 2 1
8 3 2 1 4 7 5 9 6
2 8 5 6 9 3 1 4 7
4 6 9 7 1 8 3 5 2

3 7 1 5 2 4 6 8 9
7 9 6 4 8 1 2 3 5
1 2 8 3 7 5 9 6 4
5 4 3 9 6 2 7 1 8

热点排行

C++

C++ 利用回顾算法 算数独出错，求解答

C++ 利用回顾算法算数独出错，求解答