Problem osam dama

Problem osam dama je problem postavljanja osam šahovskih dama na 8×8 šahovsku tablu tako da nijedna od njih ne može uzeti nijednu drugu od njih koristeći standardni potez dame u šahu. Boja dama je nevažna za ovu zagonetku; pretpostavka je da bi svaka dama mogla napasti bilo koju drugu. Prema tome, rešenje zahteva da dve dame ne dele istu vrstu, kolonu ni dijagonalu. Ovo je jedan primer opštijeg problema n dama u kome treba postaviti n dama na šahovsku tablu dimenzija 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

Jedno od 12 rešenja

Istorija

Problem je originalno postavio 1848. godine igrač šaha Maks Bazel i, tokom godina, mnogi matematičari, uključujući Gausa bavili su se rešavanjem ove zagonetke. Godine 1874 Ginter je predložio metod nalaženja rešenja koristeći determinante, a Glaišer je poboljšao taj pristup.

Ova zagonetka se pojavila u popularnoj kompjuterskoj igrici 7-mi gost ranih devedesetih godina.

Konstrukcija jednog rešenja

Postoji jednostavan postupak koji daje jedno rešenje problema n dama za n = 1 ili bilo koje n ≥ 4:

1. Podelite n sa 12. Upamtite ostatak (koji je 8 za zagonetku osam dama).
2. Napravite spisak parnih brojeva od 2 do n po redu.
3. Ako je ostatak 3 ili 9, premestite 2 na kraj spiska.
4. Napravite spisak neparnih brojeva od 1 do n po redu, ali ako je ostatak 8, zamenite parove (tj. 3, 1, 7, 5, 11, 9, …).
5. Ako je ostatak 2, zamenite mesta brojevima 1 i 3, a zatim premestite 5 na kraj spiska.
6. Ako je ostatak 3 ili 9, premestite 1 i 3 na kraj spiska.
7. Postavite kraljicu iz prve kolone u vrstu sa prvim brojem sa spiska, kraljicu iz druge kolone u vrstu sa drugim brojem sa spiska, itd.

U slučaju n = 8 ovo daje gore prikazano rešenje. Sledi još nekoliko primera.

• 14 dama (ostatak 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
• 15 dama (ostatak 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
• 20 dama (ostatak 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.

Nalaženje broja svih rešenja

Zagonetka osam dama ima 92 različita rešenja. Ako se rešenja koja se razlikuju samo za operator simetrije (rotacije i osne simetrije) table broje kao jedno, zagonetka ima 12 jedinstvenih rešenja. Sledeća tabela daje broj rešenja za n dama, kako jedinstvenih (sekvenca A002562 u OEIS) tako i različitih (sekvenca A000170 u OEIS).

n:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
jedinstvena:	1	0	0	1	2	1	6	12	46	92	341	1,787	9,233	45,752	285,053
različita:	1	0	0	2	10	4	40	92	352	724	2,680	14,200	73,712	365,596	2,279,184

Primetite interesantnu činjenicu da zagonetka 6 dama ima manje rešenja nego zagonetka 5 dama!

Slični problemi

Korištenje figura koje nisu dame

Na primer, na tabli 8×8 mogu se postaviti 32 skakača, ili 14 lovaca, ili 16 kraljeva, tako da se nikoje dve figure ne napadaju. Fairy šahovske figure su takođe zamenjivale dame.

Nestandardne table

Polja je proučavao problem n dama na toroidalnoj ("oblika unutrašnje gume") tabli. Drugi oblici, uključujući trodimenzionalne table, takođe su proučavani.

Dominacija

Ako je data tabla n×n, naći dominacioni broj, što je najmanji broj dama (ili drugih figura) potrebnih da napadnu ili zauzmu svako polje. Za tablu 8×8, damin dominacioni broj je 5.

Problem devet dama

Postavite devet dama i jednog pešaka na tablu 8×8 na taj način da dame ne napadaju jedna drugu. Dalje uopštenje problema (rešenje trenutno nije poznato): ako je data šahovska tabla n×n i m > n dama, naći najmanji broj pešaka takav da m dama i pešaci mogu biti postavljeni na tablu na taj način da se nikoje dve dame ne napadaju.

Problem kraljica i skakača

Postavite m dama i m skakača na tablu n sa n tako da nijedna figura ne napada drugu.

Magični kvadrati

1992ge, Demirörs, Rafraf i Tanik objavili su metod za pretvaranje nekih magičnih kvadrata u rešenja n dama i obrnuto.

Latinski kvadrati

Šahovski problemi