我们经常使用的数的进制为“常数进制”,即始终逢p进1。例如,p进制数K可表示为
K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n (其中0 <= ai <= p-1),
它可以表示任何一个自然数。
对于这种常数进制表示法,以及各种进制之间的转换大家应该是很熟悉的了,但大家可能很少听说变进制数。这里我要介绍一种特殊的变进制数,它能够被用来实现全排列的Hash函数,并且该Hash函数能够实现完美的防碰撞和空间利用(不会发生碰撞,且所有空间被完全使用,不多不少)。这种全排列Hash函数也被称为全排列数化技术。下面,我们就来看看这种变进制数。
我们考查这样一种变进制数:第1位逢2进1,第2位逢3进1,……,第n位逢n+1进1。它的表示形式为
K = a1*1! + a2*2! + a3*3! + ... + an*n! (其中0 <= ai <= i),
也可以扩展为如下形式(因为按定义a0始终为0),以与p进制表示相对应:
K = a0*0! + a1*1! + a2*2! + a3*3! + ... + an*n! (其中0 <= ai <= i)。
(后面的变进制数均指这种变进制数,且采用前一种表示法)
先让我们来考查一下该变进制数的进位是否正确。假设变进制数K的第i位ai为i+1,需要进位,而ai*i!=(i+1)*i!=1*(i+1)!,即正确的向高位进1。这说明该变进制数能够正确进位,从而是一种合法的计数方式。
接下来我们考查n位变进制数K的性质:
(1)当所有位ai均为i时,此时K有最大值
MAX[K] = 1*1! + 2*2! + 3*3! + ... + n*n!
= 1! + 1*1! + 2*2! + 3*3! + ... + n*n! - 1
= (1+1)*1! + 2*2! + 3*3! + ... + n*n! - 1
= 2! + 2*2! + 3*3! + ... + n*n! - 1
= ...
= (n+1)!-1
因此,n位K进制数的最大值为(n+1)!-1。
(2)当所有位ai均为0时,此时K有最小值0。
因此,n位变进制数能够表示0到(n+1)!-1的范围内的所有自然数,共(n+1)!个。
在一些状态空间搜索算法中,我们需要快速判断某个状态是否已经出现,此时常常使用Hash函数来实现。其中,有一类特殊的状态空间,它们是由全排列产生的,比如N数码问题。对于n个元素的全排列,共产生n!个不同的排列或状态。下面将讨论如何使用这里的变进制数来实现一个针对全排列的Hash函数。
从数的角度来看,全排列和变进制数都用到了阶乘。如果我们能够用0到n!-1这n!个连续的变进制数来表示n个元素的所有排列,那么就能够把全排列完全地数化,建立起全排列和自然数之间一一对应的关系,也就实现了一个完美的Hash函数。那么,我们的想法能否实现呢?答案是肯定的,下面将进行讨论。
假设我们有b0,b1,b2,b3,...,bn共n+1个不同的元素,并假设各元素之间有一种次序关系 b0<b1<b2<...<bn。对它们进行全排列,共产生(n+1)!种不同的排列。对于产生的任一排列 c0,c1,c2,..,cn,其中第i个元素ci(1 <= i <= n)与它前面的i个元素构成的逆序对的个数为di(0 <= di <= i),那么我们得到一个逆序数序列d1,d2,...,dn(0 <= di <= i)。这不就是前面的n位变进制数的各个位么?于是,我们用n位变进制数M来表示该排列:
M = d1*1! + d2*2! + ... + dn*n!
因此,每个排列都可以按这种方式表示成一个n位变进制数。下面,我们来考查n位变进制数能否与n+1个元素的全排列建立起一一对应的关系。
由于n位变进制数能表示(n+1)!个不同的数,而n+1个元素的全排列刚好有(n+1)!个不同的排列,且每一个排列都已经能表示成一个n位变进制数。如果我们能够证明任意两个不同的排列产生两个不同的变进制数,那么我们就可以得出结论:
★ 定理1 n+1个元素的全排列的每一个排列对应着一个不同的n位变进制数。
对于全排列的任意两个不同的排列p0,p1,p2,...,pn(排列P)和q0,q1,q2,...,qn(排列Q),从后往前查找第一个不相同的元素,分别记为pi和qi(0 < i <= n)。
(1)如果qi > pi,那么,
如果在排列Q中qi之前的元素x与qi构成逆序对,即有x > qi,则在排列P中pi之前也有相同元素x > pi(因为x > qi且qi > pi),即在排列P中pi之前的元素x也与pi构成逆序对,所以pi的逆序数大于等于qi的逆序数。又qi与pi在排列P中构成pi的逆序对,所以pi的逆序数大于qi的逆序数。
(2)同理,如果pi > qi,那么qi的逆序数大于pi的逆序数。
因此,由(1)和(2)知,排列P和排列Q对应的变进制数至少有第i位不相同,即全排列的任意两个不同的排列具有不同的变进制数。至此,定理1得证。
计算n个元素的一个排列的变进制数的算法大致如下(时间复杂度为O(n^2)):
template <typename T>
size_t PermutationToNumber(const T permutation[], int n)
{
// n不能太大,否则会溢出(如果size_t为32位,则n <= 12)
size_t result = 0;
for (int j = 1; j < n; ++j) {
int count = 0;
for (int k = 0; k < j; ++k) {
if (permutation[k] > permutation[j])
++count;
}
// factorials[j]保存着j!
result += count * factorials[j];
}
return result;
}
说明:
(1)由于n!是一个很大的数,因此一般只能用于较小的n。
(2)有了计算排列的变进制数的算法,我们就可以使用一个大小为n!的数组来保存每一个排列的状态,使用排列的变进制数作为数组下标,从而实现状态的快速检索。如果只是标记状态是否出现,则可以用一位来标记状态。
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1775思路:
简单题,可以打表,可以DFS,还可以动规
代码(dfs):
1 /* Note: 10! = 3628800 */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 10
6 int facs[MAX_LEN];
7 int mark, n;
8
9 void
10 init()
11 {
12 int i, f = 1;
13 facs[0] = 1;
14 for(i=1; i<MAX_LEN; i++) {
15 facs[i] = f*i;
16 f = facs[i];
17 }
18 }
19
20 void
21 dfs(int depth, int sum)
22 {
23 if(sum == n) {
24 mark = 1;
25 return;
26 }
27 if(depth>=MAX_LEN || mark)
28 return;
29 dfs(depth+1, sum+facs[depth]);
30 dfs(depth+1, sum);
31 }
32
33 int
34 main(int argc, char **argv)
35 {
36 init();
37 while(scanf("%d", &n)!=EOF && n>=0) {
38 mark = 0;
39 if(n > 0)
40 dfs(0, 0);
41 printf("%s\n", mark?"YES":"NO");
42 }
43 }
代码(table, from
http://blog.chinaunix.net/u3/105033/showart_2199237.html):
1 #include<iostream>
2 using namespace std;
3 bool b[1000001];
4 int sum=0;
5 int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
6 void calculate(int n)
7 {
8 if(n>=10)
9 return ;
10 sum+=a[n];
11 b[sum]=true;
12 calculate(n+1);
13 sum-=a[n];
14 calculate(n+1);
15 }
16 int main()
17 {
18 memset(b,0,sizeof(b[0]));
19 calculate(0);
20 b[0]=false;
21 int n;
22 cin>>n;
23 while( n>=0)
24 {
25 if(b[n])
26 cout<<"YES"<<endl;
27 else
28 cout<<"NO"<<endl;
29 cin>>n;
30 }
31 return 0;
32 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2248思路:
第一个想法是BFS,不过习惯性地看discuss,发现大家用的都是DFS,于是还是用DFS+减枝
这道题目的关键减枝是: num[depth+1] = num[depth]+num[i], 0<=i<=depth,另外就是从大到小的搜索顺序
另一种解法是迭代加深搜索,第一次使用,貌似就是用DFS实现BFS,不过空间需求与时间需求是两者的折衷,其模板类似于:
1 for(deep=1; 1; deep++)
2
3 {
4
5 dfs(0);
6
7 If(find = true)
8
9 break;
10
11 }
代码1:
1 #define MAX_LEN 101
2 #define INF 0x7FFFFFFF
3 int num[MAX_LEN];
4 int ans[MAX_LEN];
5 int n, min;
6
7 int
8 dfs(int depth)
9 {
10 int i, j;
11 if(depth+1 >= min)
12 return;
13 if(num[depth] == n) {
14 min = depth+1;
15 memcpy(ans, num, min*sizeof(int));
16 return;
17 }
18 for(i=depth; i>=0; i--)
19 if(num[i]+num[depth]<=n) {
20 num[depth+1] = num[i] + num[depth];
21 dfs(depth+1);
22 }
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 int i;
29 while(scanf("%d", &n)!=EOF && n!=0) {
30 min = INF;
31 num[0] = 1;
32 dfs(0);
33 for(i=0; i<min; i++)
34 printf("%d ", ans[i]);
35 printf("\n");
36 }
37 return 0;
38 }
代码2:
1 #define MAX_LEN 101
2 int num[MAX_LEN];
3 int n, find, dplimit;
4
5 void
6 dfs(int depth)
7 {
8 int i, j;
9 if(depth >= dplimit)
10 return;
11 if(num[depth] == n) {
12 if(!find) {
13 for(j=0; j<=depth; j++)
14 printf("%d ", num[j]);
15 printf("\n");
16 find = 1;
17 }
18 return;
19 }
20 for(i=depth; i>=0; i--)
21 if(num[i]+num[depth]<=n) {
22 num[depth+1] = num[i] + num[depth];
23 dfs(depth+1);
24 }
25 }
26
27 int
28 main(int argc, char **argv)
29 {
30 while(scanf("%d", &n)!=EOF && n!=0) {
31 find = 0;
32 num[0] = 1;
33 for(dplimit=1; 1; dplimit++) {
34 dfs(0);
35 if(find)
36 break;
37 }
38 }
39 }
摘要: 问题:http://acm.pku.edu.cn/JudgeOnline/problem?id=1475思路:很复杂的一题,从discuss知道可以采用嵌套的BFS来做,不过始终不知道如何下手通过这题,发现自己对于复杂问题的coding能力比较弱,不能很好的理清其中的逻辑关系,需要多多锻炼这题的关键是抓住box的每一次扩展,都对应地存在一个person的起始位置,两者需要同时记录参考:http:/...
阅读全文
才储©分析:您的性格类型倾向是“ ISFJ ”(内向 实感 情感 判断)
沉静,友善,有责任感和谨慎。能坚定不移地承担责任。做事贯彻始终、不辞劳苦和准确无误。忠诚,替人着想,细心;往往记着他所重视的人的种种微小事情,关心别人的感受。努力创造一个有秩序、和谐的工作和家居 环境。 ISFJ型的人忠诚、有奉献精神和同情心,理解别人的感受。他们意志清醒而有责任心,乐于为人所需。 ISFJ型的人十分务实,他们喜欢平和谦逊的人。他们喜欢利用大量的事实情况,对于细节则有很强的记力。他们耐心地 对待任务的整个阶段,喜欢事情能够清晰明确。 ISFJ型的人具有强烈的职业道德,所以他们如果知道自己的行为真正有用时,会对需要完成之事承担责任。他们准确系统地完成任务。他们具有传统的价值观,十分保守。他 们利用符合实际的判断标准做决定,通过出色的注重实际的态度增加了稳定性。 ISFJ型的人平和谦虚、勤奋严肃。他们温和、圆通,支持朋友和同伴。他们乐于协助别人,喜欢实际可行地帮助他人。他们利用个人热情与人 交往,在困难中与他人和睦相处。ISFJ型的人不喜欢表达个人情感,但实际上对于大多数的情况和事件都具有强烈的个人反应。他们关心、保护朋友,愿意为朋友献身,他们有为他人服务的意识,愿意完成他们的责任和义务。 您适合的领域有:领域特征不明显,较相关的如:医护领域、消费类商业、服务业领域 您适合的职业有:(该类型可能存在的盲点见完整分析报告) · 内科医生 · 营养师 · 图书/档案管理员 · 室内装潢设计师 · 顾客服务代表 · 记账员 · 特殊教育教师 · 酒店管理 · 人事管理人员 · 电脑操作员 · 信贷顾问 · 零售业主 · 房地产代理或经纪人 · 艺术人员 · 商品规划师 · 语言病理学者 · 审计师 · 会计 · 财务经理 · 办公室行政管理 · 后勤和供应管理 · 中层经理 · 公务(法律、税务)执行人员 · 银行信贷员 · 成本估价师 · 保险精算师 · 税务经纪人 · 税务检查员 · 机械、电气工程师 · 计算机程序员 · 数据库管理员 · 地质 · 气象学家 · 法律研究者 · 律师 · 外科医生 · 药剂师 · 实验室技术人员 · 牙科医生 · 医学研究员
from: http://www.apesk.com/mbti/dati.asp |
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3411思路:
做过几道类似的题,DFS
不过,这一道有点特殊,每条边以及每个点的访问次数并非只有一次,为了能够预付款,需要重复访问某个点或者边
这样出现的一个问题就是搜索何时结束?这里参考了网上的代码: 重复访问的原因是为了能够预先到达某个城市,而城市的总个数为N,也就是说,每个点的重复访问次数不需要超过N
另外,由于每两个点之间可能存在多条路径,因此不能使用邻接矩阵,而需要邻接表
代码
1 int N, m;
2 int min;
3 int mark[MAX_LEN];
4 struct Node {
5 int dest;
6 int adv;
7 int p, r;
8 struct Node *next;
9 };
10 struct Node *roads[MAX_LEN];
11 struct Node save[MAX_LEN];
12
13 void
14 init()
15 {
16 int i, a, b, c, p, r, cnt = 0;
17 min = INF;
18 memset(mark, 0, sizeof(mark));
19 memset(roads, 0, sizeof(roads));
20 for(i=0; i<m; i++) {
21 scanf("%d %d %d %d %d", &a, &b, &c, &p, &r);
22 save[cnt].dest = b;
23 save[cnt].adv = c;
24 save[cnt].p = p;
25 save[cnt].r = r;
26 save[cnt].next = roads[a];
27 roads[a] = save+cnt;
28 ++cnt;
29 }
30 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190思路:
DFS+减枝,好题
代码:
1 /*
2 * N = R[1]^2*H[1] + R[2]^2*H[2] +
+ R[M]^2*H[M]
3 * S = R[1]^2 + 2R[1]*H[1] + 2R[2]*H[2] +
+ 2R[M]H[M]
4 */
5 #include<stdio.h>
6 #include<stdlib.h>
7 #include<string.h>
8 #include<math.h>
9 #define MAX_LEVEL 21
10 #define INF 0x7FFFFFFF
11 /* from top level to the i[th] level, the minimum total volumn and area */
12 int min_volumn[MAX_LEVEL], min_area[MAX_LEVEL];
13 int n, m;
14 int rt;
15
16 void
17 init()
18 {
19 int i;
20 rt = INF;
21 min_volumn[0] = min_area[0] = 0;
22 for(i=1; i<MAX_LEVEL; i++) {
23 min_volumn[i] = min_volumn[i-1] + i*i*i;
24 min_area[i] = min_area[i-1] + 2*i*i;
25 }
26 }
27
28 /* from bottom(m[th] level) to the top */
29 void
30 dfs(int level, int last_r, int last_h, int cur_volumn, int cur_area)
31 {
32 int r, h, tmp, v, a;
33 if(cur_volumn+min_volumn[level]>n || cur_area+min_area[level]>=rt)
34 return;
35 /* ADD this pruning according the volumn&area formula */
36 if(2*(n-cur_volumn)/last_r+cur_area >= rt)
37 return;
38 if(level==0) {
39 if(cur_volumn == n)
40 rt = cur_area<rt ? cur_area : rt;
41 return;
42 }
43 /* the minimal r in [level] would be level */
44 for(r=last_r-1; r>=level; r--) {
45 tmp = (int)((n-cur_volumn-min_volumn[level-1])/(double)(r*r));
46 tmp = tmp>(last_h-1) ? (last_h-1) : tmp;
47 for(h=tmp; h>=level; h--) {
48 v = r*r*h;
49 a = 2*r*h;
50 if(level == m)
51 a += (r*r);
52 dfs(level-1, r, h, cur_volumn+v, cur_area+a);
53 }
54 }
55 }
56
57 int
58 main(int argc, char **argv)
59 {
60 int max_m_r, max_m_h;
61 while(scanf("%d %d", &n, &m) != EOF) {
62 init();
63 max_m_r = (int)(sqrt((n-min_volumn[m-1])/(double)m)) + 1;
64 max_m_h = (int)((n-min_volumn[m-1])/(double)(m*m)) + 1;
65 dfs(m, max_m_r, max_m_h, 0, 0);
66 if(rt == INF)
67 printf("0\n");
68 else
69 printf("%d\n", rt);
70 }
71 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1724思路:
有点与PKU 3256类似的题
第一个想法就是深搜
第一遍代码(WA):
对于discuss里的测试数据该代码是没有问题的,可结果还是WA...
1 #define MAX_CITIES 101
2 #define INF 100000
3 int road[MAX_CITIES][MAX_CITIES];
4 int length[MAX_CITIES][MAX_CITIES];
5 int toll[MAX_CITIES][MAX_CITIES];
6 int visited[MAX_CITIES];
7 int k, n, r;
8 int min_len;
9
10 void
11 dfs(int city, int cur_len, int cur_toll)
12 {
14 int i;
15 visited[city] = 1;
16 if(cur_len>=min_len || cur_toll>k) {
17 visited[city] = 0;
18 return;
19 }
20 if(city == n) {
21 min_len = cur_len;
22 visited[city] = 0;
23 return;
24 }
25 for(i=1; i<=n; i++) {
26 if(road[city][i] && !visited[i])
27 dfs(i, cur_len+length[city][i], cur_toll+toll[city][i]);
28 }
29 visited[city] = 0;
30 }
继续翻查discuss里,发现有人说两点之间可能有多条路径...
然后看到其他人代码是使用链表来保存所有的路径,所以修改后的AC代码如下:
1 #define MAX_CITIES 101
2 #define INF 100000
3 struct Node {
4 int dest;
5 int len;
6 int toll;
7 struct Node *next;
8 };
9 struct Node roads[MAX_CITIES];
10 struct Node backup[MAX_CITIES*MAX_CITIES];
11 int visited[MAX_CITIES];
12 int k, n, r;
13 int min_len;
14
15 void
16 dfs(int c, int cur_len, int cur_toll)
17 {
18 int i;
19 struct Node *node;
20 if(cur_len>=min_len || cur_toll>k)
21 return;
22 if(c == n) {
23 min_len = cur_len;
24 return;
25 }
26 for(node=roads[c].next; node!=NULL; node=node->next) {
27 if(!visited[node->dest]) {
28 visited[node->dest] = 1;
29 dfs(node->dest, cur_len+node->len, cur_toll+node->toll);
30 visited[node->dest] = 0;
31 }
32 }
33 }
34
35 int
36 main(int argc, char **argv)
37 {
38 int i, s, d, l, t, cnt=0;
39 memset(visited, 0, sizeof(visited));
40 scanf("%d", &k);
41 scanf("%d", &n);
42 scanf("%d", &r);
43 for(i=1; i<=n; i++)
44 roads[i].next = NULL;
45 for(i=0; i<r; i++) {
46 scanf("%d %d %d %d", &s, &d, &l, &t);
47 backup[cnt].dest = d;
48 backup[cnt].len = l;
49 backup[cnt].toll = t;
50 backup[cnt].next = roads[s].next;
51 roads[s].next = backup+cnt;
52 ++cnt;
53 }
54 min_len = INF;
55 visited[1] = 1;
56 dfs(1, 0, 0);
57 if(min_len == INF)
58 printf("-1\n");
59 else
60 printf("%d\n", min_len);
61 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3373参考:
http://blog.csdn.net/logic_nut/archive/2009/10/29/4740951.aspxhttp://iaml.is-programmer.com/posts/8249.html (这个应该是SYSU的哈哈,里面有西西里)
思路:
这个题是真不会做,即使是看别人代码都看了快两天,艾...
首先要解决的问题是如何求大数的模(这里大数用字符串表示)?
我们知道对于取模运算有: (a+b)%k = ((a%k)+(b%k))%k
(ab)%k = ((a%k)(b%k))%k
对于0-9的每个数,可以将其在个、十、百、千...位时模k的结果保存到一张表中: mod_arr
这样,修改这个大数的任何一位而模k的新结果可以在O(1)时间内取得
1 char num[MAX_LEN];
2 int hash[MAX_MOD];
3 int mod_arr[MAX_LEN][10];
4 int k, len, tmp[MAX_LEN], tmp2[MAX_LEN], start_mod;
5 int head, tail;
6 struct EACH {
7 int digits[MAX_LEN];
8 int remainder;
9 int index;
10 } queue[MAX_MOD];
11
12 void
13 init()
14 {
15 int i, j;
16 len = strlen(num);
17 for(j=0; j<10; j++)
18 mod_arr[0][j] = j%k;
19 for(i=1; i<len; i++)
20 for(j=0; j<10; j++)
21 mod_arr[i][j] = (mod_arr[i-1][j]*10)%k;
22 start_mod = 0;
23 for(i=0; i<len; i++) {
24 tmp[i] = tmp2[i] = num[len-i-1]-'0';
25 start_mod += (mod_arr[i][num[len-i-1]-'0']);
26 }
27 start_mod %= k;
28 head = -1;
29 tail = 0;
30 memset(hash, 0, sizeof(hash));
31 memset(queue, 0, sizeof(queue));
32 }
第一篇参考链接里是用DFS来做的,可惜我对于其中用于记忆化搜索的remember数组始终不理解,结果TLE
更加容易理解的方案是BFS,每次扩展改变一位数字
使用BFS的问题是如何判重?参考第二篇文章(繁琐的C++语法,没认真看呵呵),使用余数判重,其实还不是太理解
代码:
1 void
2 bfs()
3 {
4 int i, j, t, cur_rem, cur_index;
5 queue[tail].remainder = start_mod;
6 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
7 queue[tail].index = len-1;
8 hash[start_mod] = 1;
9 while(head < tail) {
10 ++head;
11 cur_rem = queue[head].remainder;
12 cur_index = queue[head].index;
13 memcpy(tmp, queue[head].digits, sizeof(int)*len);
14 if(cur_rem == 0) {
15 for(i=len-1; i>=0; i--)
16 printf("%d", tmp[i]);
17 printf("\n");
18 return;
19 }
20 /* changing digits: from least (smaller than itself) */
21 for(i=cur_index; i>=0; i--) {
22 for(j=0; j<tmp2[i]; j++) {
23 if(i==len-1 && j==0)
24 continue;
25 t = cur_rem + mod_arr[i][j] - mod_arr[i][tmp2[i]] + k; /* O(1) to find the new remainder */
26 t = t % k;
27 tmp[i] = j;
28 if(!hash[t]) {
29 ++tail;
30 queue[tail].remainder = t;
31 queue[tail].index = i-1;
32 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
33 hash[t] = 1;
34 }
35 }
36 tmp[i] = tmp2[i];
37 }
38 /* changing digits: to max (greater than itself) */
39 for(i=0; i<=cur_index; i++) {
40 for(j=tmp2[i]+1; j<10; j++) {
41 t = cur_rem + mod_arr[i][j] - mod_arr[i][tmp2[i]] + k;
42 t = t % k;
43 tmp[i] = j;
44 if(!hash[t]) {
45 ++tail;
46 queue[tail].remainder = t;
47 queue[tail].index = i-1;
48 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
49 hash[t] = 1;
50 }
51 tmp[i] = tmp2[i];
52 }
53 }
54 }
55 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2676思路:
深度搜索
纯粹按照题意进行搜索,1532MS...额...就快TLE了呵呵
据discussion说,倒过来搜索时间会相当快
代码:
1 #define MAX_LEN 10
2 char table[MAX_LEN][MAX_LEN];
3 int flag;
4
5 int
6 is_available(int x, int y, char ch)
7 {
8 int j, k, small_x, small_y;
9 for(j=0; j<9; j++) /* row */
10 if(table[x][j]==ch)
11 return 0;
12 for(k=0; k<9; k++) /* column */
13 if(table[k][y]==ch)
14 return 0;
15 small_x = x/3;
16 small_y = y/3;
17 for(j=small_x*3; j<(small_x+1)*3; j++)
18 for(k=small_y*3; k<(small_y+1)*3; k++)
19 if(table[j][k]==ch)
20 return 0;
21 return 1;
22 }
23
24 void
25 dfs(int x, int y)
26 {
27 int i, j, nx, ny;
28 if(flag)
29 return;
30 if(x==9){
31 if(!flag) {
32 for(j=0; j<9; j++)
33 printf("%s\n", table[j]);
34 flag = 1;
35 }
36 return;
37 }
38 if(y==8) {
39 nx = x+1;
40 ny = 0;
41 } else {
42 nx = x;
43 ny = y+1;
44 }
45 if(table[x][y] == '0') {
46 for(i=1; i<=9; i++) {
47 if(is_available(x, y, i+'0')) {
48 table[x][y] = i+'0';
49 dfs(nx, ny);
50 table[x][y] = '0';
51 }
52 }
53 } else
54 dfs(nx, ny);
55 }
更好的解题代码见:
http://blog.csdn.net/logic_nut/archive/2009/08/09/4428996.aspx