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.

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.