GREEDY – Scroll horse chess board example
Greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time. /*a horse through the whole chessboard passing once through each box*/ #define _CRT_SECURE_NO_DEPRECATE #include <stdio.h> #include <conio.h> #include <iostream> #include <windows.h> #include <process.h> using namespace std; void gotoxy(int, int); // prototype void clrscr(); // prototype #define N 8 #define NDIR 8 int plusx[]={0,-2,-2,-1,1,2,2,1,-1}; int plusy[]={0,-1,1,2,2,1,-1,-2,-2}; int a[N+1][N+1]; // function definition -- requires windows.h void gotoxy(int x, int y) { HANDLE hConsoleOutput; COORD dwCursorPosition; cout.flush(); dwCursorPosition.X = x; dwCursorPosition.Y = y; hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleCursorPosition(hConsoleOutput,dwCursorPosition); } // function definition -- requires process.h void clrscr() { system("cls"); } /*se verifica daca coordonatele sunt in interiorul tablei si daca casuta respectiva este libera(nu s-a mai trecut prin ea).Intoarce 1 daca se verifica conditia anterioara si 0 in caz contrar*/ int conditie(int lin,int col) { return ((lin > 0) && (lin <=N) && (col > 0) && (col <=N) && (a[lin] == 0)); } /*numara posibilitatea de continuare din pozitia(lin,col):daca numarul de casute neocupate in care s-ar putea deplasa calul*/ int posib_continuare(int lin,int col) { int dir,sum,_lin,_col; for(dir = 1,sum = 0;dir<=NDIR;dir++) { _col = col + plusx[dir]; _lin = lin + plusy[dir]; if(conditie(_lin,_col)) sum++; } return sum; } /*initializeaza tabla de sah cu 0.Deoarece variabila tablou a este globala ea este initializata implicit cu 0,insa este mai bine ca un programator sa se obisnuiasca sa nu lase variabile neinitializate*/ void init_tabla() { int lin,col; for(lin = 1;lin <= N;lin++) for(col = 1;col <= N;col++) a[lin] = 0; } /*citeste linia si coloana unde va fi plasat calul la initializare*/ void cit_date(int *lin,int *col) { clrscr(); printf("Introduceti pozitia initiala: \n"); printf("Linia: "); scanf("%d",lin); printf("Coloana: "); scanf("%d",col); } /*functia principala*/ void run(int lin,int col) { int new_lin,new_col,i0,j0,k; int min,dir; clrscr(); a[lin] = 1; gotoxy(col * 3,lin); printf("1"); for(k=1;k<N*N;k++) { i0 = 0; min = 8; for(dir =1;dir<=NDIR;dir++) { new_lin = lin + plusy[dir]; new_col = col + plusx[dir]; if(conditie(new_lin,new_col)) if(k == N*N-1) { i0 = new_lin; j0 = new_col; } else if((posib_continuare(new_lin,new_col) != 0) && (posib_continuare(new_lin,new_col) < min)) { min = posib_continuare(new_lin,new_col); i0 = new_lin; j0 = new_col; } } if(i0 == 0) { printf("Nu avem solutie!"); return; } lin = i0; col = j0; a[lin] = k + 1; gotoxy(col * 3,lin); printf("%d\n",a[lin]); } } void main() { int l,c; init_tabla(); cit_date(&l,&c); run(l,c); }
36,752 total views, 1 views today