测试dfs subtraction(测试不通过）求助：

95 阅读 0 评论 63 点赞

我是靠谱客的博主细腻睫毛膏，最近开发中收集的这篇文章主要介绍测试dfs subtraction(测试不通过）求助：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

QQ及邮箱：1 4 2 3 1 7 3 7 8 3 @qq.com

//随机生成任意空格题目（终盘随机，随机挖洞），然后测试任意解数独题的算法
//test时只做45检测
#include<iostream>
#include<fstream>
#include<vector>
#include<time.h>
#include<cstdlib>
using namespace std;
#define BLANKS   59
#define FAIL     20
int table[9][9],table_for_solve[9][9],solves=0;
struct{                       //考虑到原来用结构体，这里就没变只是在原来的基础上改动，估计时间复杂度也没啥变化。
    int semaphore[10];
} node[10][10];
int probable[10][10],storage[10][10];
int finished=0;
fstream out_stream;
vector<int> must_add1;    //must_add1,must_add2是subtraction用来保存作业记录用的，作业记录保存在must_add2中，恢复也从must_add2中恢复
vector<vector<int>> vstart,must_add2;//vstart用来存储填格子的先后顺序（i,j) 填了k

void shuffle(int arr[], int n);
bool test(int x, int y, int v);
bool put(int line, int index);
bool put_line(int line);
void print_all();
void dfs();
int check(int y,int x,int *mark) ; //求probable[y][x] 并且mark[]中为0的元素说明可以试探
int solve22();
bool create_game(int blanks);
void create_gameover();
void print_all(int k); //输出到文件
void copy(int a[9][9],int b[9][9]);

void fills_up();
void subtraction(int row,int col,int k);
void add(int k);
void print_storage();
void print_probable();
void DFS();
int solve();
bool test(); //这个函数我真不想设置，但为了确保做出来的题目符合要求还是设置，如果做一个题目多耗时可能就1ms，可是做1000000个题目耗时就不小了。

void shuffle(int arr[], int n)
{
    int tmp, rd;
    for(int i = 0; i < n; i++)
{
        rd = rand() % 9;
        tmp = arr[rd];
        arr[rd] = arr[i];
        arr[i] = tmp;
    }
}
bool test(int x, int y, int v)
{
    int _x = x / 3 * 3;
    int _y = y / 3 * 3;
    for(int i = _x; i < _x + 3; i++)                  //测试3 * 3矩阵内是否有重复的数
    {
        for(int j = _y; j < _y + 3; j++)
        {
            if(table[i][j] == v)
            {
                return false;
            }
        }
    }
    for(int i = 0; i < 9; i++)                       //测试横向、纵向是否有重复的数
    {
        if(table[x][i] == v || table[i][y] == v)
            return false;
    }
    return true;
}
bool put(int line, int index)
{
    if(index > 8)
        return true;
    int num[] = {1,2,3,4,5,6,7,8,9};
                                                  //打乱当前准备写入数字的前后顺序
    shuffle(num, 9);
    for(int i = 0; i < 9; i++)
                                                       //测试数字是否允许填入当前方格
        if( test(line, index, num[i]) == true )
  {
            table[line][index] = num[i];
                                                       //填入成功则处理下一个方格
            if( put(line, index + 1) == true )
                return true;
        }
    table[line][index] = 0;                           //失败后复位
    return false;
}
bool put_line(int line)
{
    if(line > 8)
        return true;
    if( put(line, 0) == true )
                                                               //当前一行添入完成后，进入下一行再重复处理。
        if( put_line(line + 1) == true )
            return true;
    for(int i = 0; i < 9; i++)
        table[line][i] = 0;
    return false;
}
void print_all()
{
cout<<"print storage"<<endl;
   for(int i=1;i<=9;i++)
     {
    for(int j=1;j<=9;j++)
     {
   cout<<table[i-1][j-1]<<" ";
     if(j%3==0) cout<<"   ";
     }
    cout<<endl;
    if(i%3==0) cout<<endl;
     }
   cout<<endl<<endl;
}
void dfs()
{
int i,j,im=-1,jm,min=10;
int mark[10];
for(i=0;i<9;++i)
      for(j=0;j<9;++j)
         {
            if(table_for_solve[i][j])
               continue;
            int c=check(i,j,mark);
            if(c==0)
                return;
            if(c<min)
              {
                 im=i;
                 jm=j;
                 min=c;
              }
         }
if(im==-1)
{
   solves++;
   if(solves==2)
    throw(1);                //如果解法不唯一，不会等到所有解都出来才结束运行，保留下面的return又能确定是不是只有唯一解。
   return;
}
check(im,jm,mark);
for(i=1;i<=9;++i)
    if(mark[i]==0)
       {
          table_for_solve[im][jm]=i;
          dfs();
       }
table_for_solve[im][jm]=0;
}
int solve22()
{
try
{
  dfs();
  solves=0;   //调试后发现
  return(1);
}
catch(int)
{
  solves=0;   //调试后发现，solves是全局变量，以后solves越来越大永远不可能等于2
  return(2);
}
}
int check(int y,int x,int *mark) //求probable[y][x]
{
int i,j,is,js,count=0;
for(i=1;i<=9;++i)
mark[i]=0;
for(i=0;i<9;++i)
mark[table_for_solve[y][i]]=1;
for(i=0;i<9;++i)
mark[table_for_solve[i][x]]=1;
is=y/3*3;
js=x/3*3;
for(i=0;i<3;++i)
    for(j=0;j<3;++j)
       mark[table_for_solve[is+i][js+j]]=1;
for(i=1;i<=9;++i)
    if(mark[i]==0)
      count++;
return count;
}
bool create_game(int blanks)
{
int i,k,row,col,tmp;
for( i=1;i<=blanks;i++)
{
  int num=0;
  do
  {
   do
   {
    k=rand()%81;
    row=k/9;
    col=k-9*row;
    tmp=table[row][col];
   }while(tmp==0);
   table[row][col]=0;
   copy(table_for_solve,table);
   num++;
   if(num==FAIL)   return(false);
  }while((solve22()==2)? table[row][col]=tmp : 0);
}
if(i==blanks+1) return (true);
}
void create_gameover()
{
for(int i=0;i<9;i++)
  for(int j=0;j<9;j++)
   table[i][j]=0;
for(int i = 0; i < 9; i++)
        table[0][i] = i + 1;
    shuffle(table[0], 9);
                                                        //从第二行开始添入数字
    while(!put_line(1))   ;
}
void print_all(int k)
{
   for(int i=1;i<=9;i++)
     {
    if(i%3==1) out_stream<<endl;
  for(int j=1;j<=9;j++)
     {
      if(j%3==1) out_stream<<" ";
   out_stream<<table[i-1][j-1];
     }
    out_stream<<endl;
     }
   out_stream<<endl<<endl;
}
void copy(int a[9][9],int b[9][9])
{
for(int i=0;i<=8;i++)
  for(int j=0;j<=8;j++)
   a[i][j]=b[i][j];
}

void fills_up()
{
for(int i=1;i<=9;i++)
  for(int j=1;j<=9;j++)
  {
   for(int k=1;k<=9;k++)
           node[i][j].semaphore[k]=1;
            storage[i][j]=0;
   probable[i][j]=9;
  }
}
void subtraction(int row,int col,int k)
{
finished++;
for(int j=1;j<=9;j++)
  if(node[row][j].semaphore[k]==1)
         {
    must_add1.push_back((row-1)*9+j);
    node[row][j].semaphore[k]--;
    probable[row][j]--;
      }
for(int i=1;i<=9;i++)
  if(node[i][col].semaphore[k]==1)
        {
    must_add1.push_back((i-1)*9+col);
       node[i][col].semaphore[k]--;
    probable[i][col]--;
      }
   int rom=(row-1)/3*3+1+(col-1)/3;
   int row_room=(rom-1)/3*3+1,col_room=(rom-1)%3*3+1;
   for(int i=row_room;i<=row_room+2;i++)
    for(int j=col_room;j<=col_room+2;j++)
     if(node[i][j].semaphore[k]==1)
          {
      must_add1.push_back((i-1)*9+j);
      node[i][j].semaphore[k]--;
      probable[i][j]--;
       }
   if(must_add1.size()==0) must_add1.push_back(0);
   must_add2.push_back(must_add1);
   must_add1.clear();
}
void add(int k)
{
finished--;
int t=must_add2.size()-1,row,col;
if(must_add2[t][0]==0) { must_add2.pop_back();return;}
for(int j=must_add2[t].size()-1;j>=0;j--)
{
  row=(must_add2[t][j]-1)/9+1;   col=must_add2[t][j]-9*(row-1);
  node[row][col].semaphore[k]++;
  probable[row][col]++;
}
must_add2.pop_back();
}
void print_storage()
{
out_stream<<"print storage"<<endl;
   for(int i=1;i<=9;i++)
     {
    for(int j=1;j<=9;j++)
     {
   out_stream<<storage[i][j]<<" ";
     if(j%3==0) out_stream<<"   ";
     }
    out_stream<<endl;
    if(i%3==0) out_stream<<endl;
     }
   out_stream<<endl<<endl;
}
void print_probable()
{
out_stream<<"print probable"<<endl;
   for(int i=1;i<=9;i++)
     {
    for(int j=1;j<=9;j++)
     {
   out_stream<<probable[i][j]<<" ";
     if(j%3==0) out_stream<<"   ";
     }
    out_stream<<endl;
    if(i%3==0) out_stream<<endl;
     }
   out_stream<<endl<<endl;
}
void DFS()
{
int count=10,row=-1,col;
for(int i=1;i<=9;i++)
   for(int j=1;j<=9;j++)
    if(probable[i][j]<=count && storage[i][j]==0)
    {
     count=probable[i][j];
     row=i;
     col=j;
    }
    if(row==-1) throw(1);
if(count==0) return;
for(int k=1;k<=9;k++)
  if(node[row][col].semaphore[k]==1)
  {
   vector<int> v1;
   int must_recover[12]={0};
   for(int i=1;i<=9;i++)
    must_recover[i]=node[row][col].semaphore[i];
   must_recover[10]=storage[row][col];
   must_recover[11]=probable[row][col];
   for(int i=1;i<=9;i++)
    node[row][col].semaphore[i]=0;
   storage[row][col]=k;
   probable[row][col]=0;
   v1.push_back(row); v1.push_back(col); v1.push_back(k); vstart.push_back(v1); v1.clear();
   subtraction(row,col,k);
   DFS();
   add(k); vstart.pop_back();
   for(int i=1;i<=9;i++)
    node[row][col].semaphore[i]=must_recover[i];
   storage[row][col]=must_recover[10];
   probable[row][col]=must_recover[11];
  }
}
int solve()
{
try
{
   DFS();
   return(0);
}
catch(int)
{
  return(1);
}
}
bool test()
{
int sum=0;
for(int i=1;i<=9;i++)
{
  sum=0;
  for(int j=1;j<=9;j++)
   sum+=storage[i][j];
  if(sum!=45) return(false);
}
for(int j=1;j<=9;j++)
{
  sum=0;
  for(int i=1;i<=9;i++)
   sum+=storage[i][j];
  if(sum!=45) return(false);
}
int rom_row,rom_col;
for(int rom=1;rom<=9;rom++)
{
  sum=0;
  rom_row=(rom-1)/3*3+1; rom_col=(rom-1)%3*3+1;
  for(int i=rom_row;i<=rom_row+2;i++)
   for(int j=rom_col;j<=rom_col+2;j++)
       sum+=storage[i][j];
  if(sum!=45) return(false);
}
return(true);
}

int main()
{
long time1;
vector<int> v1;
time1=clock();
out_stream.open("d:\my documents\visual studio 2010\projects\测试算法\测试dfs subjection.txt");
    srand((unsigned int)time(NULL));
for(unsigned op=1;op<=1000000;op++)
{
    int statistics;
create_gameover();
while(!create_game(BLANKS))
  create_gameover();
statistics=0;
for(int i=1;i<=9;i++)
  for(int j=1;j<=9;j++)
     if(table[i-1][j-1]!=0)
     {
       statistics++;
    v1.push_back(i);
       v1.push_back(j);
       v1.push_back(table[i-1][j-1]);
       vstart.push_back(v1);
       v1.clear();
     }
fills_up();
for(int i=0;i<vstart.size();i++)
{
   for(int k=1;k<=9;k++)
      node[vstart[i][0]][vstart[i][1]].semaphore[k]=0;
  probable[vstart[i][0]][vstart[i][1]]=0;
  storage[vstart[i][0]][vstart[i][1]]=vstart[i][2];
}
for(int i=0;i<vstart.size();i++)
  subtraction(vstart[i][0],vstart[i][1],vstart[i][2]);
solve();
if(statistics==22)
     { if(test()) ;
     else { out_stream<<"测试第"<<op<<"个题目——59空但解题失败"<<endl; print_all(1); print_storage();}
     }
else
  { out_stream<<"测试第"<<op<<"个题目——非59空"<<endl; print_all(1); print_storage();}
vstart.clear();
}
    time1=clock()-time1;
    out_stream<<"用时"<<time1/1000<<"秒"<<time1%1000<<"毫秒"<<endl;
    out_stream.close();
}