淘先锋技术网

首页 1 2 3 4 5 6 7

数独九宫格游戏

一.题目说明 

数独的游戏规则:

1、在9×9的大九宫格内,已给定若干数字,其他宫位留白,玩     家需要自己按照逻辑推敲出剩下的空格里是什么数字。
   2、必须满足的条件:每一行与每一列都有1到9的数字,每个小    九宫格里也有1到9的数字,并且一个数字在每行、每列及每   个小九宫格里只能出现一次,既不能重复也不能少。
   3、每个数独游戏都可根据给定的数字为线索,推算解答出来。

按照数独的游戏规则,用计算机实现已知数独的求解和数独题目的出题。

二.数据结构说明

数据结构一维数组、二维数组以及类似于“栈”的数据结构。

主要操作有:进栈,出栈,栈顶元素的操作等等

三.抽象数据类型

五个全局变量数组,其中两个二维数组,三个一维数组。

int a[10][10]

int sd[82]

int fix[82]

int possible[82][10]

int stack[82]

四.算法设计

程序可以考虑人工智能的算法。采用人机的游戏方式,这里采用“回溯”的方法解决数独问题。

基本框架如下:

 

 图片粘贴不了

 

 

五.数独程序代码:

   #include"stdio.h" //标准输入输出头文件

#include"conio.h" //包含getch()的头文件

#include"stdlib.h" //包含rand()的头文件

#include"assert.h" //包含assert()的头文件

#include"time.h" //包含srand()的头文件

int a[10][10];//用来接收输入数据的数组

int sd[82];//处理题目以及保存最终结果

int fix[82];//记录哪些位置是确定的,确定为1,否则为0

int possible[82][10];//记录所有未确定数字的可能性

int stack[82];//用来放置填入的数的栈

int t;

void clssd()//初始化函数,所有位置设为0

{

   int i,j,k;

   for(i=0;i<9;i++)

      for(j=0;j<9;j++)

         a[i][j]=0;

   for(k=1;k<=81;k++)

      sd[k]=0;

}

int line(int line,int value)//检验行

{

   int i;

   for(i=1;i<=9;i++)

   {

      if(a[line][i]==value) return 0;

   }

   return 1;

}

int row(int row,int value)//检验列

{

   int i;

   for(i=1;i<=9;i++)

   {

      if(a[i][row]==value) return 0;

   }

   return 1;

}

int square(int line,int row,int value)//检验3*3的九宫

{

   int L,R,i,j;

   L=(line%3!=0)+line/3;//L表示所在九宫的行数

   R=(row%3!=0)+row/3;//R表示所在九宫的列数

   for(i=(L-1)*3+1;i<=L*3;i++)

   {

      for(j=(R-1)*3+1;j<=R*3;j++)

         if(a[i][j]==value) return 0;

   }

   return 1;

}

   int transform_to_line(int i)

   {

      int line;

      line=i/9+(i%9!=0);

      return line;

   }

   int transform_to_row(int i)

   {

      int row;

      row=i%9+9*(i%9==0);

      return row;

   }

void transform_to_a(int i)

{

      int l,r;

      l=transform_to_line(i);

      r=transform_to_row(i);

      a[l][r]=sd[i];

}

void transform_to_sd()

{

   int line,row,i=1;

  

   for(line=1;line<=9;line++)

      for(row=1;row<=9;row++)

         do

         {

            sd[i]=a[line][row];

            i++;       

            break;

         }while(i<=81);

 

}

//输出函数

void printAll()

{

   int i;

   for(i=0;i<81;i++)

   { 

      if(i%9==0)

         printf("\n\n\t\t");

      printf("%4d",sd[i+1]);

  

   }

   printf("\n\n\n");

}

void input()//输入数据到a[10][10]

