求用C语言编一个解九宫格数独的程序

前两天刚写完,还没优化,已运行通过了.

晕，一维的好麻烦，这个也是碰巧前两天刚写好的，你看着自己修改下

#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

}

数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

解题手法

依解题填制的过程可区分为直观法与候选数法。

直观法就是不做任何记号，直接从数独的盘势观察线索，推论答案的方法。

候选数法就是删减等位群格位已出现的数字，将剩余可填数字填入空格做为解题线索的参考，可填数字称为候选数(Candidates，或称备选数)。

直观法和候选数法只是填制时候是否有注记的区别，依照个人习惯而定，并非鉴定题目难度或技巧难度的标准，无论是难题或是简单题都可上述方法填制，一般程序解题以候选数法较多。

摒除法

摒除法：用数字去找单元内唯一可填空格，称为摒除法，数字可填唯一空格称为摒余解(Hidden Single)。

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

数字可填唯一空格在「宫」单元称为宫摒余解（Hidden Single in Box），这种解法称宫摒除法。

数字可填唯一空格在「行」单元称为行摒余解（Hidden Single in Row），这种解法称行摒除法。

数字可填唯一空格在「列」单元称为列摒余解（Hidden Single in Column），这种解法称列摒除法。

行摒余解和列摒余解合称行列摒余解（Hidden Single in Line）。

得到行列摒余解的方法称为行列摒除法。

余数法

Peer等位群格位

余数法：用格位去找唯一可填数字，称为余数法，格位唯一可填数字称为唯余解（Naked Single）。

余数法是删减等位群格位（Peer）已出现的数字的方法，每一格位的等位群格位有 20 个，如图七所示。

进阶解法

上述方法称为基础解法（Basic Techniques），其他所有的解法称为进阶解法（Advanced Techniques），是在补基本解法之不足，所以又称辅助解法。

进阶解法包括：区块摒除法（Locked Candidates）、数组法（Subset）、四角对角线（X-Wing）、唯一矩形（Unique Rectangle）、全双值坟墓（Bivalue Universal Grave）、单数链（X-Chain）、异数链（XY-Chain）及其他数链的高级技巧等等。已发展出来的方法有近百种之多。

其中前三种加上基础解法为一般数独书中介绍并使用的方法，同时也是大部分人可以理解并掌握的数独解题技法。

通过基础解法出数只需一种解法，摒除法或唯余法，超出此范围而需要施加进阶解法时，解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数，该解题点的解法需要多个步骤协力完成，因此称做组合解法。

解题必须以逻辑为依归，猜测的方法被称为暴力型解法(Brute Force)，这不是提倡数独的本意。

区块摒除法

区块摒除法包括宫区块摒除法（Pointing）与行列区块摒除法（Claiming）。

在基础题里，利用区块摒除可以替代一些基础解法的观察，或辅助基础解法寻找焦点。

在非基础题里，区块可以隐藏任何其他结构，简单的可以把基础解法隐藏起来，难的可以隐藏数对等等其他进阶技巧。

区块摒除法

首先数字6对第五宫摒除，得到第五宫的6在R4C5或者R6C5。

不论是在R4C5或者R6C5，C5的其他格都不能再有数字6。（R4C5与R6C5就是数字6的区块，这也是区块摒除作用的观点）

数字6对第二宫摒除，得解R1C4=6。

数对法

当一个单元（行、列、宫）的某两个数字仅可能在某两格时，我们称这两个格为这两个数的数对（Pairs）。

数对出现在宫称为宫数对；数对出现在行列成为行列数对。

用候选数法的观点去看，数对有两种，一种是在同单元内其中两格有相同的双候选数，一看就明白，因此称为显性数对（Naked Pair），另一种是，同单元内有两个候选数占用了相同的两格，该两格因为还有其它候选数很难辨认，因此称为隐性数对（Hidden Pair）。

