Trong cờ vua, chúng ta biết rằng kỵ sĩ có thể nhảy theo một cách đặc biệt. Nó có thể di chuyển hai hình vuông theo chiều ngang và một hình vuông theo chiều dọc hoặc hai hình vuông theo chiều dọc và một hình vuông theo chiều ngang theo mỗi hướng, Vì vậy, chuyển động hoàn chỉnh trông giống như chữ cái tiếng Anh ‘L’.
Trong bài toán này có một bàn cờ trống, và một kỵ sĩ xuất phát từ vị trí bất kỳ trong bàn cờ, nhiệm vụ của chúng ta là kiểm tra xem quân sĩ có thể đi thăm tất cả các ô trong bàn cờ hay không. Khi Nó có thể truy cập tất cả các ô vuông, hãy đặt số lần nhảy cần thiết để đến vị trí đó từ điểm xuất phát.
Sự cố này có thể có nhiều giải pháp, nhưng chúng tôi sẽ cố gắng tìm ra một giải pháp khả thi.
Đầu vào và Đầu ra
Input: The size of a chess board. Generally, it is 8. as (8 x 8 is the size of a normal chess board.) Output: The knight’s moves. Each cell holds a number, that indicates where to start and the knight will reach a cell at which move. 0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12
Thuật toán
isValid (x, y, giải pháp)
Đầu vào - Đặt x và y và ma trận nghiệm.
Đầu ra - Kiểm tra xem (x, y) đã ở đúng vị trí và chưa được chỉ định chưa.
Begin if 0 ≤ x ≤ Board Size and 0 ≤ y ≤ Board Size, and (x, y) is empty, then return true End
knightTour (x, y, move, sol, xMove, yMove)
Đầu vào - (x, y) vị trí, số lần di chuyển, ma trận nghiệm và danh sách chuyển động x và y có thể có.
Đầu ra - Ma trận giải pháp được cập nhật nếu nó tồn tại.
Begin if move = Board Size * Board Size, then //when all squares are visited return true for k := 0 to number of possible xMovement or yMovement, do xNext := x + xMove[k] yNext := y + yMove[k] if isValid(xNext, yNext, sol) is true, then sol[xNext, yMext] := move if knightTour(xNext, yNext, move+1, sol, xMove, yMove), then return true else remove move from the sol[xNext, yNext] to backtrack done return false End
Ví dụ
#include <iostream>
#include <iomanip>
#define N 8
using namespace std;
int sol[N][N];
bool isValid(int x, int y, int sol[N][N]) { //check place is in range and not assigned yet
return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
void displaySolution() {
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
cout << setw(3) << sol[x][y] << " ";
cout << endl;
}
}
int knightTour(int x, int y, int move, int sol[N][N], int xMove[N], int yMove[N]) {
int xNext, yNext;
if (move == N*N) //when the total board is covered
return true;
for (int k = 0; k < 8; k++) {
xNext = x + xMove[k];
yNext = y + yMove[k];
if (isValid(xNext, yNext, sol)) { //check room is preoccupied or not
sol[xNext][yNext] = move;
if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true)
return true;
else
sol[xNext][yNext] = -1;// backtracking
}
}
return false;
}
bool findKnightTourSol() {
for (int x = 0; x < N; x++) //initially set all values to -1 of solution matrix
for (int y = 0; y < N; y++)
sol[x][y] = -1;
//all possible moves for knight
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
sol[0][0] = 0; //starting from room (0, 0)
if (knightTour(0, 0, 1, sol, xMove, yMove) == false) {
cout << "Solution does not exist";
return false;
} else
displaySolution();
return true;
}
int main() {
findKnightTourSol();
} Đầu ra
0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12