Jezdec a šachovnice

Zadání

Vytvoříme program, který nalezne (alespoň) jednu cestu jezdcem skrz celou šachovnici, přičemž smí jezdec skočit na každé políčko nejvýše jednou a nesmí se ocitnout mimo šachovnici.

VSTUP: žádný
VÝSTUP: Něco takového (podle původních souřadnic a pořadí tahů):

Teorie

Jezdec se může pohybovat pouze následujícím způsobem:

Takže si musíme tahy uvést jako vektory:
TAH1 = (-1;-2)
TAH2 = (1;-2)
TAH3 = (2;-1)
TAH4 = (2;1)
TAH5 = (1;2)
TAH6 = (-1;2)
TAH7 = (-2;1)
TAH8 = (-2;-1)

Abychom neprocházeli všechny možnosti (což by trvalo příliš dlouho), budeme vybírat jen nejvhodnější tah, což bude ten, ze kterého vede co nejnižší množství cest dále. Abychom si ale nevzali možnost na dokončení, budeme po každém tahu kontrolovat, zda není nějaké políčko již "zazděné" - v tom případě se budeme muset vrátit a zvolit jiný tah.Při výběru nejlepšího následujícího tahu budeme vždy kontrolovat, zda je políčko ještě volné a zda neleží mimo naši šachovnici. Pokud se z aktuálního políčka nedokážeme dostat na další, musíme se vrátit a pokračovat dalším možným tahem.

Samotný program bude vypadat následovně:
1. Inicializace proměnných.
2. Začneme průchod šachovnicí z daného pole:
2a) Na aktuální políčko zapíšeme číslo tahu.
2b) Zkontrolujeme, zda není žádné nenavštívené tlačítko uvězněné. Pokud ano, vracíme se.
2c) Zjistíme nejlépe vyhovující tah.
2d) Postupujeme na další políčko, pokud to nelze, vracíme se na předchozí tah a jdeme jinudy.

Řešení

V celém programu budeme využívat několik proměnných:

final static int SIZE = 8;
static int[] moves;
static int[][] chessboard;
static final int[][] knightMoves = 
{
    {-1,-2},
    {1,-2},
    {2,-1},
    {2,1},
    {1,2},
    {-1,2},
    {-2,1},
    {-2,-1}
};

SIZE - velikost naší šachovnice
moves - pole, obsahující tahy, kterými jsme se dostali do aktuální pozice
chessboard - šachovnice, obsahuje políčka označená číslem, kdy jsme je navštívili
knightMoves - tahy, jak jsme si je již definovali.

Program začneme tedy inicializací proměnných:

public static void init(){
    for(int i = 0; i < moves.length; i++) moves[i] = -1;
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++){
            chessboard[i][j] = -1;
        }
}
public static void main(String[] args){
    moves = new int[SIZE * SIZE];
    chessboard = new int[SIZE][SIZE];
    init();
}

A hned po metodě init() zavoláme funkci throughChessboard(1, 7), která začne inicializací pomocných proměnných a pak začne iterativně procházet šachovnici.

public static void throughChessboard(int startX, int startY){
    int x = startX;
    int y = startY;
    boolean nextMove;
    int returnedMove = -1;
    for(int i = 0; i < moves.length; i++){
        nextMove = false;
        chessboard[y][x] = i + 1;
        if(behindWall(chessboard)){        
            returnedMove = moves[i - 1];
            moves[i - 1] = -1;
            moves[i] = -1;
            chessboard[y][x] = -1;
            x = x - knightMoves[returnedMove][0];
            y = y - knightMoves[returnedMove][1];
            chessboard[y][x] = -1;
            i = i - 2;
            continue;
        }
        returnedMove = findBestMove(x, y) - 1;
        for(int j = (returnedMove<0)?0:(returnedMove + 1); j < knightMoves.length && moves[i] == -1; j++){
            if(x + knightMoves[j][0] >= 0 && x + knightMoves[j][0] < SIZE &&
               y + knightMoves[j][1] >= 0 && y + knightMoves[j][1] < SIZE &&
               chessboard[y + knightMoves[j][1]][x + knightMoves[j][0]] == -1 &&
               (returnedMove == -1 || returnedMove != j)){
                x = x + knightMoves[j][0];
                y = y + knightMoves[j][1];
                nextMove = true;
                returnedMove = -1;
                moves[i] = j;
                break;
            }                
        }
        if(i == moves.length - 1 && isFull(chessboard)) break;
        if(!nextMove){
            returnedMove = moves[i - 1];
            moves[i - 1] = -1;
            moves[i] = -1;
            chessboard[y][x] = -1;
            x = x - knightMoves[returnedMove][0];
            y = y - knightMoves[returnedMove][1];
            chessboard[y][x] = -1;
            i = i - 2;
        }
    }
    showChessboard(chessboard);
}

Proměnné x a y budou uchovávat aktuální souřadnice na šachovnici, proměnná nextMove bude uchovávat booleovskou hodnotu, zda půjdeme na další tah a nebo se budeme vracet, a proměnná returnedMove uchovává číslo tahu, po kterém bychom měli pokračovat - defaultně bude obsahovat -1, čili budeme pokračovat následujícím, nultým tahem.