数独是风靡全世界的填数字游戏。游戏的目的是在空格内填上1到9，每行、每列和每个3x3的小九宫格内的数字不能重复。这是个很有趣的游戏，但刚开始玩时可能有些棘手，让人摸不着头脑。

工具/原料

时间 当你有了一些经验后，简单及中等难度的数独只需10到20分钟。 中等及困难的数独需30到45分钟。 武士数独需花1到4小时（除非你非常熟练）。 杀手数独需花超过4小时。 铅笔 橡皮擦 耐心 逻辑思维

方法 1: 简单难度

1/6分步阅读

通过数1到9来解决谜题。既然你知道每行、每列和每个九宫格内不能出现相同的数字，你可以运用这个规则找到适当的数字。难度将取决于已知数字的位置。

2/6

寻找“唯一可填的数字”。想要解决简单的数独，你首先必须找出某个方格里唯一可填的数字，或是某个数字唯一可填的位置。从1开始，在有1的每一行和（或）每一列虚构一条线。当3x3九宫格内只剩一个没划线的方格，你就知道这肯定得填1

3/6

继续用上述方法寻找2到9的位置。填了几个数字后，一些之前有超过一个可能性的方格也能得到确定。注意，之前无法解决的3最后也确定了位置。

4/6

当你遇到困难时，可以重新检查一遍。遇到困难时，重新检查每一个方格和数字，你很有可能漏考虑了什么东西。通常只需要一个数字就能让你继续解决谜题。如果还是无法找到任何解决方法，那就开始在剩下的方格中，列出每一个可能的数字。

5/6

开始解报章或网上的数独题。报章上的数独通常有不同的难度，你可以留意各别等级的刊载规律（比如说每个周一和周二的题目比较容易，之后越来越难）。

6/6

尝试解决更难的数独题。

方法 2: 困难难度

1/4

从1开始。使用和简单难度同样的逻辑思维，列出每个空格中可以填入的所有数字。如果可以，尽量找出唯一可填的数字。

面对困难的数独题时，你无法从一开始就用利解决谜题，所以只需填下所有可能的数字。每个方格中都有两三个选择，把它们列出来能帮助你记住这些数字。

2/4

注意，如果某一九宫格、行或列中有两个方格只能填两个相同数字的其中之一，那么你可以用这两个数字排除其它的可能性。

3/4

困难的数独题可能要花很多时间才能解决。困难的数独题实际上可能要好几天才能解开，但还是很有趣。题目越难，完成后的乐趣越大。困难数独和简单数独的解决方法一样，只不过一开始它只给你比较少的已知数字。只要每个方格你都知道有哪些数字可以填，解起题来就会轻松许多哦。

比方说，在某个九宫格中有两个方格可以填2，它们位于同一行或同一列，而且九宫格中的其它方格都不能填2。这意味着2只能填在这个九宫格里两个方格之一，同一行或同一列的其它地方也不能再出现2。这个思考方法是很简单有用的。

4/4

考虑使用这个必能成功的替代方法，以准确、快速地解决谜题。在这个方法中，你需要列出每一个空格可以填入的所有数字。在空格上方写下所有可能的数字（字体要小）。你可以在比较大的纸上把题目重画一遍，确保方格有足够的填写空间。列出空格所在的那一行、列和九宫格中缺少的数字。完成所有行列后，开始填入显而易见的答案。每一行列填写完毕后，就能解决谜题。

方法 3: 武士数独

1/4

做个有自信的高难度数独玩家。武士数独是数独高手才能挑战的谜题，基本上由5个数独组成。每个数独其中一角的九宫格都与中间的数独重叠。这些数独很长，而且难度高。

2/4

时时留意重叠的九宫格。解决武士数独时，记住重叠的九宫格必须同时适用于两个数独。

3/4

注意比较长的行列。武士数独中有几个行列是由21个方格组成，看起来像是3个由9格组成的行列连在一起，而中间的行列又与左右两旁重叠。

