Ot Sayohati
Ushbu maqolamizda ajoib boshqotirmalardan biri bo'lgan «Knight's tour» ya'ni «Ot sayohati» masalasiga to'xtalib o'tmoqchimiz. Masala sharti juda ham oddiy: NxN o'lchamdagi shaxmat doskasining barcha kataklarini ot bilan yurib chiqish, bunda toychoq har bir katakka bir marta tashrif buyuradi. Masala bilan wikida batafsil tanishib chiqishingiz mumkin.
Bu masala qadim zamonlardan beri mavjud, turli yechimlar va algoritmlar taklif etilgan. Eng sodda va xozircha tushunishimizga oson algoritmi Warnsdorff tomonidan 1983-yili taklif etilgan: ya'ni otni joriy C katakdan keyingi shunday N katakka yurishimiz kerakki, bunda N katakdan keyingi yura olishimiz mumkin bo'lgan F kataklar soni minimal bo'lsin. Agar jumlani tushunmagan bo'lsangiz qayta-qayta o'qib ko'ring :). Bu usul bilan 5x5 dan to 76x76 o'lchamdagi doskada otni yuritib chiqishimiz mumkin. Undan katta o'lchamlarda toychoq adashib qolish extimoli mavjud. Bu usulda masalaning yechimi otning boshlang'ich nuqtasiga ham bog'liqligini aytib o'tishim kerak.
Hozircha shu. Agar ayni masala ustida izlanib ko'rgan bo'lsangiz va Sizda optimallashtirish yoki boshqa algoritmlar bilan yechimni topish yo'llari yoyinki boshqa dasturlash tillarida dastur kodi bo'lsa biz bilan o'rtoqlashasiz degan umiddamiz.
Eng oson qoida
Bu masala qadim zamonlardan beri mavjud, turli yechimlar va algoritmlar taklif etilgan. Eng sodda va xozircha tushunishimizga oson algoritmi Warnsdorff tomonidan 1983-yili taklif etilgan: ya'ni otni joriy C katakdan keyingi shunday N katakka yurishimiz kerakki, bunda N katakdan keyingi yura olishimiz mumkin bo'lgan F kataklar soni minimal bo'lsin. Agar jumlani tushunmagan bo'lsangiz qayta-qayta o'qib ko'ring :). Bu usul bilan 5x5 dan to 76x76 o'lchamdagi doskada otni yuritib chiqishimiz mumkin. Undan katta o'lchamlarda toychoq adashib qolish extimoli mavjud. Bu usulda masalaning yechimi otning boshlang'ich nuqtasiga ham bog'liqligini aytib o'tishim kerak.
Dastur kodi
Endi yuqorida berilgan algoritmni tadbiq etgan holda yechimni kodlashtirib chiqsak. Ushbu yechimda men otni boshlang'ich holatini A1 deb oldim, ya'ni yurishni A1 katakdan boshlaymiz. Agar qaysidir N o'lchamda yechim topilmasa otni boshlang'ich holatini almashtirish kerak. Yechim java dasturlash tilida yozilgan. Izoh orasida asosiy qadamlarga KATTA_HARFLARDA ssilka qo'yilgan.import java.util.Scanner;
public class ChessBoard {
protected int board[][]; //Shaxmat taxtasi - butun sonlar massivi
protected int n, counter;
protected int[] moveX = {1, 1, -1, -1, 2, 2, -2, -2}; // ot yura olishi mumkin bo'lgan X va Y yo'nalishlar
protected int[] moveY = {2, -2, 2, -2, 1, -1, 1, -1}; // Masalan moveX[a]:moveY[a] yo'nalishda yura oladi
protected int currentX, currentY; // otning boshlang'ich koordinatasi
public static void main(String[] args) { // Dastur main funksiyadan boshlab ishga tushadi
int n; // shaxmat doskasi o'lchami NxN
Scanner in = new Scanner(System.in);
System.out.print("N=");
n = in.nextInt();
ChessBoard board = new ChessBoard(n); // shaxmat doskasi obyekti yaratildi
board.startMove(); // yurishni boshlaymiz
board.draw(); // yakuni natijani chop etish
}
public ChessBoard(int n) {
this.n = n;
board = new int[n][n];
currentX = 0; // boshlang'ich holatda ot 1:1 katakda joylashgan (ya'ni A1)
currentY = 0;
counter = 1; // qaysi kattakka yursa shu katakni otning n-yurishi bilan raqamlab ketamiz
board[currentX][currentY] = counter;
}
public void startMove() {
this.moveHorse(currentX, currentY, true); // Rekursiv metodga murojaat
}
/**
* Ushbu funksiya cx:cy katakdan qolgan kataklarga yura olishlar sonini hisoblaydi,
* ya'ni otning keyingi xodlari orasidan shu xodlar uchun navbatdagi xodlar sonining
* eng minimalini topadi va topilgan xod bo'yicha yuradi.
*
* Masalan ot ayni damda cx:cy katakda turibdi, uning navbatdagi xodi quyidagi kataklar bo'lishi mumkin:
* (moveX, moveY massiv sonlari kombinatsiyasi) -->COMBINATION
* N1. cx+1:cy+2 = nx:ny
* N2. cx+1:cy-2 = nx:ny
* N3. cx-1:cy+2 = nx:ny
* N4. cx-1:cy-2 = nx:ny
* N5. cx+2:cy+1 = nx:ny
* N6. cx+2:cy-1 = nx:ny
* N7. cx-2:cy+1 = nx:ny
* N8. cx-2:cy-1 = nx:ny
*
* Albatta bu kataklarning barchasi NxN doska ichida yotmasligi mumkin yoki qaysidir biriga allaqachon yurilgan.
* Bu kabi kataklarni hisobdan chiqaramiz. -->IS_VALID_MOVE
*
* Endi avvalgi har bir N hod uchun keyingi F xodlar soni M ni hisbolaymiz (COMBINATION bosqich bilan bir xil).
* Masalan:
* N1 da turgan holda F1, F4, F5 (jami M=3 ta) katakka yura olishi mumkin -->FIND_MIN
* N2 da turgan holda F2, F7 (jami M=2 ta) katakka yura olishi mumkin
* va hokazo...
*
* Endi otni min(M) bo'lgan N katakka yuramiz, masalan N2 katakka -->NEXT_MOVE
*/
public int moveHorse(int cx, int cy, boolean findMin) {
int x, y, moves = 0, min = 10, nextX = 0, nextY = 0;
boolean canMove = false;
for (int k = 0; k < 8; k++) {
x = cx + moveX[k]; // <--COMBINATION
y = cy + moveY[k];
if ((x < 0 || x > n - 1 || y < 0 || y > n - 1) || board[x][y] != 0) //<-- IS_VALID_MOVE
continue;
moves++;
if (findMin) {
int minM = this.moveHorse(x, y, false); //<--FIND_MIN
if (minM < min) {
min = minM;
nextX = x;
nextY = y;
canMove = true;
}
}
}
if (canMove) {
counter++;
board[nextX][nextY] = counter;
return this.moveHorse(nextX, nextY, true); // <-- NEXT_MOVE
}
return moves;
}
//Doska holatini chop etish
public void draw() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%5d", board[i][j]);
}
System.out.println();
}
System.out.println();
System.out.println((counter == n * n) ? "Completed" : "Not Completed");
}
}
Natija
N=5
1 12 25 18 3
22 17 2 13 24
11 8 23 4 19
16 21 6 9 14
7 10 15 20 5
Completed
N=11
1 4 49 38 21 6 19 16 23 8 11
50 37 2 5 18 39 22 7 10 15 24
3 48 51 106 45 20 17 40 25 12 9
36 107 46 59 52 109 44 57 14 41 26
47 60 117 108 105 58 53 110 43 56 13
116 35 102 97 114 111 104 71 54 27 42
61 96 115 118 103 98 113 80 85 72 55
34 121 62 101 112 119 86 99 70 79 28
63 92 95 120 87 100 81 84 73 76 69
94 33 90 65 82 31 88 67 78 29 74
91 64 93 32 89 66 83 30 75 68 77
Completed
Hozircha shu. Agar ayni masala ustida izlanib ko'rgan bo'lsangiz va Sizda optimallashtirish yoki boshqa algoritmlar bilan yechimni topish yo'llari yoyinki boshqa dasturlash tillarida dastur kodi bo'lsa biz bilan o'rtoqlashasiz degan umiddamiz.
3 комментария