{

   system("cls");//清屏

   int b[3]={0,0,0},i,j;

   printf("请输入已知数据");

   printf("\n\n例如输入7 8 9,表示第8行 第9列的数值为7,以此类推。\n\n\n");

   do

   {       

      printf("\n输入数据:按照 值 / 行 / 列的顺序,以0结束");

      for(i=0;i<3;i++)

      {

         j=getch()-48;

         if(j==0&&i==0) break;//实现按0结束语句

         if(j>0&&j<10)

         {

            b[i]=j;

            printf("%3d",b[i]);

         }

         else i--;

      }

      a[b[1]][b[2]]=b[0];  

   }while(j); 

   transform_to_sd();

   printf("\n\n\n\t您输入的题目为:\n\n");//打印输入的数独

   printAll();

}

//三个重要函数

bool beExist(int i,int j)//判断 sd 数组中位置为 i 的元素是否存在

{

   int l,r;

   l=transform_to_line(i);

   r=transform_to_row(i);

   //if(sd[i]!=0) return 1; 关键的错误所在!!! 

   if(line(l,j)*row(r,j)*square(l,r,j)==0) return 1;

   else return 0;

}

void setPb()//控制possible数组

{

  

   int i,j;

   for(i=1;i<=81;i++)

   {    

      for(j=1;j<=9;j++)

      {

         if(sd[i]!=0) possible[i][j]=-1;

         else if( beExist(i,j))

         {possible[i][j]=-1;}

         else

         {possible[i][j]=j;}

      }

   }

 

}

bool fixAll(int sd[],int fix[],int possible[82][10])//控制fix数组

{

   int i,j;

   int k[82]; 

   for(i=1;i<=81;i++)

   {

      if(sd[i]!=0)

      {fix[i]=1;}

      else

      {fix[i]=0;}

   } 

   for(i=1;i<=81;i++)

   {

      if(sd[i]!=0) continue;

      if(fix[i]==0)

      {

         for(j=1;j<=9;j++)

         if(possible[i][j]!=-1)

            k[i]++;

      }

      if(k[i]==1)//如果存在只有一种可能的位置则将fix[i]改为1

         fix[i]=1;

         sd[i]=possible[i][j];

   } 

   for(i=1;i<=81;i++)//判断是否存在只有一种可能的位置,若没有返回0

   {

      if(k[i]==1) return 1;

      else return 0;

   }

}

//判断是否完成

int isFull(int sd[])

{

   int i;

   for(i=1;i<=81;i++)

      if(sd[i]==0) return 0;  

   return 1;

}

void preDo()//预处理

{

   while(1)

   {

      setPb();

      if(!fixAll(sd,fix,possible)) //即不存在只有一种可能性的位置

         break;

      if(isFull(sd)) //若已经推出全部结果

         break;

   }

   if(isFull(sd))

      printAll();//打印结果

 

}

int calculate()//填数独 (关键算法!!!)

{

   preDo();//预处理,找出所有的位置的可能数值

   if(isFull(sd)) return 1;

   int top=0;

   //将所有为0的位置入栈

   for(int i=1;i<82;i++)

   { 

      if(fix[i]==0)

         stack[top++]=i;

   }

   int max=top;//记录最大数目加1

   top=0;//指向栈顶

   int temp;

   bool flag=true;//该标志位说明了当前是正常入栈

   while(1)

   {

      assert(top>=0);

      if(flag)

      {

         int j;

         for(j=1;j<=9;j++)

            if(possible[stack[top]][j]!=-1&&!beExist(stack[top],j))

            //若top所示的位置上,可以安插j这个数值,则

            {

                fix[stack[top]]=1;

                sd[stack[top]]=j;

                transform_to_a(stack[top]);

                ++top;

                if(top>=max) return 1;

                break;

            }

         if(j>9)//该空所有可能值都不可以,则退一格

         {

        

            --top;

            if(top<0) {printAll(); return 0;}

            flag=false;

         }

      }    

      else

      {

         if(sd[stack[top]]==9)

         {

            fix[stack[top]]=0;

            sd[stack[top]]=0;

            transform_to_a(stack[top]);

            --top;

            if(top<0) {printAll(); return 0;}

         }

         else

         {

            temp=sd[stack[top]];    

            temp++;

            while(possible[stack[top]][temp]==-1||beExist(stack[top],temp))

            {

                temp++;

                if(temp>9)

                break;

            }

            if(temp>9)//当前节点没有更换的可能性,继续退回

            {

                fix[stack[top]]=0;

                sd[stack[top]]=0;

                transform_to_a(stack[top]);

                --top;

                if(top<0) {printAll(); return 0;}

            }

            else

            {

                sd[stack[top]]=temp;

                transform_to_a(stack[top]);

                ++top;

                flag=true;

            }

         }

     

      }

   }

  

}