Následuje počátek cyklu, který neskončí, dokud nebudeme na konci pole tahů. Začneme označením aktuálního políčka číslem označujícím pořadí tahu, a poté budeme kontrolovat, zda jsme tímto tahem nějaké políčko neuvěznili. O zjištění, zda je nějaké políčko uvězněné, se postará metoda behindWall(chessboard):

public static boolean behindWall(int[][] chess){
    boolean isBehindWall = true;
    int count = 0;
    for(int i = 0; i < SIZE; i++){
        for(int j = 0; j < SIZE; j++){
            if(chess[i][j] == -1){
                isBehindWall = true;
                count++;
                for(int k = 0; k < knightMoves.length; k++){
                    if(j + knightMoves[k][0] >= 0 && j + knightMoves[k][0] < SIZE &&
                       i + knightMoves[k][1] >= 0 && i + knightMoves[k][1] < SIZE &&
                       chess[i + knightMoves[k][1]][j + knightMoves[k][0]] == -1){
                        isBehindWall = false;
                    }
                }
            } 
        }
    }
    if(count <= 2) return false;
    return isBehindWall;
}

Tato metoda zjišťuje, zda existuje neobsazené políčko, ze kterého se již nedá nikam skočit, pokud ano, vrátí false a v původním cyklu v metodě throughChessboard dojde k vymazání tohoto i předchozího tahu a budeme pokračovat dále následujícím možným tahem.

Následuje zjištění nejvhodnějšího tahu metodou findBestMove(x, y), která vypadá následovně:

public static int findBestMove(int x, int y){
    int bestMove = -1;
    int x2 = x;
    int y2 = y;
    int[] ways = new int[knightMoves.length];
    for(int i = 0; i < knightMoves.length; i++) ways[i] = 0;
    for(int i = 0; i < knightMoves.length; i++){
        x2 = x + knightMoves[i][0];
        y2 = y + knightMoves[i][1];
        if(x2 < 0 || x2 >= SIZE || y2 < 0 || y2 >= SIZE || chessboard[y2][x2] != -1) continue;
        for(int j = 0; j < knightMoves.length; j++){
            if(x2 + knightMoves[j][0] < 0 || x2 + knightMoves[j][0] >= SIZE ||
                    y2 + knightMoves[j][1] < 0 || y2 + knightMoves[j][1] >= SIZE ||
                    chessboard[y2 + knightMoves[j][1]][x2 + knightMoves[j][0]] != -1){
                ways[i]++;
            }
        }
    }
    int max = 0;
    for(int i = 0; i < knightMoves.length; i++)
        if(ways[i] > max){
            max = ways[i];
            bestMove = i;
        }
    return bestMove;
}

Touto metodou projdeme všechny možné tahy a spočteme, na kolik různých pozic nelze pokračovat. Tah, který má nejméně možností, kam pokračovat, určíme jako nejvhodnější (například tah, který může pokračovat jen na políčko, které může dále pokračovat jen na jedno další políčko, bude zvolen jako nejvhodnější). Abychom určili nejlepší následující tah, budeme srovnávat počet možných tahů, které by následovaly, a jejich srovnáním dostaneme ten nejlepší z nich.

Index tohoto tahu vrátíme a pokračujeme v cyklu metody throughChessboard. Z aktuální pozice se přesuneme nejvhodnějším tahem dále, pokud jsou podmínky splněné (tato pozice leží na šachovnici a zároveň na ní jezdec ještě nebyl), do pole tahů přidáme další hodnotu a pokračujeme od začátku cyklu.
Pokud ale nebyl nalezen žádný vhodný tah, musíme se vrátit a pokračovat následujícím možným tahem, protože aktuální větev je zřejmě slepá. Předtím ale ještě zjistíme, zda už nejsme na konci cyklu a zda není celá šachovnice již  "proskákána". To ověříme pomocí funkce isFull(chessboard):

public static boolean isFull(int[][] a){
    boolean full = true;
    for(int i = 0; i < a.length; i++)
        for(int j = 0; j < a.length; j++)
            if(a[i][j] == -1)full = false;
    return full;
}

Tato funkce pouze vyhledává políčka s hodnotou -1, pokud takové najde, znamená to, že průchod šachovnicí ještě není kompletní.

Poté se již jen zjišťuje, zda byl nalezen následující tah po aktuálním tahu, pokud ne, vrátíme se a zkusíme to s dalším tahem v pořadí.

Zbývá již jen jednoduchá metoda pro výpis šachovnice:

public static void showChessboard(int[][] chess){
    for(int i = 0; i < SIZE; i++){
        for(int j = 0; j < SIZE; j++)
            System.out.print(((chess[i][j]<10 && chess[i][j]>=0)?" " + chess[i][j]:chess[i][j]) + " | ");
        System.out.println();
    }            
    System.out.println();
}

Pokud byste si ještě přáli vypsat pořadí tahů, jak táhnout, může přijít vhod funkce Arrays.toString(názevPole) - nechte si ji vypsat jako

System.out.println(Arrays.toString(moves));

a budete mít vypsána čísla jednotlivých tahů.