A feladat leírása
A 8-királynő probléma ismertetése
A nyolckirálynő-probléma egy sakkfeladvány, lényege a következő: hogyan illetve hányféleképpen lehet 8 királynőt (vezért) úgy elhelyezni egy 8×8-as sakktáblán, hogy a sakk szabályai szerint ne üssék egymást. Ehhez a királynő/vezér lépési lehetőségeinek ismeretében az kell, hogy ne legyen két bábu azonos sorban, oszlopban vagy átlóban.
A nyolckirálynő-probléma egy példa az ennél általánosabb „n királynő problémára”, ami azt a kérdést veti fel, hányféleképpen lehet lerakni n darab királynőt egy n×n-es táblán.
A 8-királynő probléma (8-queens problem) az egyik legöregebb algoritmuselméleti probléma, sakkfeladvány. A probléma lényege, hogy 8 királynőt (melyeket szokás vezérnek is nevezni) kell elhelyezni egy hagyományos 8 x 8-as sakktáblán, oly módon, hogy azok a sakk szabályai szerint ne kerüljenek ütésbe. Ehhez a királynő (vezér) lépési lehetőségeinek ismeretében az szükséges, hogy egynél több bábu ne legyen azonos sorban, azonos oszlopban, illetve átlóban.
A 8-királynő probléma tulajdonképpen egy speciális esete az ennél általánosabb n-királynő problémának. Ezen probléma azt a kérdést veti fel, hogy hányféleképpen lehet lerakni „n” darab királynőt (vezért) egy n x n-es sakktáblán.
A probléma rövid története
A problémát először Max Bezzel (1824. február 4. - 1871. július 30.), német sakkozó vetette fel 1848-ban [1]. A probléma azért is bizonyult izgalmasnak, mert látszólag néhány próbálkozás árán megfejthető, az egzakt megoldás azonban csak a matematika komolyabb eszközeinek használatával található meg. Az évek során sok matematikus – többek között Carl Friedrich Gauss (1777. április 30. - 1855. február 23.), német matematikus és természettudós [2], illetve Georg Cantor (teljes nevén: Georg Ferdinand Ludwig Philipp Cantor), (1845. március 3. - 1918. január 6.), orosz születésű és élete jelentős részét Németországban töltő matematikus – foglalkozott vele és az általánosított n-királynő problémával [3]. Gauss elsőre csak 72 megoldást talált meg a lehetséges összes 92-ből (a 8-királynő problémára).
Az első megoldást Franz Nauck, német matematikus adta 1850-ben, aki szintén foglalkozott a feladat n x n-es kiterjesztésével, az n-királynő problémával, mely probléma felvetését sokan neki tulajdonítják [4].
24 évvel később, 1874-ben S. Günther egy látszólag egész más terület, a determinánsok segítségével jutott eredményre, amivel lerakhatók a bábuk. Később ezt az eljárást finomította James Glaisher (teljes nevén: James Whitbread Lee Glaisher), (1848. november 5. - 1928. december 7.), angol matematikus [5] [6].
Edsger Dijkstra (teljes nevén: Edsger Wybe Dijkstra), (Rotterdam, 1930. május 11. - Hollandia, Nuenen, 2002. augusztus 6.), holland matematikus, informatikus, 1972-ben arra használta ezt a problémát, hogy bemutassa a strukturált programozás előnyeit, erejét. Publikált egy részletes leírást a probléma egy lehetséges megoldását jelentő backtrack algoritmusról („depth-first backtracking algorithm”) [7] [8]. A későbbiekben ez az algoritmus részletesebben is kifejtésre kerül.
A feladat megoldása
A probléma megoldása
A megoldás nehezen számítható, mivel a bábuknak összesen (64 „alatta” 8) = 4426165368 különböző lerakása létezik, de ebből csak 92 felel meg a 8-királynő probléma szabályainak. Ez igen nagy számítási időt jelent kimerítő keresést alkalmazva. Az összes lehetséges lerakások száma, és ezáltal a számításhoz szükséges idő csökkenthető azáltal, hogy bevezetünk egy olyan egyszerű és magától értetődő szabályt, miszerint minden sorban (vagy oszlopban) csak egy-egy bábu állhat. Így a vizsgálandó lerakások száma 8^8 = 16777216-ra redukálódik. Ez 16884-szer kevesebb, mint az első esetben, kimerítő keresést feltételezve. Ugyan még ebben az esetben is kimerítő keresést alkalmazunk, bizonyos lehetőségeket kihagyva, de n = 8 királynő esetén, egy 8 x 8-as sakktáblán már kezelhető lépésszámhoz jutunk. Ugyanakkor nagy „n” esetén, például n = 1.000.000-ra továbbra is megengedhetetlenül nagy a lépésszám. Mint azt láthatjuk, a „próbálgatáson” alapuló kimerítő keresésnél intelligensebb keresési algoritmusra van szükségünk a probléma polinomiális időben történő megoldásához.
Első megközelítésben alkalmazzunk egy egyszerű intuitív megoldást. A sakktábla legbaloldalibb oszlopába helyezzünk el egy királynőt (legfelső = legkisebb sorszámú sorba, a sorok sorszáma lefelé haladva növekszik). Ezt követően minden – még nem foglalt – legbaloldalibb (üres) oszlopba helyezzünk egy-egy királynőt, úgy hogy azt ne támadja egyetlen másik sem. Tehát az adott királynőt mindig a legkisebb sorszámú olyan sorba helyezzük, ahol az nem kerül ütésbe. Ha a királynő egy adott sorban ütésbe kerülne, akkor az adott királynő oszlopában ahhoz a sorhoz tartsuk nyilván, hogy hány darab másik királynő által kerülne ütésbe. Ha a lerakás során olyan eset fordulna elő, hogy az adott királynőt bármelyik sorba is helyeznénk, az mindig ütésbe kerülne más királynő/királynők által, akkor a királynőt helyezzük abba a legkisebb sorszámú sorba, ahol az a legkevesebb másik királynővel kerülne ütésbe. Ezzel a lépéssel azonban nem lenne helyes a lerakás, ezért a most lerakott királynőtől balra eső oszlopban (konkrétan abban az oszlopban, ahonnan a királynőnk „ütve van”), (nyilván ez az oszlop létezik, hiszen a tőlünk balra eső „térfélről” kerültünk ütésbe) helyezzük a királynőt az abban az oszlopban lévő legkisebb sorszámú olyan sorba, ahol az a legkevesebb, tőle balra eső királynővel kerülne ütésbe. Szerencsés esetben létezik olyan sor is, ahol a királynő nem kerül ütésbe. Nyilván ekkor az előbbi szabálynak megfelelően ezt a sort választjuk, illetve ha több ilyen sor is van, akkor ezek közül a legkisebb sorszámút. Ebben az esetben már helyes a lerakás, ellenkező esetben ismételjük az eljárást addig (mindig balra haladva), amíg végül helyes lerakáshoz jutunk (mindig lesz ilyen). Majd, ha még maradt bábunk, akkor azokat is hasonlóan próbáljuk meg lerakni. Ez az eljárás biztosan ad jó megoldást. Az eljárással csak kb. 2000 állapot fordul elő.
Algoritmusa:
Algoritmizálási szempontból a bábuk helyét érdemes tömbként kezelni: mivel minden sorban csak egyetlen bábu állhat, ezért elég a sorokat megszámozni (1-től n-ig), majd n darab számot lejegyezni aszerint, hogy az n-edik sorban hányadik helyen áll bábu.
Itt egy algoritmus, ami egy - a probléma szabályainak megfelelő - tömböt ad eredményül (n≥4 és n=1 esetekre):
Osszuk el n-et 12-vel. Jegyezzük le a maradékot.
Írjuk le egy listába 2-től n-ig a páros számokat növekvő sorrendben.
Ha a maradék 3 vagy 9, akkor a 2-es számot vigyük át a lista végére.
Írjuk a lista végére 1-től n-ig a páratlan számokat növekvő sorrendben, de ha a maradék 8, akkor páronként cseréljük fel őket (például 3, 1, 7, 5, 11, 9, …).
Ha a maradék 2, akkor cseréljük ki az 1-et és 3-at, valamint tegyük az 5-öt a lista végére.
Ha a maradék 3 vagy 9, akkor tegyük az 1-et és 3-at a lista végére (ebben a sorrendben).
Végül tegyük le a bábukat a sakktáblára: az első sorba oda, ahova a lista első száma mutatja; a második sorba oda, ahová a lista második száma mutatja…
Megoldás php-ban:
<?
class Tabla
{
private $T = array( array() ) ;
private $UresCella ;
function __construct( $c )
{
$this->UresCella = $c ;
for( $i=0 ; $i<=7; $i++ )
{
for( $j=0 ; $j<=7; $j++ )
{
$this->T[$i][$j] = $this->UresCella ;
}
}
}
function Megjelenit()
{
for( $i=0 ; $i<=7; $i++ )
{
for( $j=0 ; $j<=7; $j++ )
{
print $this->T[$i][$j] ;
}
print "<br>" ;
}
print "<br>" ;
}
function Elhelyez( $db )
{
for( $i=0 ; $i<$db; $i++ )
{
do
{
$x = rand(0,7) ;
$y = rand(0,7) ;
}
while( $this->T[$x][$y] != $this->UresCella ) ;
$this->T[$x][$y] = "K" ;
}
}
function UresOszlop( $m )
{
$i = 0 ;
while( $i<=7 && $this->T[$i][$m]==$this->UresCella )
{
$i++ ;
}
return !($i<=7) ;
}
function UresOszlopokSzama()
{
$db=0 ;
for( $i=0 ; $i<=7; $i++ )
{
if( $this->UresOszlop($i) ) $db++ ;
}
return $db ;
}
function UresSor( $m )
{
$i = 0 ;
while( $i<=7 && $this->T[$m][$i]==$this->UresCella )
{
$i++ ;
}
return !($i<=7) ;
}
function UresSorokSzama()
{
$db=0 ;
for( $i=0 ; $i<=7; $i++ )
{
if( $this->UresSor($i) ) $db++ ;
}
return $db ;
}
function FajlbaIr()
{
$fp = fopen("tablak64.txt","a") ;
for( $i=0 ; $i<=7; $i++ )
{
for( $j=0 ; $j<=7; $j++ )
{
fwrite( $fp , $this->T[$i][$j] ) ;
}
fwrite( $fp , "\r\n" ) ;
}
fwrite( $fp , "\r\n" ) ;
fclose($fp) ;
}
}
$t = new Tabla(".") ;
print "4. feladat: az üres tábla:<br>" ;
$t->Megjelenit() ;
$t->Elhelyez(8) ;
print "6. feladat: a feltöltött tábla:<br>" ;
$t->Megjelenit() ;
print "9. feladat: Üres oszlopok és sorok száma:<br>" ;
print "Oszlopok: " . $t->UresOszlopokSzama() . "<br>" ;
print "Sorok: " . $t->UresSorokSzama() . "<br>" ;
$tt[] = array() ;
if( file_exists("tablak64.txt") ) unlink("tablak64.txt") ;
for( $x=1 ; $x<=64; $x++ )
{
$tt[$x] = new Tabla("*") ;
$tt[$x]->Elhelyez($x) ;
$tt[$x]->FajlbaIr() ;
}
print "<br>10. feladat:<br>" ;
print "<a href='tablak64.txt' target=_blank>tablak64.txt</a><br>" ;
?>
Nincsenek megjegyzések:
Megjegyzés küldése