# include <iostream>
# include <cstring>
using namespace std;
const int MAX_N = 10 ;
int n, x_start, y_start;
int sol[MAX_N][MAX_N]; // matricea solutie
int moves[ 8 ][ 2 ] = {{ -2 , -1 }, { -2 , 1 }, { -1 , -2 }, { -1 , 2 }, { 1 , -2 }, { 1 , 2 }, { 2 , -1 }, { 2 , 1 }}; // vectorii deplasarii calului
// functie care verifica daca pozitia (x,y) este valida pe tabla de sah
bool isValid ( int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= n && sol[x][y] == 0 ;
}
// functie recursiva care gaseste o solutie
bool solve ( int x, int y, int step) {
if (step == n * n) {
return true ; // s-a gasit o solutie
}
for ( int i = 0 ; i < 8 ; i++) {
int new_x = x + moves[i][ 0 ];
int new_y = y + moves[i][ 1 ];
if ( isValid (new_x, new_y)) {
sol[new_x][new_y] = step + 1 ; // marcheaza pozitia ca fiind ocupata
if ( solve (new_x, new_y, step + 1 )) {
return true ;
}
sol[new_x][new_y] = 0 ; // marcheaza pozitia ca fiind libera
}
}
return false ; // nu s-a gasit o solutie
}
int main () {
cout << "Introduceti dimensiunea tablei de sah: " ;
cin >> n;
cout << "Introduceti coordonatele de start (x,y): " ;
cin >> x_start >> y_start;
memset (sol, 0 , sizeof (sol)); // initializam matricea solutie cu 0
sol[x_start][y_start] = 1 ; // marcam pozitia initiala ca fiind ocupata
if ( solve (x_start, y_start, 1 )) { // cautam o solutie
cout << "Solutia este:\n" ;
for ( int i = 1 ; i <= n; i++) {
for ( int j = 1 ; j <= n; j++) {
cout << sol[i][j] << " " ;
}
cout << endl;
}
} else {
cout << "Nu exista solutie!\n" ;
}
return 0 ;
}
Pentru această situație, datele de intrare ar fi:
Aceste date pot fi introduse în program pentru a rula algoritmul de backtracking care să găsească o soluție pentru problema acoperirii tablei de șah cu un cal.
Algoritmul de backtracking pentru problema acoperirii tablei de șah cu un cal constă în parcurgerea recursivă a tuturor pozițiilor posibile pe care calul le poate lua pe tablă și verificarea dacă acea poziție poate fi o soluție viabilă pentru a acoperi întreaga tablă.
Pentru a implementa acest algoritm, putem urma următorii pași:
Algoritmul se oprește atunci când toate pozițiile de pe tabla de șah au fost vizitate sau când s-a găsit o soluție.
Programul complet pentru rezolvarea problemei acoperirii tablei de șah cu un cal folosind metoda greedy în C++:
# include <iostream>
# include <cstring>
using namespace std;
const int N = 8 ;
bool isValid ( int x, int y, int visited[N][N], int n) {
return (x >= 0 && x < n && y >= 0 && y < n && visited[x][y] == -1 );
}
int getDegree ( int x, int y, int visited[N][N], int n) {
int degree = 0 ;
int movesX[] = { 2 , 1 , -1 , -2 , -2 , -1 , 1 , 2 };
int movesY[] = { 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 };
for ( int i = 0 ; i < N; i++) {
int nextX = x + movesX[i];
int nextY = y + movesY[i];
if ( isValid (nextX, nextY, visited, n)) {
degree++;
}
}
return degree;
}
bool getNextCell ( int x, int y, int visited[N][N], int & nextX, int & nextY, int n) {
int minDegree = N + 1 ;
int movesX[] = { 2 , 1 , -1 , -2 , -2 , -1 , 1 , 2 };
int movesY[] = { 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 };
for ( int i = 0 ; i < N; i++) {
int nextXtemp = x + movesX[i];
int nextYtemp = y + movesY[i];
if ( isValid (nextXtemp, nextYtemp, visited, n)) {
int degree = getDegree (nextXtemp, nextYtemp, visited, n);
if (degree < minDegree) {
minDegree = degree;
nextX = nextXtemp;
nextY = nextYtemp;
}
}
}
if (minDegree == N + 1 ) {
return false ;
}
return true ;
}
void solveKT ( int x, int y, int n) {
int visited[N][N];
memset (visited, -1 , sizeof (visited));
visited[x][y] = 0 ;
for ( int i = 1 ; i < n * n; i++) {
int nextX, nextY;
if ( getNextCell (x, y, visited, nextX, nextY, n)) {
visited[nextX][nextY] = i;
x = nextX;
y = nextY;
} else {
cout << "Nu se poate rezolva" << endl;
return ;
}
}
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
cout << visited[i][j] << " " ;
}
cout << endl;
}
}
int main () {
int n, startX, startY;
cout << "Introduceti dimensiunea tablei de sah: " ;
cin >> n;
cout << "Introduceti coordonatele de start (x y): " ;
cin >> startX >> startY;
// Verifică dacă coordonatele de start sunt în interiorul tablei de șah
if (startX < 0 || startX >= n || startY < 0 || startY >= n) {
cout << "Coordonatele de start nu sunt valide. Programul se va inchide." << endl;
return 0 ;
}
// Inițializează tabla de șah cu -1 (neparcurs)
int board[n][n];
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
board[i][j] = - 1 ;
}
}
// Setează poziția inițială a calului
board[startX][startY] = 0 ;
// Parcurge tabla de șah folosind algoritmul greedy
int x = startX;
int y = startY;
int movesX[] = { 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 };
int movesY[] = { 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 };
for ( int move = 1 ; move < n * n; move++) {
int minDegree = n + 1 ;
int nextX, nextY;
// Verifică toate mutările posibile din poziția curentă și alege mutarea cu cel mai mic grad
for ( int i = 0 ; i < 8 ; i++) {
int newX = x + movesX[i];
int newY = y + movesY[i];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && board[newX][newY] == - 1 ) {
int degree = 0 ;
for ( int j = 0 ; j < 8 ; j++) {
int nextX2 = newX + movesX[j];
int nextY2 = newY + movesY[j];
if (nextX2 >= 0 && nextX2 < n && nextY2 >= 0 && nextY2 < n && board[nextX2][nextY2] == - 1 ) {
degree++;
}
}
if (degree < minDegree) {
minDegree = degree;
nextX = newX;
nextY = newY;
}
}
}
// Nu există mutări posibile din poziția curentă
if (minDegree == n + 1 ) {
cout << "Nu exista solutie!" << endl;
return 0 ;
}
// Parcurge următoarea poziție
x = nextX;
y = nextY;
board[x][y] = move;
}
// Afișează soluția găsită
cout << "Solutia gasita este: " << endl;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
cout << board[i][j] << " " ;
}
cout << endl;
}
return 0 ; }