http://gorbem.hu/PHP.php

Nyolc vezér

 

Helyezzünk el a sakktáblán nyolc vezért úgy, hogy ne üssék egymást. Ez azt jelenti (ismerve a vezér képességeit), hogy egyetlen sorban és egyetlen oszlopban sem helyezkedhet el két vezér, sőt egyetlen átló mentén sem (átlóba beleértve a két főátlóval párhuzamos bármely mezősort). Egy helyes elrendezést a következő screenshot mutat:

 

 

A vezérek elhelyezkedését a $tomb nevű egydimenziós tömbben tároljuk, ahol a tömbindex az oszlopindexet, a tömb értéke pedig a sorindexet jelenti. A kezdő állapotban a vezérek mindegyike a főátlóban helyezkedik el, biztosítva azt, hogy sem oszlop, sem sor szerint nincs ütközés.

 

 

Ha ezek után két oszlopban lévő vezéreket úgy cserélünk fel, hogy a sorindexek ne változzanak (azaz a két tömbelemet felcseréljük), akkor sor és oszlop szerinti ütközés nem jön létre, csak az átlók szerinti ütközés változik. A programba, ezt kihasználva, az ütközésmentesítő algoritmus van beépítve.

 

A vezérek képernyőn (sakktáblán) való megjelenítésére, cseréjére és az ütközési szám meghatározására függvényeket írtunk. A rendezés az Rendezés/Újra feliratú gomb megnyomásra indul, melyben először alapértelmezés szerinti átlóban elhelyezzük a vezéreket, majd 1000-szer véletlen cseréket hajtunk végre. Ezek után ütközésmentesítéssel addig rendezzük, amíg az ütközési szám nulla nem lesz, végül a helyes elhelyezést megjelenítjük.

 

http://gorbem.hu/PH/Vezer.php

 

<html>

<head>

<title>Nyolc vezér</title>

</head>

<body>

<form name="" action="Vezer.htm" method="POST">

<input type="submit" name="vissza" value="Vissza" />

</form>

 

<center>

<form name="" action="Vezer.php" method="POST">

<h1><u>Nyolc vezér</u> &nbsp;

<input type="submit" name="ujra" value="Rendez/Újra" />

</h1>

</form>

<?php

function csere($tomb,$s1,$s2){

            $p = $tomb[$s1];

            $tomb[$s1] = $tomb[$s2];

            $tomb[$s2] = $p;

            return $tomb;

}

function utkozes($tomb){

            $utkoz = 0;

            for ($i=0; $i<7; $i++){

                  for ($j=$i+1; $j<8; $j++){

                        if ( abs($tomb[$i]-$tomb[$j]) == $j-$i ){

                             $utkoz++;

                        }

                  }

            }

            return $utkoz;

}

function kepre($tomb){

            print "<table border=\"1\" cellpadding=\"5\" cellspacing=\"0\" >\n";

            for ($i=0; $i<8; $i++){

                  print "<tr>\n";

                  for ($j=0; $j<8; $j++){

                        if ( ($i+$j)%2 == 1 ){

                             print "\t<td align=\"center\" bgcolor=\"#888888\" width=\"38px\"><font size=\"6\">";

                  }

                        else{

                             print "\t<td align=\"center\"><font size=\"6\">";

                        }

                        if ($tomb[$i] == $j){

                        print "V";

                        }

                        else{

                             print "&nbsp;";

                        }

                        print "</font>";

                        print "</td>\n";

                  }

                  print "</tr>\n";

            }

            print "</table>\n";

            return true;

}

           

            if ( isset($_POST['ujra']) ){

                  $tomb = array();

                  //tömbfeltöltés

                  for ($i=0; $i<8; $i++){

                        $tomb[$i] = $i;

                  }

                  //keverés

                  for ($i= 0; $i<1000; $i++){

                        $s1 = rand(0,7);

                        $s2 = rand(0,7);

                        $tomb = csere($tomb,$s1,$s2);

                  }

                  //rendezés ütközésmentesítéssel

                  $ut = utkozes($tomb);

                  while ($ut !== 0){

                        $s1 = rand(0,7);

                        $s2 = rand(0,7);

                        $el = utkozes($tomb);

                        $tomb = csere($tomb,$s1,$s2);

                        $ut = utkozes($tomb);

                        if ($ut>$el){

                             $tomb = csere($tomb,$s1,$s2);

                             $ut = utkozes($tomb);

                        }

                  }

                  kepre($tomb);

            }

            if ( !isset($_POST['ujra']) ){

                  $tomb = array();

                  //tömbfeltöltés

                  for ($i=0; $i<8; $i++){

                        $tomb[$i] = $i;

                  }

                  kepre($tomb);

            }

?>

</center>

</body>

</html>