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

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

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

Külső hivatkozások

• http://www.research.att.com/~njas/sequences/A075324 - domináns királynők problémája az OEIS weblapján

Lásd még

• Diszkrét matematika
• Nyolckirálynő-probléma