就是呢 王凡班的project不是要用redlib来写吗 然後它的用法还真的是颇有趣... 我个人看了满久之後 大概理解出个大概了 底下这个是教授给我们的资料中 解一个9x9的数独的code 我加了一些可有可无的注解 如果有兴趣又不嫌我嘴炮的 就看看呗~ sudoku.c ---------------------------------------- /* 这个是为了让这个程式比较好懂，所做的一些注解。当然，我的希望只是让 它比较好懂，所以如果我表达能力不佳或者其它因素，让你觉得不是很有帮 助的话，就不要看吧，毕竟我也只是推想出它可能的意思而已。也因为这个 原因，里面很多地方可能都有错，所以请各位选择性的采信呗:) 另外一个想说的是，这是用C写出来的，所以有很多跟C++很像的地方，可是 有些地方又会有很大差别，所以自行小心呗~~不过除了印东西的时候，不用 cout而用fprintf(输出的地方, "要印的字串",变数)外，基本上其它不会太 麻烦(吧)。有关语法的可以去GOOGLE找，找printf这个函数来看应该会有帮 助。 另外，里面很多地方是有关图论的部份，至於图的性质也不是很容易说的 (因为要画图才能解释)，所以如果觉得不太好懂的话，那就多讨论吧~~ 最後我个人建议大家，不要用Dev-Cpp 来写程式。既然最後是要在linux上 compile的，那麽用 Dev-Cpp写也不会比用记事本好... 私心推荐Notepad++ 好用~真的~ 2010/05/02,by Helicoid */ //这两行是写C的时候很重要的 //就当作习惯的直接加上去呗 #include <stdio.h> #include <stdlib.h> //下两行顺序不能对调，不然会有满满的错误 #include "redlib.h" #include "redlib.e" char *s[9][9]; int count_print = 0; //redgram是一个资料型别，而这三行的意思等於是 //redgram slot_constraint(redgram d, int i, int j) 其实只是个函数 redgram slot_constraint(d, i, j) redgram d; int i, j; { // 宣告有的没的 int value, h, k, nc, ac, gs; redgram conj; //value从1到9，h从0到8，来看它要做什麽 for(value =1; value <= 9; value++) { for (h = 0; h < 9; h++){ if (h != i) { //底下这个式子是因为，在9x9的数独里，同一行当然不能同时是某个数字啦~ //例如说，当value=3时，第i列j行和 第h列j行是不能同时等於3的 //所以画一个图表示要避开这种事 conj = red_diagram("~(%s==%d && %s==%d)", s[i][j], value, s[h][j], value ); //底下可以暂时不看，反正就是跟输出有关的东西 //倒是有一点值得注意，RED_OUT这个东西似乎跟输出有关 //它的意义大家想想吧(我不知道XD) if ((++count_print) < 100 &&(gs=red_diagram_size(d, &nc, &ac))<30){ fprintf(RED_OUT, "\nMutual exclusion to value:%1d at %s and %s:\nconstraint:\n", value, s[i][j], s[h][j] ); red_print_line(conj); fprintf(RED_OUT, "\n"); red_print_diagram(conj); fprintf(RED_OUT, "input diagram:\n"); red_print_line(d); fprintf(RED_OUT, "\n"); red_print_diagram(d); } //下面这行是重点!!表示把刚刚的"同一行不能同时是某个数字" //这点加到原本的redgram中，而且是AND //(因为正确的图形要同时满足所有的限制!) d = red_and(d, conj); //再来也可以暂时不要看 if (count_print < 100 && gs < 30) { fprintf(RED_OUT, "result diagram:\n"); red_print_line(d); fprintf(RED_OUT, "\n"); red_print_diagram(d); } /* fprintf(RED_OUT,"%s && %s, after one conjunction.\n",s[i][j],s[h][j]); red_print_graph(d); fprintf(RED_OUT, "\n"); fflush(RED_OUT); */ //接下来的概念完全一样，就是说如果同在一个3x3的小正方形内 //那麽数字不能同时等於某个value //稍微看一下，画出一个数独的形状再比一比，应该比较好理解 if ((h/3) == (i/3)) { for (k = 0; k < 9; k++) { if ((k/3)==(j/3) && (k!=j)) { d = red_and(d, red_diagram("~(%s==%d && %s==%d)", s[i][j], value, s[h][k], value ) ); /* fprintf(RED_OUT,"%s && %s, after one conjunction.\n",s[i][j],s[h][k]); red_print_graph(d); fprintf(RED_OUT, "\n"); fflush(RED_OUT); */ } } } } //一样的概念第三次出现(也是最後一次了) //同样的一列里面，任两格是不能同时为相同的数字的~ if (h != j) { d = red_and(d, red_diagram("~(%s==%d && %s==%d)", s[i][j], value, s[i][h], value ) ); /* fprintf(RED_OUT, "%s && %s, after one conjunction.\n", s[i][j], s[i][h]); red_print_graph(d); fprintf(RED_OUT, "\n"); fflush(RED_OUT); */ } } } //复习一下刚刚做了什麽事 //就是，一个正常的数独的限制条件 //1.一行里面有1~9<=>任何两格数字不同 //2.一列里面有1~9<=>任何两格数字不同 //3.一个3x3小方格里面有1~9<=>任何两格数字不同 //重点是都用到了red_and这个函数，他是这个程式的主角 //接下来的我是用猜的啦...不太确定 //把d在堆叠的号码找出来，然後标记一下不要被清掉 h = red_push(d); //清掉用过的垃圾图表(狡兔死走狗烹的道理吧...) red_garbage_collect(RED_GARBAGE_SILENT); //把d给挤出来(?) red_pop(h); //传回加了料之後的图表d return(d); } /* slot_constraint() */ //以上slot_constraint函数告一段落 //这两行只是定义了东西而已 #define FLAG_MULTIPLE 1 #define FLAG_SINGLE 0 //以下为main函数 main(argc, argv) int argc; char **argv; { //宣告有的没的 char a, *start, *condition, *p; redgram sol, cube; int i, j, k, u, v, h, m, c[9][9], lb[9][9], ub[9][9], flag; char stop[30]; FILE *datafile; //argc是用终端机(类似cmd)的时候，输入的变数数目 //例如说，当我们打"程式名 输入档名"时，argc就会是2 //然後argv[0]="程式名" argv[1]="输入档名" //所以... 就会有底下的两个if if (argc < 2) { printf("Input file for sudoko not specified!\n"); exit(0); } datafile = fopen(argv[1], "r"); if (datafile == NULL) { printf("Can't open the data file of sudoko!! \n"); exit(0); } //一些REDLIB所需的架构 //RED_input_file("sample.d"); red_begin_session(RED_SYSTEM_UNTIMED, "sudoku", 2); red_begin_declaration(); /* each process for a row on the board. */ //REDLIB所用的变数要有个名子，所以就跑个for跑出一大堆名子 //(因为REDLIB跟C的变数是不一样的，所以光是给名子就有点麻烦) //後面的 red_declare_variable， //(我觉得)是宣告d00,d01,d02,...,d87,d88都是1到9的离散变数 //(因为数独上面不会有7.4或者 2π之类的东东吧) for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { s[i][j] = malloc(4); sprintf(s[i][j], "d%1d%1d", i, j); red_declare_variable(RED_TYPE_DISCRETE, 1, 9, "%s", s[i][j]); } } //REDLIB所需的架构 red_end_declaration(RED_NO_REFINED_GLOBAL_INVARIANCE); /* How to access a variable ? */ //RED_print_variables(); //RED_print_xtions(); //RED_verify(); /* Declaration of the 81 slot variable indices as a 9X9 arrays. * Note this is not for the array of slot variable values. * This is only for the slot variable indices. */ do { /* After the completion of the loop, sol should be the MBDD+CRD * that records the solutions to your input board specification. * Initially, we set sol to TRUE. */ //sol是整个程式的主要图表，一开始我们让它恒真(总不能一开始就错了吧...) sol = red_true(); /* Please fill in the code here to calculate the solution for * the given sudoko puzzle. * The details of the main processing body, that you should fill in, include: 1. Read in the values of those given slots on the board and construct the logic formula with the REDLIB procedures. 2. Iteratively restrict the formula you got in step 1 with all the sudoko rules. Now start filling in the main processing body in the following. |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV */ for (i = 0; i < 9; i++){ for (j = 0; j < 9; j++){ //读取数字(不过用char的方式存 ) //读到换行就丢了再读 a = getc(datafile); if (a == '\n') a = getc(datafile); //把读到的字元换成字串 sprintf(stop, "%c\0", a); //把字串换成数字，用atoi这个有趣函数 c[i][j] = atoi(stop); if (c[i][j] != 0) { //如果读到非零值，就要加上"某位置=读到的某数"这个限制条件 //一样，用到的是red_and sol = red_and(sol, red_diagram("%s==%d", s[i][j], c[i][j])); //把这个东西拿去做前面的函数 sol = slot_constraint(sol, i, j); } } } //因为我们可以发现，不管那格的数字是不是被决定了 //它都应该要拿去做slot_constraint //所以我们对漏网之鱼拿去做 slot_constraint //(个人认为(纯猜测)如此安排是效率因素) for(i = 0; i < 9; i++) { for(j = 0; j < 9; j++) { if (c[i][j] == 0) sol = slot_constraint(sol, i, j); } } /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| After the main processing body of the loop, * we are now ready to print out the solution board specification. * We do this in two ways. * In the first way, we print the board as a 9X9 char array. * We do this by first invoking the depth-first traversing procedure * red_process_DFS() for MBDD+CRD. * For each node in the MBDD+CRD, red_process_DFS() process the * node with procedure max_rec() and each arc of the node with * procedure arc_noop(). * * In the second way, we print the MBDD+CRD of sol as a single-line * Boolean formula. */ /* red_print_diagram(sol); */ //似乎是要算总解数的样子 //(小声说)但是这个算到的数字跟印出来的都不一样...这条函数似乎... i = red_diagram_discrete_model_count(sol); //印出来呗 switch (i) { case 0: fprintf(RED_OUT, "\nNo solutions!\n"); break; case 1: fprintf(RED_OUT, "\nOnly 1 solution\n"); break; default: fprintf(RED_OUT, "\nTotal %1d solutions!\n", i); break; } //接下来的我不太懂... //不过，可以理解为就是纯粹的印出吧 //既然是印出，参数改一改要印出别的东西应该也是可行的 cube = red_first_cube(sol); for (; cube != red_false(); cube = red_next_cube(sol)) { fprintf(RED_OUT, "\n\nOne solution:\n"); flag = FLAG_SINGLE; for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { red_get_cube_discrete_value( cube, s[i][j], &(lb[i][j]), &(ub[i][j]) ); if (lb[i][j] < ub[i][j]) flag = FLAG_MULTIPLE; fprintf(RED_OUT, "%1d", lb[i][j]); } fprintf(RED_OUT, "\n"); } if (flag != FLAG_MULTIPLE) continue; fprintf(RED_OUT, "\n\nOne more solution:\n"); for (i = 0; i < 9; i++) { for (j = 0; j < 9; j++) { fprintf(RED_OUT, "%1d", ub[i][j]); } fprintf(RED_OUT, "\n"); } fprintf(RED_OUT, "\n"); } fprintf(RED_OUT, "\n-----------------------------------------------\n"); // red_print_line(sol); // fprintf(RED_OUT, "\nsolution diagram:\n"); // red_print_diagram(sol); break; } //如果先前抓到档案结束之类的，会跳出吧 //不过说实在的我不清楚这整个do while的运作方式 while( strcmp(fgets(stop, 30, datafile), "end") != 0 && strcmp(fgets(stop, 30, datafile), "END") != 0 ); //结束了~收个尾，记得关档 red_end_session(); fclose(datafile); } /* main() */ //一个满奇怪的地方是，记得最最後面留一行空行 //不然用linux来compile的时候会有意见(不要问我为什麽) --------------------------------------------- 大概是这样吧 我把它修剪成刚好贴在一般看B的宽度了 觉得在这边看不清楚的人(应该是每个人吧= =) 把它复制到文字编辑器里 不然就... http://www.badongo.com/file/22378576 里面有.c档~ 嗯嗯 後来我(以为)有写出教授要的code啦 放了几个输入档还没有错(只是跑很慢,慢到差点以为系计中电脑当了) 那就祝王凡班的各位都写出来呗~ 我该回去写普物报告了@@ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.241.41