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

Из Википедије, слободне енциклопедије


Chess zhor 26.png
Chess zver 26.png
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.png
Chess zhor 26.png
Једно од 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 дама, како јединствених Шаблон:OEIS тако и различитих Шаблон: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 дама и обрнуто.
Латински квадрати
Шаховски проблеми