Utolsó módosítás: 2009. április 30.
Helyezzünk el egy 7-szer 7-es sakktáblán négy vezért úgy, hogy minden mezőn vagy álljon egy vezér, vagy valamelyik vezér támadja.
Először írjunk egy függvényt, ami kiszámítja, hogy melyik mezőket támad egy vezér, beleértve most azt a mezőt is, amin a vezér áll. Teszteljük ezt a függvényt úgy, hogy kirajzoljuk ezeket a mezőket egy vezérre.
A sakktábla 49 mezőjét jelöljük 0-tól 48-ig terjedő számokkal, ekkor az s indexű sor o indexű mezője 8 * s + o, másrészt az m indexű mező az m / 8 indexű sorban és az m % 8 indexű oszlopban van.
Íme a kód: hcg0.rb.
def tamad(k, m) ks = k / 7 ko = k % 7 ms = m / 7 mo = m % 7 ks == ms || ko == mo || ks - ms == ko - mo || ks - ms == mo - ko end k = 7 * 2 + 3 (0...7).each {|x| (0...7).each {|y| if tamad(k, 7 * x + y) print "O" else print "." end } print "\n" }
Kimenet:
.O.O.O. ..OOO.. OOOOOOO ..OOO.. .O.O.O. O..O..O ...O...
Most akkor menjünk végig az összes lehetséges kombináción, ahogy négy vezért le lehet rakni a táblára, mindegyikről ellenőrizzük, jó-e, és írjuk ki a jókat.
Vegyük észre, hogy minden kombinációt csak egy sorrendben nézünk meg, nem mind a 24 sorrendben, ez jelentősen gyorsítja a program futását. (Nem törődünk azonban a sakktábla szimmetriájával, így egy megoldás tükrözött változatait akár nyolcszor is megvizsgálhattuk és kiírhattuk.
Letöltés: hcg1.rb.
def tamad(k, m) ks = k / 7 ko = k % 7 ms = m / 7 mo = m % 7 ks == ms || ko == mo || ks - ms == ko - mo || ks - ms == mo - ko end def kirajzol(k0, k1, k2, k3) (0...7).each {|x| (0...7).each {|y| k = 7 * x + y if k0 == k || k1 == k || k2 == k || k3 == k print "O" else print "." end } print "\n" } print "\n" end def ellenoriz(k0, k1, k2, k3) jo = true (0 ... 49).each {|m| if !(tamad(k0, m) || tamad(k1, m) || \ tamad(k2, m) || tamad(k3, m)) jo = false end } if jo kirajzol(k0, k1, k2, k3) end end (0 ... 49).each {|k0| (0 ... k0).each {|k1| (0 ... k1).each {|k2| (0 ... k2).each {|k3| ellenoriz(k0, k1, k2, k3) } } } }
És a kimenet eleje:
....... ....... ....... O..OOO. ....... ....... ....... ....... ....... ....... .OOO..O ....... ....... ....... ....O.. .....O. ......O ....... .O..... ....... .......
A teljes program úgy egy perc alatt fut le, az utolsó megoldás, amit talál, az alábbi.
....... ...O... ....... .O..... ....... .....O. ......O