Vuit reines: diferència entre les revisions

4.737 bytes afegits ,  fa 1 any
Noves seccions: Generalitzacions i solucions
(Nova secció: Plantejament)
(Noves seccions: Generalitzacions i solucions)
L'[[algorisme]] comprova primer si <math>k=8</math>; si es dóna aquest cas vol dir que és un vector 8-prometedor, és a dir que compleix totes les restriccions és una solució vàlida.
Si <math>k<8</math> l'algorisme explora les extensions <math>(k+1)</math>-prometedores realitzant un cicle de 1 a 8 al qual es comprova si les reines col·locades es veuen les unes a les altres. Si no és el cas es realitza una recurrència en la qual s'incrementa <math>k</math> (es busca el <math>(k+1)</math>-prometedor) i s'afegeix una nova fila, columna i diagonals al conjunt de restriccions per la propera iteració.
 
== Generalització per ''n'' reines ==
El problema de les vuit reines es pot generalitzar per a <math>n</math> reines. El problema consisteix en col·locar <math>n</math> reines en un escaquer de <math>n \times n</math> de manera que cap d'elles sigui amenaçada.
 
: <div style="padding:8px 16px;margin-bottom:8px;display:inline-block;background:rgba(0,0,0,0.1);">Podeu consultar el nombre de solucions possibles totals per cada <math>n</math>, incloent translacions, simetries i rotacions, a l'[[OEIS]] [[oeis:A000170|A000170]]</div>
: <div style="padding:8px 16px;margin-bottom:8px;display:inline-block;background:rgba(0,0,0,0.1);">Podeu consultar el nombre de solucions úniques possibles per cada <math>n</math> a l'[[OEIS]] [[oeis:A002562|A002562]]</div>
 
== Solucions al problema de les vuit reines ==
El problema de les vuit reines té 92 solucions, de les quals 12 són '''essencialment diferents''', és a dir les 92 solucions existents es poden obtenir a partir de translacions, simetries i rotacions de les 12 solucions úniques, que es mostren a continuació:
 
{|
|-
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|ql|__|__|__|__|=
7 |__|__|__|__|__|__|ql|__|=
6 |__|__|ql|__|__|__|__|__|=
5 |__|__|__|__|__|__|__|ql|=
4 |__|ql|__|__|__|__|__|__|=
3 |__|__|__|__|ql|__|__|__|=
2 |ql|__|__|__|__|__|__|__|=
1 |__|__|__|__|__|ql|__|__|=
|Solució única 1
}}
 
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|__|ql|__|__|__|=
7 |__|ql|__|__|__|__|__|__|=
6 |__|__|__|ql|__|__|__|__|=
5 |__|__|__|__|__|__|ql|__|=
4 |__|__|ql|__|__|__|__|__|=
3 |__|__|__|__|__|__|__|ql|=
2 |__|__|__|__|__|ql|__|__|=
1 |ql|__|__|__|__|__|__|__|=
|Solució única 2
}}
 
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|ql|__|__|__|__|=
7 |__|ql|__|__|__|__|__|__|=
6 |__|__|__|__|__|__|ql|__|=
5 |__|__|ql|__|__|__|__|__|=
4 |__|__|__|__|__|ql|__|__|=
3 |__|__|__|__|__|__|__|ql|=
2 |__|__|__|__|ql|__|__|__|=
1 |ql|__|__|__|__|__|__|__|=
|Solució única 3
}}
 
|-
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|ql|__|__|__|__|=
7 |__|__|__|__|__|ql|__|__|=
6 |__|__|__|__|__|__|__|ql|=
5 |__|__|ql|__|__|__|__|__|=
4 |ql|__|__|__|__|__|__|__|=
3 |__|__|__|__|__|__|ql|__|=
2 |__|__|__|__|ql|__|__|__|=
1 |__|ql|__|__|__|__|__|__|=
|Solució única 4
}}
 
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|ql|__|__|__|__|__|=
7 |__|__|__|__|__|ql|__|__|=
6 |__|__|__|__|__|__|__|ql|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|__|ql|__|__|__|__|=
3 |__|__|__|__|__|__|ql|__|=
2 |__|__|__|__|ql|__|__|__|=
1 |__|ql|__|__|__|__|__|__|=
|Solució única 5
}}
 
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|__|ql|__|__|__|=
7 |__|__|ql|__|__|__|__|__|=
6 |__|__|__|__|__|__|__|ql|=
5 |__|__|__|ql|__|__|__|__|=
4 |__|__|__|__|__|__|ql|__|=
3 |ql|__|__|__|__|__|__|__|=
2 |__|__|__|__|__|ql|__|__|=
1 |__|ql|__|__|__|__|__|__|=
|Solució única 6
}}
 
|-
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|__|ql|__|__|__|=
7 |__|__|__|__|__|__|ql|__|=
6 |__|__|__|ql|__|__|__|__|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|ql|__|__|__|__|__|=
3 |__|__|__|__|__|__|__|ql|=
2 |__|__|__|__|__|ql|__|__|=
1 |__|ql|__|__|__|__|__|__|=
|Solució única 7
}}
 
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|ql|__|__|__|__|=
7 |ql|__|__|__|__|__|__|__|=
6 |__|__|__|__|ql|__|__|__|=
5 |__|__|__|__|__|__|__|ql|=
4 |__|__|__|__|__|ql|__|__|=
3 |__|__|ql|__|__|__|__|__|=
2 |__|__|__|__|__|__|ql|__|=
1 |__|ql|__|__|__|__|__|__|=
|Solució única 8
}}
 
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|ql|__|__|__|__|__|=
7 |__|__|__|__|__|ql|__|__|=
6 |__|__|__|ql|__|__|__|__|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|__|__|__|__|__|ql|=
3 |__|__|__|__|ql|__|__|__|=
2 |__|__|__|__|__|__|ql|__|=
1 |__|ql|__|__|__|__|__|__|=
|Solució única 9}}
 
|-
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|__|__|ql|__|__|=
7 |__|ql|__|__|__|__|__|__|=
6 |__|__|__|__|__|__|ql|__|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|__|ql|__|__|__|__|=
3 |__|__|__|__|__|__|__|ql|=
2 |__|__|__|__|ql|__|__|__|=
1 |__|__|ql|__|__|__|__|__|=
|Solució única 10
}}
 
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|ql|__|__|__|__|=
7 |__|__|__|__|__|__|ql|__|=
6 |ql|__|__|__|__|__|__|__|=
5 |__|__|__|__|__|__|__|ql|=
4 |__|__|__|__|ql|__|__|__|=
3 |__|ql|__|__|__|__|__|__|=
2 |__|__|__|__|__|ql|__|__|=
1 |__|__|ql|__|__|__|__|__|=
|Solució única 11
}}
 
|
{{Diagrama d'escacs|=
| tright
|
|=
 
8 |__|__|__|__|__|ql|__|__|=
7 |__|__|__|ql|__|__|__|__|=
6 |__|__|__|__|__|__|ql|__|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|__|__|__|__|__|ql|=
3 |__|ql|__|__|__|__|__|__|=
2 |__|__|__|__|ql|__|__|__|=
1 |__|__|ql|__|__|__|__|__|=
|Solució única 12}}
 
|}
 
== Referències ==
Usuari anònim