Domináns királynők problémája

A Wikipédiából, a szabad enciklopédiából

Adott egy n×n-es sakktábla (ahol n pozitív egész). Szeretnénk úgy királynőket elhelyezni a táblán, hogy bárhova is tennénk új bábut, az már valamelyik korábbi királynő által ütésben legyen. Keressük a királynők minimális számát.

Megoldás[szerkesztés | forrásszöveg szerkesztése]

A probléma az alkalmazott diszkrét matematika témakörébe tartozik. Egyelőre nincs egzakt eredmény, amellyel tetszőleges n értékére kiszámítható lenne a szükséges királynők száma. A királynők minimális számára azonban már született felső becslés. Kis n értékekre számítógéppel kipróbálható valamennyi szóba jöhető állás, és így megkapható a kérdéses szám.

Az alábbi táblázat mutatja a különböző méretű sakktáblákhoz tartozó domináns királynők számát:

A tábla mérete Domináns királynők
1×1 1
2×2 1
3×3 1
4×4 3
5×5 3
6×6 4
7×7 4
8×8 5
9×9 5
10×10 5
11×11 5
12×12 7
13×13 7
14×14 8
15×15 9
16×16 9
17×17 9
18×18 10

Egy példa n=8 esetre[szerkesztés | forrásszöveg szerkesztése]

Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg


További információk[szerkesztés | forrásszöveg szerkesztése]

Lásd még[szerkesztés | forrásszöveg szerkesztése]