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

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

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Једно од 12 решења

Историја

Проблем је оригинално поставио 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 дама, како јединствених (секвенца A002562 у ) тако и различитих (секвенца A000170 у ).

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 дама и обрнуто.

Латински квадрати

Шаховски проблеми