Bypass sakk lovag ellátás

előző ◈ a következő
  1. Nyilatkozat a problémát
  2. bejáráshoz
  3. Egy példa a program
  4. lista:

Ez érdekes puzzle javasolták matematikus Euler. Feladat első pillantásra meglehetősen egyszerű # 150; szüksége van egy sakk lovag található egy tetszőleges cellában a sakktábla, hogy megkerülje az összes többi sejtek a fórumon, amelynek mérete is önkényesen. Azonban csak egyszer úgy tűnik, mint egy sejt.

A ló, mint tudja, elmegy L-alakú. Ie két sejtek bármilyen irányban (felfelé, lefelé, balra, jobbra), és egy cella egy merőleges. Így, egy ló, ez lehet egy legfeljebb nyolc különböző stroke előre meghatározott sejtek (vagy kevesebb, ha a ló található a széleit a fórumon).

A probléma megoldására a számítógép szükséges kialakítani a szabályokat, amelyek szerint a számítógép fogja választani a lépés. Elvileg, a következő lépés lehet véletlenszerűen kiválasztott.

Az eredeti szabály, amely egy lineáris idejű algoritmust szegélylécek, Varnsdorf (Warnsdorff) javasolták 1983-ban. Valósítottam meg a saját természetesen a munka.

Az algoritmus megfogalmazása nagyon egyszerű: a következő lépés a ló, hogy nem egy cellában, ahol a lehető legkevesebb mozog. Ha ugyanaz a sejtek száma a mozgást, akkor lehet választani.

A gyakorlatban ez nem valósul meg, például, a következők szerint. Mielőtt minden mozog a ló értékelték értékelés legközelebbi elérhető területeken - mely területeken a ló még nem volt, és tudja mozgatni egy körben. Értékelés mező határozza meg a rendelkezésre álló területek mellette. Minél alacsonyabb a minősítés, annál jobb. Aztán előrelépést tett a helyszínen a legalacsonyabb minősítés (a bármely olyan, ha egynél több), és így tovább, amíg van hová menjen.

A heurisztika mindig dolgoznak a táblák 5x5 legfeljebb 76x76 sejtek nagy tábla mérete ló megtorpant. Ezen túlmenően, a szabályon alapulnak az algoritmus nem ad az összes lehetséges megoldást (azaz ló sávok), akkor mehet a szabályok ellen, és még mindig kielégítő kerek feladat.

Van egy lineáris algoritmus táblák bármilyen méretű, amely elválasztja a tábla kisebb darabokra, de azért, mert a rengeteg különleges esetekben, ez elég bonyolult, és nem olyan érdekes, mint az elegáns heurisztikus.

Bypass sakk lovag ellátás
Ezen kívül szeretném elmagyarázni, hogyan kell elvégezni a lépés. Már említettük, hogy nyolc lehetséges lépések. ezek mind kódolt számokkal 0 és 7. ábrán. sorolja fel a lehetséges lépéseket.

Minden természetesen lehet leírni, mint mozgó egy előre meghatározott számú sejtet vízszintesen és függőlegesen. Például, a zéró elmozdulás megfelel mozgatni két vízszintes sejtekben, és a „-1” vertikális cella (mínusz jel jelzi a mozgás irányát).

Kitöltése a rendelkezésre álló tömb egy kicsit bonyolultabb. Minden elem felel meg egy cellát a táblára, de itt vagyunk felvenni információkat, hogy hány sejtek sétálhatunk a forgatáson. Például, az A1 cellában hasonlítanak két sejt (c2 és b3). Egy sor ez előtt a probléma megoldása a következő:

Bypass sakk lovag ellátás

Egy példa a program

Dialog létrehozásának sakktábla egy ló, amely úgy döntünk, hogy a mező mérete, a cella mérete, helyzete és a többi paramétert a ló. Azt is letölthető a kép elemeit a testület a fájlokat.

Bypass sakk lovag ellátás

5x5 létrehozott mező, a ló áll a 2x4 helyzetbe. Most, hogy a területen már létrejött, akkor fuss az algoritmus bypass ló fórumon.

Bypass sakk lovag ellátás

Eredmény bejáráshoz látható a fedélzeten látható számok bejárás érdekében ló fórumon. Törölheti a bejárási sorrendet, és futtassa az algoritmus újra. Akkor is megy ló segítségével nyilak és egerekben.

Bypass sakk lovag ellátás

//// változat 8 végleges Javasoljunk

// felhívni a ló kép területén belül

g.drawImage (HorseImage, EventBoardHorseMovedelX, EventBoardHorseMovedelY, null);

* Létrehoz egy háttérképet a sakktábla egy sűrű elrendezésű világos és sötét sejtek