void solve_problem()//解题

{

   int p;

   system("cls"); //清屏

   clssd(); //赋初值为0

   input(); //输入数据

   transform_to_sd(); //转换为sd[i]数组

   p=calculate(); //计算数独

   if(p==0)

      printf("\t题目有误!!! ");

      printf("\n\n\t答案为:\n");

   printAll();

void random()//从1-9中随机产生几个值输入sd[1]至sd[9]

   { 

      int i,j,r;

      int change=1;

      int b[10]={0,0,0,0,0,0,0,0,0,0};

       for(i=1;i<=9;)//从1-9中随机产生几个值

       { 

         change=1;

         j=1+rand()%9;

         for(r=1;r<=9;r++)

            if(b[r]==j) change=0;

         if(change==1)

         {b[i]=j;  i++;}

       }

       

       for(i=1;i<=9;i++)

       {

         sd[i]=b[i];

         transform_to_a(i);

       }

   }

void hide()

   {

      int i,f;

      printf("请输入难度:\n\n1.Easy\n\n2.Normal\n\n3.Hard\n\n4.So Hard\n\n5.Terrible Hard\n\n");

      do

      {

         f=getch()-48;

      }while(f>5||f<1);//一共5个级别

  

      for(i=1;i<=81;i++)

      { 

         if(rand()%6>=f)//利用随机数出现的概率出题

         printf("%4d",sd[i]);

         else

            printf("   0");

         if(i%9==0)

            printf("\n\n");

      }

   }

void make_problem()//出题函数

   system("cls");//初始化

   clssd();

   random();//填9个随机值

   calculate();//算出答案

   hide();

   printf("\t\t\t注意:题目中0代表待填数据\n\n\t\t   按空格键输出答案,其他键退出程序\n");

   int f;

   do

   {

      f=getch()-32;

      if(!f)

         printAll();

      else break;

   }while(f);

}

void quit()

{

int i;

for(i=0;i<100;i++)

{

 printf("%d\n",i);

 if (i>2||i<1)

 {

  exit(1);

 }

}

}

void main()//主函数

{

   srand((unsigned)time(0));//设置时间种子为0

   system("cls");//清屏

   clssd();

   printf("\n\t数独游戏\n\n\t1.你出题,电脑来解\n\n\t2.电脑出题,你来解\n\n\t3.退出游戏");

   int i;

   do

   {

      i=getch()-48;

      switch(i)

      {

      case 1:solve_problem();

         break;

      case 2:make_problem();

         break;

      case 3:quit();

         break;

      }

   }while(i>2||i<1);

}

六.调试报告

1.整个程序最麻烦的地方是二维数组a[10][10]与一 维数组sd[82]之间的转换。因为输入数据为了方便 和符合人类的思维采用了与数独相似的二维数组   进行输入。但是回溯算法要求转换成一维数组进行  操作。

2.调试过程中,用到了一个宏命令assert(top>=0)  top是栈顶元素的“指针”,用来操控栈中元素。正  常情况下top>=0的。如果出现异常情况,则assert 函数会弹出对话框报错。这表示calculate函数在 回溯的时候top值总是会回到栈底元素之前。事实  上,开始因为在beExist()函数中用了错误的判断 方 式,运行程序时总是会使得top<0。

3.上一条中的错误之所以会出现,是因为在设计程序 之初没有想好,不够完善。于是出现了,自己设计 的判断方法与计算数独矛盾的结果。得到的教训   是,动手之前应该先考虑清楚完整的架构和应该考 虑到的细节.

 

七.测试结果分析

下面为规定测试数据:

 图片粘贴不了

 

 

 

 

 

 

 

 

 

 

 

 

 

转载于:https://www.cnblogs.com/wanghongcai/p/4839090.html