就是呢 王凡班的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