4/4

像解决普通数独一样解决武士数独。你只需记得在比较长的行列中，同一个数字可以出现多达3次。

方法 4: 杀手武士数独

1/1

好好研究杀手武士数独。它结合了武士数独与数和的玩法，规则有些不同，而且以颜色划分“区”。标准的数独规则仍适用于杀手武士数独，也即是每个九宫格里必须填上1到9。

杀手武士数独规则

1/4

留意每个彩色方格里的小数字。这是同区的数字总和。例如，如果某个区有3个方格，总和为7，那么个别方格的数字必定是1、2和4，但玩家得自己确认数字的排列顺序。

2/4

注意，同区方格的数字可能重复，但可能性不大。

3/4

留意总和。每一行、列及九宫格里的数字总和必须是45。

4/4

了解在杀手数独中，有4个3x3九宫格同时属于两个不同的数独。在这种情况下，你需要遵守数独的规则，也即是1到9只能在九宫格里出现一次。因此，很显然的这4个九宫格是解决整个谜题的关键。

解谜技巧

1/6

先看看总和比较高或比较低的区。它们的数字组合比较少，因此更容易解决。

2/6

寻找跨越两个数独的颜色区（有一格在另一数独的九宫格里）。 利用同一行、列和九宫格数字不得重复的规则，你应该能确认区内至少一个方格的数字。

3/6

不要只想着每一行、列和九宫格的总和是45。有时候你可以把同一排的2、3、4或更多九宫格加起来，得到总和90、135或180等，以确认某个难以捉摸的数字。

4/6

找出跨越两个九宫格、总和比较高或低的颜色区。例如，图中总和为3的颜色区和总和为4的颜色区形成90度的夹角位置。你应该很容易推算出方格里的数字，因为只有3个数字可以选，那就是1、2和3 。但别忘了每一行列的数字（1到9）不得重复。

5/6

找出是否有些组合可以被排除。如果由2个方格组成的颜色区总和为4、6、8等，逻辑上这些方格不能填上同样的数字（例如2和2、3和3及4和4等），所以你可以排除这些组合。

6/6

寻找形成一排的颜色区。例如，如果4个各有2格的颜色区形成一排，你可以用总和45减掉已知的数字，从而找出遗漏的数字。

先做比较简单的数独题，才挑战杀手武士数独。杀手武士数独是数独的进阶版，强烈建议你先试着完成普通数独和武士数独，才挑战这些更复杂的谜题。杀手武士数独非常难，可能要花好几天才能完成。你需要耐心一些。

小提示

先找出比较明显的数字。

购买数独书来练习也不错。 市面上有许多数独谜题书。有些甚至提供逐步说明，让你进步更快。

经常练习就能提高解题速度。

先检查各个九宫格里的数字，然后才逐行、逐列检查。

如果遇到困难，你可以停下来，休息几个小时。小睡一会儿、做些家务、玩游戏等。

反复检查及确认后才填写数字。

和朋友或同事比赛。复印几份数独题，分发给大家，看看谁最快完成。每天或每周做一次，能大幅提升你完成数独的速度。

用记号笔把报章上的数独题复制到更大的格子里。现在，你可以用铅笔清楚地列出所有可能的数字，然后解决谜题。

与其列出所有号码，你可以把每个方格想像成一个小小的九宫格。在左上角画点代表1，右上角画点代表3，中间的点代表5，以此类推。这个方法帮助你节省空间，使空格看起来不那么乱。

警告

尝试从不同角度看谜题。与其每次从上往下解题，你也可以从右到左检查各个数字和方格。记住，两面都要看好，才继续查看下一个九宫格。

只是随便猜测数字的位置是一种欺骗。所有真正的数独题只能用逻辑思考来解决。如果方格可以填入两个可能的数字，而你随便选一个，并抱着侥幸心理妄想它是对的，这是欺骗。

使用解算程序前，先尝试自己解决谜题。

---