Domináns királynők problémája
gráfelméleti fogalom
Adott egy n×n-es sakktábla (ahol n pozitív egész). Szeretnénk úgy királynőket (vezéreket) 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ésA 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 (A075458 sorozat az OEIS-ben):
| A tábla mérete | Domináns királynők |
|---|---|
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 1 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
| 8×8 | 5 |
| 9×9 | 5 |
| 10×10 | 5 |
| 11×11 | 5 |
| 12×12 | 6 |
| 13×13 | 7 |
| 14×14 | 8 |
| 15×15 | 9 |
| 16×16 | 9 |
| 17×17 | 9 |
| 18×18 | 9 |
Egy példa n=8 esetre
szerkesztés
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 8x8-as táblán 5 vezér (királynő) lefedi az összes mezőt | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
