[計概] 王凡班的project 有一點點想法
就是呢 王凡班的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
→
05/02 17:05, , 1F
05/02 17:05, 1F
→
05/02 17:07, , 2F
05/02 17:07, 2F
→
05/02 17:20, , 3F
05/02 17:20, 3F
推
05/02 18:29, , 4F
05/02 18:29, 4F
推
05/02 19:07, , 5F
05/02 19:07, 5F
推
05/02 21:27, , 6F
05/02 21:27, 6F
推
05/03 11:50, , 7F
05/03 11:50, 7F
推
05/04 17:07, , 8F
05/04 17:07, 8F
→
05/05 06:25, , 9F
05/05 06:25, 9F
推
05/05 22:14, , 10F
05/05 22:14, 10F