数独 算法 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>

typedef struct

{

int line

int row

int num

}Node

int main()

{

/*

int a[9][9]={

{4,0,3,6,0,0,0,0,0},

{0,0,0,0,0,1,0,2,4},

{0,1,0,0,4,0,5,0,0},

{0,0,0,9,0,4,0,6,0},

{3,0,2,0,0,0,4,0,9},

{0,7,4,1,0,3,0,0,0},

{0,0,1,0,9,0,0,4,0},

{2,4,0,3,0,0,0,0,0},

{0,0,0,4,0,8,2,0,7}}

*/

int a[9][9]={

{0,0,0,8,0,0,0,6,0},

{8,7,0,0,0,0,0,0,0},

{2,9,0,0,4,1,0,0,5},

{0,0,5,7,0,0,0,0,9},

{0,2,0,0,0,0,0,1,0},

{9,0,0,0,0,4,3,0,0},

{7,0,0,6,1,0,0,9,8},

{0,0,0,0,0,0,0,5,2},

{0,6,0,0,0,9,0,0,0}}

/*

int a[9][9]={

{0,2,0,0,6,0,0,0,0},

{0,9,0,4,0,5,1,3,0},

{0,0,8,7,0,0,0,0,5},

{6,0,0,3,0,0,4,0,0},

{0,0,0,9,0,6,0,0,0},

{0,0,7,0,0,1,0,0,3},

{4,0,0,0,0,7,3,0,0},

{0,8,5,2,0,4,0,7,0},

{0,0,0,0,9,0,0,1,0}}

*/

/*

int a[9][9]={

{0,0,3,0,2,0,0,0,6},

{0,0,2,0,9,0,0,0,4},

{7,0,0,8,0,0,2,0,3},

{0,8,0,0,7,0,5,0,0},

{0,7,0,1,0,6,0,3,0},

{0,0,0,2,0,0,0,9,0},

{4,0,6,0,0,8,0,0,5},

{6,0,0,0,4,0,3,0,0},

{9,0,0,0,1,0,7,0,0}}

*/

int i,j,n,en,flag,y,k=0,x,qu,p,q

Node b[70]

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

{

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

{

if(!a[i][j])

{

b[k].line=i

b[k].row=j

b[k].num=0

k+=1

}

}

}

en=k

/*从b[0]开始试，若b[k].num>9,则k-1,否则k+1*/

for(k=0k<en)

{

++b[k].num

i=b[k].line

j=b[k].row

a[i][j]=b[k].num

n=0

while(n<9&&b[k].num<=9)

{

if(n==i)

{

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

{

if(y==j)

continue

if(a[n][y]==a[i][j])

flag=1

}

}

else if(n==j)

{

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

{

if(y==i)

continue

if(a[y][n]==a[i][j])

flag=1

}

}

/*判断同一块中有郑碧没有相同值*/

qu=3*(i/3)+j/3

switch(qu)

{

case 0:x=0

y=0

break

case 1:x=0

y=3

break

case 2:x=0

y=6

break

case 3:x=3

y=0

break

case 4:x=3

y=3

break

case 5:x=3

y=6

break

case 6:x=6

y=0

break

case 7:x=6

y=3

break

default :x=6

y=6

break

}

p=x

q=y

for(x<p+3x++)

{

for(y<q+3y++)

{

if(x==i&&y==j)

continue

if(a[x][y]==a[i][j])

{

flag=1

break

}

}

if(flag==1)

break

}

if(flag==1)

{

a[i][j]=++b[k].num

flag=0

n=0

continue

}

n++

}

if(b[k].num>9)

{

a[i][j]=b[k].num=0

k--

if(k<0)

{

printf("error!\r\n")

return -1

}

}

else

k++

}

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

{

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

{

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

}

printf("\r\n")

}

return 1

}

void readGame (sudukoGrid game) {

cell currentCell = 0

int inChar = getchar()

while (inChar != EOF) {

if (

((inChar >= MIN_VALUE) &&(inChar <搏档枝= MAX_VALUE)) ||

(inChar == EMPTY_VALUE)

) {

assert (currentCell <= MAX_CELL)

game [currentCell] = inChar

currentCell++

}

inChar = getchar()

}

assert (currentCell == (MAX_CELL+1))

}

第一基敏个readgame，蠢答谁会别的？

---