Проблем осам дама

Из Википедије, слободне енциклопедије
a b c d e f g h
8
Chessboard480.svg
d8 white queen
g7 white queen
c6 white queen
h5 white queen
b4 white queen
e3 white queen
a2 white queen
f1 white queen
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Једно од 12 решења

Проблем осам дама је проблем постављања осам шаховских дама на 8×8 шаховску таблу тако да ниједна од њих не може узети ниједну другу од њих користећи стандардни потез даме у шаху. Боја дама је неважна за ову загонетку; претпоставка је да би свака дама могла напасти било коју другу. Према томе, решење захтева да две даме не деле исту врсту, колону ни дијагоналу. Ово је један пример општијег проблема n дама у коме треба поставити n дама на шаховску таблу димензија n×n.

Историја[уреди]

Проблем је оригинално поставио 1848. године играч шаха Макс Базел и, током година, многи математичари, укључујући Гауса бавили су се решавањем ове загонетке. Године 1874 Гинтер је предложио метод налажења решења користећи детерминанте, а Глаишер је побољшао тај приступ.

Ова загонетка се појавила у популарној компјутерској игрици 7-ми гост раних деведесетих година.

Конструкција једног решења[уреди]

Постоји једноставан поступак који даје једно решење проблема n дама за n = 1 или било које n ≥ 4:

  1. Поделите n са 12. Упамтите остатак (који је 8 за загонетку осам дама).
  2. Направите списак парних бројева од 2 до n по реду.
  3. Ако је остатак 3 или 9, преместите 2 на крај списка.
  4. Направите списак непарних бројева од 1 до n по реду, али ако је остатак 8, замените парове (тј. 3, 1, 7, 5, 11, 9, …).
  5. Ако је остатак 2, замените места бројевима 1 и 3, а затим преместите 5 на крај списка.
  6. Ако је остатак 3 или 9, преместите 1 и 3 на крај списка.
  7. Поставите краљицу из прве колоне у врсту са првим бројем са списка, краљицу из друге колоне у врсту са другим бројем са списка, итд.

У случају n = 8 ово даје горе приказано решење. Следи још неколико примера.

  • 14 дама (остатак 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
  • 15 дама (остатак 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
  • 20 дама (остатак 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.

Налажење броја свих решења[уреди]

Загонетка осам дама има 92 различита решења. Ако се решења која се разликују само за оператор симетрије (ротације и осне симетрије) табле броје као једно, загонетка има 12 јединствених решења. Следећа табела даје број решења за n дама, како јединствених (sequence A002562 in OEIS) тако и различитих (sequence A000170 in OEIS).

n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
јединствена: 1 0 0 1 2 1 6 12 46 92 341 1,787 9,233 45,752 285,053
различита: 1 0 0 2 10 4 40 92 352 724 2,680 14,200 73,712 365,596 2,279,184

Приметите интересантну чињеницу да загонетка 6 дама има мање решења него загонетка 5 дама!

Слични проблеми[уреди]

Кориштење фигура које нису даме
На пример, на табли 8×8 могу се поставити 32 скакача, или 14 ловаца, или 16 краљева, тако да се никоје две фигуре не нападају. Fairy шаховске фигуре су такође замењивале даме.
Нестандардне табле
Поља је проучавао проблем n дама на тороидалној ("облика унутрашње гуме") табли. Други облици, укључујући тродимензионалне табле, такође су проучавани.
Доминација
Ако је дата табла n×n, наћи доминациони број, што је најмањи број дама (или других фигура) потребних да нападну или заузму свако поље. За таблу 8×8, дамин доминациони број је 5.
Проблем девет дама
Поставите девет дама и једног пешака на таблу 8×8 на тај начин да даме не нападају једна другу. Даље уопштење проблема (решење тренутно није познато): ако је дата шаховска табла n×n и m > n дама, наћи најмањи број пешака такав да m дама и пешаци могу бити постављени на таблу на тај начин да се никоје две даме не нападају.
Проблем краљица и скакача
Поставите m дама и m скакача на таблу n са n тако да ниједна фигура не напада другу.
Магични квадрати
1992ге, Demirörs, Rafraf и Tanik објавили су метод за претварање неких магичних квадрата у решења n дама и обрнуто.
Латински квадрати
Шаховски проблеми