A probléma elhelyezése királynők
Friss hírek
A probléma az elhelyezés dáma. Visszalépés.
A probléma az elhelyezés dáma.
Egy kis tipp, hogy a problémát a mérleg 8 dáma.
Az a probléma lényegét. Szükséges volt, hogy megtalálja az egyensúlyt a nyolc dáma normális sakktábla, így nem nyomja egymáshoz.
Meg kell jegyezni, hogy azonnal át az összes lehetőséget a szabályok nem tudjuk. Pontosabban, akkor biztosan írni egy programot, de akkor folytassa másképp optimálisabban.
Néhány megjegyzés a megállapodás a tárolási módszer.
Számoljuk ki, hogyan fogjuk tárolni a helyét a dáma a fedélzeten. A kézenfekvő megoldás az lenne, hogy egy 8x8 tömb és írj rá egy vagy nulla, attól függően, hogy a sejt által elfoglalt egy queen-e vagy sem.
De gondoljunk bele, mi szükség van az egész táblát? Kiderült, hogy van. Emlékeztetünk, hogy a királynő sétál. Mindenesetre a cellák száma függőlegesen, vízszintesen vagy átlósan. Nyilvánvaló, hogy ha egy bizonyos függőleges queen, aztán ebben a függőleges másik királynő nem működik, mert fognak verni egymást.
Logikus, hogy egy egydimenziós tömb nyolc elem, amelyek mindegyike megfelel az egyik iparágakban. Ha az érték minden egyes eleme felel meg a vonalat, amelyen van szerelve a királyné. Az alábbi ábra szemlélteti ezt az elvet nagyon jól.
Ellenőrzését, hogy a mező „támadás alatt”, vagy sem.
Leírjuk matematikailag, amelyek sejtek sakktábla „támadás alatt” Queen szereljék be a cellába [i] [j].
Tekintse meg az alábbi ábrát.
Ezek a feltételek könnyű megváltoztatni egy módja tartani a királynők elhelyezést.
Tegyük fel, hogy van már néhány sor királynők, amelyek nem érik egymást. Mik az előírt feltételeket a következő királynő?
Egyértelmű, hogy meg kell végighaladni az egyes korábbi elemek. Tegyük fel, hogy szeretnénk, hogy a királynő a helyzetben k.
Kezdjük, hogy ellenőrizze, az első tétel, benne írunk értéke nyolc. Következésképpen k meg kell egyeznie a nyolc, vagy két queen lesz ugyanazon a vízszintes vonal. Ezen túlmenően, k + 4! = 8 + 1 (a feltétele a zöld vonal), egyébként igyekszünk tenni a királynő egy forgalmas átlós. Végül, k-4! = 8-1 (a feltétele a kék vonal), ellenkező esetben meg fogjuk találni magunkat ismét a diagonális, ami verte a másik királynő. Állapotának ellenőrzése a piros vonal nem szükséges elvégezni, mert így a képviselő setup memóriában nem teszi lehetővé egy, hogy egy vízszintes két dáma.
Hasonló ellenőrzéseket kell végeznie a királynők, aki ezen a ponton már telepítve van a fedélzeten. Ésszerű kiosztani ezeket a vizsgálatokat egy függvényt, amely két paramétert - a húr oszlop és a sejtek, amelyekben szeretnénk beállítani a királyné.
Az alap algoritmus megoldásokat. Visszalépés.
Most megvitassák az alap algoritmus valósítja összehangolás dáma. Mindent meg fogunk tenni, mint ahogy azt cselekedni, ha lenne egy igazi társasjáték a szemed előtt.
Helyezve először királynő az első cellában az első függőleges. Ennek megfelelően az első elem a tömb tartani a yedinichku. Nos, az első királyné beállítva. Itt az ideje, hogy próbálja meg létrehozni a második királynő.
Úgy kell a második vízszintes.
Ellenőrizze a második cella, a második függőlegesen. Az ellenőrzés eredményét nem kielégítő, ezen a területen is veri a korábban megállapított királynő.
Most ellenőrizze a harmadik cella a második függőleges, lehet, hogy a megközelítés? Nagyon illik. Állítsa a királyné. Mi jár a telepítés egy harmadik királynő a harmadik függőleges.
Azáltal, hogy elkezdte végrehajtani a harmadik cella 1 függőlegesen.
Azt hiszem, nyilvánvaló, hogy sem az első, sem a második, sem a harmadik, sem még egy negyedik sejtek nem fogunk csinálni, mert verte a korábban megállapított királynők. De az ötödik cella lesz csak jobb, mert sem az első, sem a második királynők nem üt. Tehát, hogy telepíteni a harmadik királynőt.
Hasonló módon töltse ki a negyedik, ötödik, hatodik és hetedik függőleges. Bár lehetséges, hogy végre minden szabványos felsorolás két ciklusban. A külső hurok mozog az összes sorok 1-8, és a belső kontúrokat.
Külön fontolniuk a királyné az utolsó függőleges.
Ha te mindent algoritmus szerint, akkor ezen a ponton kap a helyzet a jobb oldalon látható. Kiderült, hogy a jelenlegi királynő sehol telepíteni, mint az összes sejteket a függőleges dobogó korábban megállapított hét dáma.
Mit kell tenni? Be kell, hogy lépjen vissza, és próbálja meg a hetedik királynő egy másik helyre.
Ez a művelet a visszatérés.
Ellenőrizni fogja csak azok a sejtek 5 és 8 Könnyen, hogy megbizonyosodjon arról, hogy egyikük sem nem alkalmas. Tehát végre egy újraindítás és próbálja meg létrehozni az ötödik királyné egy új helyre.
Ellenőrizze, ahogy lehet sejtette kezdjük a harmadik cella az ötödik függőleges. Nem áll jól nekünk, mert a támadás alatt, és két dáma egyszerre, a második és a harmadik. De a negyedik cella ingyenes, és így bele, és fogjuk fel a királynő.
Folytatva ebben a szellemben (váltakozó létesítmények visszatér), előbb-utóbb befut egy ilyen elrendezés királynők, amely megfelel minden követelménynek. Más szóval a hajón lesz található, 8 dáma, hogy nem üt egymást. Megbotlott egy ilyen megállapodás, akkor tartsa egy külön tömbben, vagy azonnal megjelenik. Ezt követően, akkor folytatni kell a keresést.
Tehát ez egy hatalmas hegy. Ezen ismeretek Térjünk most megpróbálja írni a megfelelő programot.