Puzzle de opt regine

	la	b	c	d	Și	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	la	b	c	d	Și	f	g	h

O posibilă soluție la problemă.

Puzzle-ul (sau problema) celor opt regine este o problemă care constă în găsirea modului de a poziționa opt femei (bucată de șah ) pe o tablă de șah de 8x8 astfel încât niciuna dintre ele să nu poată captura alta, folosind mișcări standard ale reginei. Prin urmare, o soluție va trebui să prevadă că nicio regină nu are o coloană, traversă sau diagonală în comun cu o altă regină. Problema opt regine este un exemplu de n mai general regine problemă, care constă în plasarea n regine pe n x n tablă de șah cu condițiile ilustrate mai sus; în această formă, în special, este adesea folosit pentru a ilustra tehnicile de proiectare și programare a algoritmilor . S-a demonstrat matematic că problema este rezolvabilă pentru n = 1 sau n ≥ 4, în timp ce nu este rezolvabilă pentru n = 2 și n = 3.

Istorie

Problema a fost propusă inițial în 1848 de șahistul Max Bezzel și, de-a lungul anilor, mulți matematicieni , inclusiv Gauss , care au reușit să găsească 72 din cele 92 de soluții, au lucrat asupra problemei și a formei sale generalizate. Prima soluție a fost dată de Franz Nauck în 1850. Nauck a fost cel care a extins problema la forma generalizată. În 1874, S. Günther a propus o metodă pentru a găsi soluția problemei folosind determinanții , metodă care a fost perfecționată ulterior de JWL Glaisher.

Edsger Dijkstra , în 1972, a folosit problema n reginelor pentru a ilustra puterea a ceea ce el a numit programare structurată . El a publicat o descriere foarte detaliată a dezvoltării unui algoritm DFS de backtracking .

Toate soluțiile

Cele 92 de soluții sunt reduse în esență la 12 care nu pot fi obținute una de la cealaltă prin rotații și reflexii :

la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 1	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 2	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 3	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 4
la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 5	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 6	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 7	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 8
la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 9	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 10	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 11	la b c d Și f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 la b c d Și f g h Soluție unică 12

Numărul de soluții

Tabelul următor arată numărul de soluții la problema n regine, atât unice ^{[1] cât} și distincte ^[2] , pentru n = 1-14, 24-27.

Rețineți că problema celor șase regine are mai puține soluții decât problema celor cinci regine.

Încă nu există o formulă pentru a calcula numărul exact de soluții.

Versiune animată a soluției recursive

Această animație folosește backtracking pentru a rezolva problema. O regină este plasată într-o coloană fără conflict. Dacă coloana nu este găsită, programul revine la ultima stare pozitivă și se încearcă o altă coloană.

Notă

Bibliografie

• 8 regine pe o tablă de șah (abordare IT), în Micro & Personal Computer , n. 7, Roma, Sound Publishing Group, octombrie / noiembrie 1980, pp. 64-69,OCLC 859585120 .
• ( EN ) Jordan Bell și Brett Stevens, O anchetă a rezultatelor cunoscute și a domeniilor de cercetare pentru n-regine , Matematică discretă , Vol. 309, numărul 1, ianuarie 2009, 1-31.
• (EN) John Watkins, Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press, 2004. ISBN 0-691-11503-6 .
• ( EN ) Ole-Johan Dahl , EW Dijkstra , CAR Hoare Structured Programming , Academic Press, Londra, 1972. ISBN 0-12-200550-3 .
• (EN) L.Allison, CNYee și M. McGaughey, Three Dimensional NxN-Queens Problems , Departamentul de Informatică, Universitatea Monash, Australia, 1988.
• ( EN ) S. Nudelman, The Modular N-Queens Problem in Higher Dimensions , Discrete Mathematics, vol 146, iss. 1-3, 15 noiembrie 1995, pp. 159–167.
• ( EN ) Ricardo Gomez, Juan Jose Montellano și Ricardo Strausz, Despre problema modulară a reginei N în dimensiuni superioare , Instituto de Matematicas, Area de Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexic, 2004.
• ( EN ) J. Barr și S. Rao, The n-Queens Problem in Higher Dimensions , Elemente der Mathematik, vol. 61 (2006), pp. 133–137.

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere pe puzzle - ul celor opt regine

linkuri externe

• ( RO ) Articol pe MathWorld , pe mathworld.wolfram.com .
• (EN) soluții , pe bridges.canterbury.ac.nz. Adus la 22 martie 2006 (arhivat din original la 1 ianuarie 2011) .
• ( RO ) Pagina despre problema N Queens , pe liacs.nl . Adus la 22 martie 2006 (arhivat din original la 14 octombrie 2006) .
• Pagina despre problema N Queens , la durangobill.com . Adus la 22 martie 2006 (arhivat din original la 5 ianuarie 2011) .
• Versiunea DOS / Windows redată , pe sblendorio.eu .
• Versiunea CP / M redabilă , pe github.com .
• Opt Queens Brain Teaser: Joc iPhone gratuit , pe itunes.apple.com .

Algoritmi și programe de soluții

• Soluție în Atari BASIC , pe atarimagazines.com .
• Metoda generală n regine cu implementare în java
• Soluție cu algoritmi genetici , pe dosar-andreas.net .
• Soluție Haskell / Java , pe scdi.org . Adus la 22 martie 2006 (arhivat din original la 30 aprilie 2006) .
• Soluție Java , la math.utah.edu .
• Soluție standard ML , pe dcs.ed.ac.uk.
• Soluție LISP , pe obereed.net .
• Soluția C (normală și, de asemenea, cu calcul paralel cu MPI) ^{[ link rupt ]} , la parallelknoppix.info .

Portalul de matematică

Portalul șahului