Bypass sakk lovag ellátás
- Nyilatkozat a problémát
- bejáráshoz
- Egy példa a program
- 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.
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ő:
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.
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.
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.
//// 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