Cho bản cờ n x n ô tìm cách di chuyển một quân mã xuất phát từ một ô bất kì, mã di chuyển theo luật cờ vua và đi qua tất cả các ô, mỗi ô qua đúng một lần. Ví dụ. Hình 7 là một phương án với n - 5.

Bài toán 4. Mã đi tuần

Cho bản cờ n x n ô tìm cách di chuyển một quân mã xuất phát từ một ô bất kì, mã di chuyển theo luật cờ vua và đi qua tất cả các ô, mỗi ô qua đúng một lần. Ví dụ. Hình 7 là một phương án với n - 5.


#define MAX 8
using namespace std;
 
int A[MAX][MAX] = { 0 };//Khởi tạo mảng giá trị 0
int X[8] = { -2,-2,-1,-1, 1, 1, 2, 2};
int Y[8] = { -1, 1,-2, 2,-2, 2,-1, 1};
int n;// Số phần tử của bàn cờ bạn muốn tạo
int main() {
}
//Hàm xuất//
void xuat() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cout << A[i][j] << " ";
cout << endl;

//Hàm bước đi

void diChuyen(int x, int y) {

++dem;//Tăng giá trị bước đi
A[x][y] = dem;//Đánh dấu đã đi
        //Tìm tất cả các bước đi có thể đi và tiến hành đi thử
for (int i = 0; i < 8; i++) {
//Kiểm tra xem mã đã đi hết bàn cờ chưa
if (dem == n * n) {
cout << "Cac buoc di la: \n";
xuat();
exit(0);//kết thúc chương trình
}
//Nếu chưa đi hết bàn cờ thì tạo bước đi mới
int u = x + X[i];//tạo một vị trí x mới
int v = y + Y[i];//tạo một vịi trí y mới
//Nếu hợp lẹ thì tiến hành di chuyển
if (u >= 0 && u < n&&v >= 0 && v < n&& A[u][v] == 0)
diChuyen(u, v);
}
//Nếu không tìm được bước đi thì ta phải trả lại các giá trị ban đầu
--dem;
A[x][y] = 0;

}

#include<stdio.h>
#define MAX 8
using namespace std;
int A[MAX][MAX] = { 0 };//Khởi tạo mảng giá trị 0
int X[8] = { -2,-2,-1,-1, 1, 1, 2, 2};
int Y[8] = { -1, 1,-2, 2,-2, 2,-1, 1};
int dem = 0;//Số bước đi
int n;
void xuat() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%2d ", A[i][j]);
cout << endl;
}
cout << endl;
}
void diChuyen(int x, int y) {
++dem;//Tăng giá trị bước đi
A[x][y] = dem;//Đánh dấu đã đi
for (int i = 0; i < 8; i++) {
//Kiểm tra xem mã đã đi hết bàn cờ chưa
if (dem == n * n) {
cout << "Cac buoc di la: \n";
xuat();
exit(0);//kết thúc chương trình
}
//Nếu chưa đi hết bàn cờ thì tạo bước đi mới
int u = x + X[i];//tạo một vị trí x mới
int v = y + Y[i];//tạo một vịi trí y mới
//Nếu hợp lẹ thì tiến hành di chuyển
if (u >= 0 && u < n&&v >= 0 && v < n&& A[u][v] == 0)
diChuyen(u, v);
}
//Nếu không tìm được bước đi thì ta phải trả lại các giá trị ban đầu
--dem;
A[x][y] = 0;
}
int main() {
cout << "Nhap n: ";
cin >> n;
int a, b;
cout << "Nhap vi tri ban dau.\nx: ";
cin>>a;
cout << "y: ";
cin >> b;
diChuyen(a, b);
//Nếu không tìm được bước đi thì sẽ thông báo
cout << "Khong tim thay duong di.";
}

Bình luận

Giải bài tập những môn khác