Phụ lục 1: Mẫu bìa báo cáo khổ A4 (210x297mm)

3.3. Thuật toán

• 
  Rơi vào tình trạng "thrashing": quá trình tìm kiếm gặp phải bế tắc với cùng một nguyên nhân.
  
• 
  Thực hiện các công việc dư thừa: Mỗi lần chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
  
• 
  Không sớm phát hiện được các khả năng bị bế tắc trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết được nhánh tìm kiếm sẽ đi vào bế tắc.
  

4. CHƯƠNG TRÌNH VÀ KẾT QUẢ

4.1. Tổ chức chương trình

#include
#include #include int c=0;
char N[10] = {'_', '1', '2','3', '4', '5', '6', '7', '8', '9'};
int S[9][9];
void show(int S[][9]);
void gotoxy(int x, int y);
void setcolor(int color);
void tientrinh(int i, int j, int k,int color);
int readFile(FILE *f);
void getData(int S[][9]);
void option1_solve_sudoku(int S[9][9], int x, int y);
void option2_solve_sudoku(int S[9][9], int x, int y);
int check(int S[][9], int x, int y, int k);
void Output(int S[][9]);
void resuilt(int S[][9]);
void main(void){ getData(S); int index; int t=1; show(S); printf("\n\n"); while (t)
{ printf("-------------SUDOKU---------------\n"); printf("1. Xem tien trinh : \n"); printf("2. Xem dap an : \n"); printf("----------------------------------\n");
printf("Nhap lua chon:"); scanf("%d",&index);
switch (index)
{
case 1: option1_solve_sudoku(S,0,0); break; case 2: option2_solve_sudoku(S,0,0); c=0;
break; case 0: t=0; break;
default :
break;
}
}
}
// ham gotoxy
void gotoxy(int x, int y)
{ static HANDLE h = NULL;
if(!h)
h = GetStdHandle(STD_OUTPUT_HANDLE);
COORD c = { x, y };
SetConsoleCursorPosition(h,c);
}
// ham thiet lap mau chu
void setcolor(int color)
{
HANDLE hConsoleColor; hConsoleColor = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hConsoleColor, color);
}
// ham tien trinh
void tientrinh(int i, int j, int k, int color)
{ int size= 4; gotoxy(j*size, i*(size-2));
setcolor(color); printf("%c", N[k]); }
// ham doc file
int readFile(FILE *f){ int n; fscanf(f,"%d", &n); return n;
}
// ham chuyen du lieu file qua mang S
void getData(int S[][9])
{ int A[81]; int count = 0; FILE *f; f = fopen("Input.txt", "r"); while (!feof(f)){ A[count] = readFile(f); count++; } int t = 0; int i, j;
for (i = 0; i < 9; i++)
{ for (j = 0; j < 9; j++) {
S[i][j] = A[t]; t++;
} } fclose(f);
}
// lua chon tien trinh giai sudoku
void option1_solve_sudoku(int S[9][9], int x, int y){ Sleep(400);
if(y == 9){ if(x == 8){
setcolor(12); gotoxy(60, c*20+1); printf("DAP AN %d:\n\n",c+1); resuilt(S); system("pause"); Output(S); c++;
} else { option1_solve_sudoku(S, x+1,0);
}
} else if(S[x][y] == 0){ int k = 0; for (k = 1; k <=9; k++){ if(check(S,x,y,k)){ tientrinh(x, y, k,12);
S[x][y] = k; option1_solve_sudoku(S, x, y+1); tientrinh(x, y, 0, 5); S[x][y] = 0;
Sleep(400);
}
}
} else { option1_solve_sudoku(S,x,y+1);
}
}
// lua chon xuat tat ca dap an ra man hinh
void option2_solve_sudoku(int S[9][9], int x, int y){
if(y == 9){ if(x == 8){ setcolor(12); gotoxy(60, c*20+1); printf("DAP AN %d:\n\n",c+1); resuilt(S);
Output(S); c++;
} else { option2_solve_sudoku(S, x+1,0);
}
} else if(S[x][y] == 0){ int k = 0; for (k = 1; k <=9; k++){ if(check(S,x,y,k)){
S[x][y] = k; option2_solve_sudoku(S, x, y+1);
S[x][y] = 0;
}
}
} else { option2_solve_sudoku(S,x,y+1);
}
}
// ham kiem tra so k co dien duoc vao vi tri x y hay ko
int check(int S[][9], int x, int y, int k){
int i = 0, j = 0; for(i = 0; i <9 ; i++){ if(S[x][i] == k) return 0;
} for(i = 0; i <9 ; i++){ if(S[i][y] == k) return 0;
} int a = x/3, b = y/3; for(i = 3*a; i < 3*a+3; i++){ for(j = 3*b; j < 3*b+3; j++){ if(S[i][j] == k) return 0;
}
} return 1;
} // ham xuat mang
void show(int S[][9]){ setcolor(10);
int i = 0, j = 0; int size= 4; for ( i= 0; i<9 ; i++)
{
for (j= 0; j<9; j++)
{
gotoxy(j*size,i*(size-2)); printf("%c",N[S[i][j]]);
}
}
}
//ham xuat dap an ra man hinh
void resuilt(int S[][9]){ setcolor(3);
int i = 0, j = 0; int size= 4; for ( i= 0; i<9 ; i++)
{
for (j= 0; j<9; j++)
{
gotoxy(j*size+60,i*(size-2)+3+c*20); printf("%c",N[S[i][j]]);
}
}
gotoxy(0, 21); printf("\n");
}
// ham xuat ra file dap an
void Output(int S[][9]){
FILE *p = fopen("Output.TXT", "w+"); int i, j;
for (i = 0; i < 9; i++)
{ for (j = 0; j < 9; j++)
{ int a = S[i][j]; fprintf(p, "%2d", S[i][j]);
} fprintf(p, "\n");
} fclose(p); system("pause");
}

tải về 0.68 Mb.

Chia sẻ với bạn bè của bạn: