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.
<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>
<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 " ";
}
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>