数独 算法 C语言 代码

一、步骤：

1.对每一个空格，根据规则推断它可能填入的数字，并存储它的所有可能值；

2.根据可能值的个数，确定填写的顺序。比如说，有些空格只有一种可能，那必然是正确的结果，首先填入。

3.将所有只有一种可能的空格填写完毕以后，回到步骤1，重新确定剩下空格的可能值；

4.当没有只有一种可能的空格时（即每个空格都有两种以上可能），按照可能值个数从小到大的顺序，使用深度（广度）优先搜索，完成剩下空格。

二、例程：

#include <windows.h>

#include <stdio.h>

#include <time.h>

 

char sd[81]

bool isok = false

 

//显示数独

void show()

{

 if (isok) puts("求解完成")

 else puts("初始化完成")

 

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

 {

  putchar(sd[i] + '0')

  if ((i + 1) % 9 == 0) putchar('\n')

 }

 putchar('\n')

}

 

//读取数独

bool Init()

{

 FILE *fp = fopen("in.txt", "rb")

 if (fp == NULL) return false

 fread(sd, 81, 1, fp)

 fclose(fp)

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

 {

  if (sd[i] >= '1' && sd[i] <= '9') sd[i] -= '0'

  else sd[i] = 0

 }

 show()

 return true

}

 

//递归解决数独

void force(int k)

{

 if (isok) return

 if (!sd[k])

 {

  for (int m = 1 m <= 9 m++)

  {

   bool mm = true

   for (int n = 0 n < 9 n++)

   {

    if ((m == sd[k/27*27+(k%9/3)*3+n+n/3*6]) || (m == sd[9*n+k%9]) || (m == sd[k/9*9+n]))

    {

     mm = false

     break

    }

   }

   if (mm)

   {

    sd[k] = m

    if (k == 80)

    {

     isok = true

     show()

     return

    }

    force(k + 1)

   }

  }

  sd[k] = 0

 }

 else

 {

  if (k == 80)

  {

   isok = true

   show()

   return

  }

  force(k + 1)

 }

}

 

int main()

{

 system("CLS")

 if (Init())

 {

  double start = clock()

  force(0)

  printf("耗时%.0fms", clock() - start)

 }

 else puts("初始化错误")

 getchar()

}

#include<stdio.h>

int result=0 //结果数

int main()

{

int a[9][9]

void Sudoku(int a[9][9],int n)

printf("请输入数独中的原始数据，没有数据的用0代替。\n")

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

{

 printf("请输入第%d行的9个数：",i+1)

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

  scanf("%d",&a[i][j])

}

printf("数独的解为：\n\n")

Sudoku(a,0)

if(result==0)

 printf("此数独无解!")

return 0

}

//输出可行的解

void print(int a[9][9])

{

result++

printf("第%d个填法为：\n",result)

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

{

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

 {

  printf("%d ",a[i][j])

  if((j==2)||(j==5))

   printf(" ")

 }

 printf("\n")

 if((i==2)||(i==5))

  printf("\n")

}

printf("\n")

}

//判断是否可以将第i行、第j列的数设为k

bool check(int a[9][9],int i,int j,int k)

{

int m,n

//判断行

for(n=0n<9n++)

{

 if(a[i][n] == k)

  return false

}

//判断列

for(m=0m<9m++)

{

 if(a[m][j] == k)

  return false

}

//判断所在小九宫格

int t1=(i/3)*3,t2=(j/3)*3

for(m=t1m<t1+3m++)

{

 for(n=t2n<t2+3n++)

 {

  if(a[m][n] == k)

   return false

 }

}

//可行，返回true

return true

}

//数独求解函数

void Sudoku(int a[9][9],int n)

{

int temp[9][9]

int i,j

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

{

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

  temp[i][j]=a[i][j]

}

i=n/9 j=n%9 //求出第n个数的行数和列数

if(a[i][j] != 0) //已经有原始数据

{

 if(n == 80)   //是最后一个格子，输出可行解

  print(temp)

 else    //不是最后一个格子，求下一个格子

  Sudoku(temp,n+1)

}

else    //没有数据

{

 for(int k=1k<=9k++)

 {

  bool flag=check(temp,i,j,k)

  if(flag) //第i行、第j列可以是k

  {

   temp[i][j]=k //设为k

   if(n == 80)

    print(temp)

   else

    Sudoku(temp,n+1)

   temp[i][j]=0 //恢复为0，判断下一个k

  }

 }

}

}

用MATLAB的GUI制作一个数独游戏，可以下来方法来制作

1、首先用guide命令，打开GUI模板，搭建数独游戏的界面（界面可以根据自己的喜好搭建）

2、其二对每个组件的特性进行定义编辑，同时输入相应的执行代码

3、然后保存，调试，运行

4、数独的主要计算代码

%找出A中一个最小数(一般为0)的位置(row,col)

[row,col]=find(temp==min(min(temp)))

row=row(1)col=col(1)

%找出(row,col)位置所有可能的元素

r=A(row,:)c=A(:,col) 

rc1=union(r,c)

rr=ceil(row./3)-1

cc=ceil(col./3)-1

rc2=A(rr*3+1:rr*3+3,cc*3+1:cc*3+3)

total=union(rc1,rc2(:))

P= setdiff([1:9],total)

5、下面是没有嵌入GUI的界面的运算结果

---