数独怎么做?

数独怎么做?,第1张

单向扫看法:在第一个例子中,我们注意看一下第2宫。

我们知道,每个宫内必须包含数字9,第1宫以及第3宫中都包含数字9,并且第1宫的9位于第3行。

第3宫的9位于第2行,这也就意味着第2宫的9不能在第2行和第3行,所有第2宫的敬弯9只能放置在第2宫第1行的空格内。

2.双向扫看法:同样的技巧也可以扩展到相互垂直的行与列中。让我们想一下第3宫中1应该放在哪里。在这个例子中,第1行以及第2行已经有1了,那么第3宫中只有底部的俩个空格可以填1。不过,方格g4已经有1了,所有第g列不能再有1。

所以i3是该宫唯一符合条件填上数字1的地方。

3.寻找候选法:通常地,一个方格只能有一个数字的可能性,因为剩下的其他8个数字都已经被相关的行列宫所排除了。我们看一下下面例子中b4这个方格。b4所在的宫中已经存在了数字3,4,7,8,1和6位于同一行,5和9位于同一列,排除上述所有数字,b4只能填上2。

4数字排除法:排除法是一培稿巧个相对繁杂的寻找数字的方法。我们可以从c8中的1间接推出e7和e9必须包含数字1,不管这个1在哪个方格,我们可以确认的是,第e列的数字1肯定在第8宫内,所以第2宫内中配键间这一列就不可能存在数字1。因此,第2宫的数字一必须填在d2处。

用0代表要填的数

#include <stdio.h>

#include <stdlib.h>

#define SIZE 9

#define get_low_bit(x) ((~x&(x-1))+1)

struct{

int left

char num

char try

}board[SIZE][SIZE]

int bit2num(int bit)

{

switch(bit){

case 16:

case 256:

return 9

基础解法

排除法(摒除法)

摒除法:用数字去找单元内唯一可填空格,称为摒除法,数字可填唯一空格称为排除法 (Hidden Single)。

根据不同的作用范围,摒余解可分为下述三种:

数字可填唯一空格在「宫」单元称为宫排除(Hidden Single in Box),也称宫摒除法。

数字可填唯扰大一空格在「行」单元称为行排除法缓肢竖(Hidden Single in Row),也称行摒饥雀除法。

#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 = 0i <81i++)

{

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 = 0i <81i++)

{

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 = 1m <= 9m++)

{

bool mm = true

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

{

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()

}


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/12564800.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-26
下一篇 2023-05-26

发表评论

登录后才能评论

评论列表(0条)

保存