* Ha a kép nem init. (Nulla), a háttér nem húzott,

* Az, hogy a napelemek elrendezésének „a kurzív, egyikén keresztül,” Melyik az első cella a mező határozza meg az első paraméter.

* @param whiteCells fényképek fényes cella (cella).

* @param blackCells fényképek sötét cellában (cella).

* @param firstCellWhite ha igaz - az első cella a fény mező, ha hamis - a sötétben

* @return igaz - háttér festett hamis - a háttér nem levonni a tény, hogy nem izobrascheniya init. vagy init. tábla mérete.

public boolean BoardFonCreate (BufferedImage whiteCells, BufferedImage blackCells, logikai firstCellWhite)

BoardFon = új BufferedImage (BoardSize, BoardSize, BufferedImage.TYPE_INT_RGB);

int Kx = 0 /// koordináták "rajz pont"

boolean firstCell = firstCellWhite; /// jelzőt az első cella

Graphics Fon = BoardFon.createGraphics (); /// rajz

Fon.clearRect (0, 0, BoardFon.getWidth (), BoardFon.getHeight ()); /// tisztít

A (int j = 0; j

Kx = 0; // egy új sorban

A (int i = 0; i

Fehér // ha még sejt és az első cella fehér

Fehér // ha páratlan cella és az első cella a fekete

Fon.drawImage (whiteCells, Kx, KY, CellsSize, CellsSize, null);

Fon.drawImage (blackCells, Kx, KY, CellsSize, CellsSize, null);

Kx = kx + CellsSize; // pass line a megfelelő rajz a következő cella (sejtek)

/// következő sorban kezdődik az ellenkező szín a sejt

* Zászlója az a tény, hogy a testület húzta a ló az egérrel

* A kezdeti koordinátáit a ló, hogy húzza, X gorizotali (pixel)

* A kezdeti koordinátáit a ló, hogy húzza, Y függőleges (pixel)

* Változás koordináták X gorizotali (pixel)

* Változás koordinálja, Y függőleges (pixel)

* A koordináták az egér kattintva a bal egérgombbal a ló koordinátarendszerben (JButton), X gorizotali (pixel)

* Egér koordináták, ha megnyomja a bal egérgombbal ló egy koordináta-rendszerben (JButton), Y függőleges (pixel)

* Pereprorisovka panel (board)

* A kiindulási helyzetbe, amikor mozog a nyíl

* Mielőtt az első része a „T” alakú szélütés

* Ie, a vízszintes helyzetben a sejt (db, sejtek).

* A kiindulási helyzetbe, amikor mozog a nyíl

* Mielőtt az első része a „T” alakú szélütés

* Ie, A függőleges helyzete a sejt (db, sejtek).

* Kód billentyűt nyom első, „első kézből”

* Component tolva az első része a „T” alakú szélütés

* (Hossza a szegmens a sejtben 1)

végleges int firstPartG = 2;

* Irányba, amíg az első része a „T” alakú szélütés

* A második rész merőleges az első ( „L”),

* True - függőlegesen. false - vízszintesen.

* Kód billentyűt nyom két: azaz a második nyíl miután az első nyíl

* Component eltolva a második része a „T” alakú szélütés

* (Hossza a szegmens a sejtben 1)

végleges int secondPartG = 1;

* A ló egy példányát (amely a fedélzeten)

nyilvános clHorse Ló = null;

* Class Ló örökölt JButton további elhelyezését a panel fórumon.

* A fényképek ló nem szerepel az osztály, és az osztály venni a táblák, valamint a paraméterek és funkciók veszik.

* (Osztályok Ló és tábla nem választhatók egyáltalán).

osztály clHorse kiterjed JButton

private static final hosszú serialVersionUID = 1L;

* Az alapértelmezett konstruktor inicializálja a ló

this.setBounds (0, 0, CellsSize, CellsSize) /// fel a lovag a táblára (ez az alapértelmezett)

this.addKeyListener (új KeyMoveListener ()); // hozzá hallgató billenytûkombinációkat ló események

mouseMoveListener = new MouseMoveListener (); // a hallgató számára egéreseményeket kapcsolatban a ló

* A kivitelező inicializálja a lovat üzembe azt egy állványon

* @param PosX sejtszámot vízszintesen

* @param jelige sejtszám függőleges

clHorse (int PosX, int posy)

ez (); // hívja a kivitelező (ez az alapértelmezett) ló

HorseMove (PosX, bokréta); /// ló hordoz egy bizonyos helyen a fedélzeten

* Pozíció ló vízszintes sejtek: 0,1,2. CellsNumberX-1

* Pozíció ló függőleges cella: 0,1,2. CellsNumberY-1

Kapcsolódó cikkek

előző ◈ a következő