Problema celor opt regine
Problema celor opt regine cere opt regine pe o tablă de șah, fără ca două dintre ele să se atace. Compozitorul de șah Max Bezzel a publicat-o în 1848, iar ea a devenit primul exemplu clasic de căutare cu backtracking.
Un puzzle de șah din 1848
Max Bezzel, un compozitor german de șah, a propus problema într-o revistă de șah din Berlin în 1848. Franz Nauck a publicat toate cele 92 de soluții în 1850 și a pus aceeași întrebare pentru table mai mari. Carl Friedrich Gauss a urmărit problema cu interes și a discutat-o în scrisorile sale.
O regină pe fiecare linie și coloană
Opt regine care nu se atacă trebuie să stea pe opt linii diferite și pe opt coloane diferite. Deci o soluție este o amestecare a numerelor de la 1 la 8, o permutare, cu o regulă în plus: două regine nu pot fi pe aceeași diagonală. Din cele 40.320 de permutări, doar 92 trec.
Backtracking
Backtrackingul construiește o soluție bucată cu bucată și se întoarce în momentul în care ajunge într-o fundătură. Pentru regine: pune o regină pe primul pătrat sigur de pe linia următoare, iar când o linie nu are niciun pătrat sigur, întoarce-te la linia de deasupra și mută acea regină mai departe. În 1972, Edsger Dijkstra a folosit problema ca să explice programarea structurată exact cu această căutare.
Simetria
Rotește tabla cu un sfert de tură sau oglindește-o, iar o soluție rămâne soluție. Asta dă până la opt versiuni ale fiecăreia. Cele 92 de soluții se împart în 12 astfel de familii: unsprezece cu câte 8 membri și una cu doar 4, pentru că acea soluție arată la fel după o jumătate de tură.
Problema celor n regine
Pe o tablă n×n, întrebarea este aceeași, cu n regine. Există soluții pentru orice n de la 4 în sus, iar numărul lor crește repede: 2 pentru 4×4, 92 pentru 8×8 și 14.200 pentru 12×12. Nu se cunoaște nicio formulă pentru acest număr; valorile record provin din căutări mari pe calculator.
Încearcă în PictorX
Deschide Opt regine și dă clic pe un pătrat ca să așezi o regină; dă clic din nou ca s-o iei de pe tablă. Arată atacurile marchează cu un punct pătratele atacate de reginele tale, iar reginele roșii se atacă între ele. Rezolvă rulează căutarea cu backtracking pas cu pas și păstrează reginele pe care le-ai așezat. Soluția următoare parcurge toate soluțiile în ordine, iar Dimensiune schimbă tabla de la 4×4 la 12×12.
Întrebări frecvente
Cine a inventat problema celor opt regine?
Max Bezzel, un compozitor german de șah, în 1848. Franz Nauck a publicat primul set complet de soluții în 1850.
Câte soluții există?
92 pe tabla standard. Dacă rotațiile și reflexiile contează ca una singură, sunt 12.
De ce are tabla de 6×6 atât de puține soluții?
Are doar 4, toate din aceeași familie. Tabla mai mică de 5×5 are 10. Tablele mai mari au tot mai multe: 40 pe 7×7 și 92 pe 8×8.
PictorX încarcă ceva?
Nu. Tabla este desenată pe o pânză în browser. Salvează descarcă un PNG, iar Editează deschide imaginea în editorul PictorX.
Unelte conexe
Opt regine
Așază opt regine pe o tablă de șah astfel încât niciuna să nu atace alta. Încearcă singur, urmărește cum căutarea cu backtracking găsește o soluție pas cu pas și parcurge toate cele 92 de soluții.
Turul calului
Fă un cal de șah să sară pe fiecare câmp al tablei exact o dată. Joacă singur cu indiciile lui Warnsdorff sau urmărește cum Rezolvă termină un tur deschis sau închis. Salvează drumul ca PNG.
Turul calului
Istoria și matematica turului calului: Euler și Warnsdorff, tururi deschise și închise, de ce tablele impare nu au tur închis și cum găsește un calculator unul.
Turnurile din Hanoi
Mută un turn de discuri pe trei tije, în browser. Câte un disc, niciodată unul mai mare pe unul mai mic. Cea mai scurtă soluție are 2ⁿ − 1 mutări.
Turnurile din Hanoi
Turnurile din Hanoi: trei tije, câte un disc și niciodată unul mai mare pe unul mai mic. Cea mai scurtă soluție are 2ⁿ−1 mutări. Édouard Lucas a prezentat puzzle-ul în 1883.
Furnica lui Langton
Rulează furnica lui Langton în browser. Urmărește simetria, haosul și autostrada de 104 pași, apoi încearcă reguli multicolore, mai multe furnici, o grilă hexagonală și turmite.
Eşti gata să încerci?
Deschide PictorX în browser-ul tău
Încearcă Opt regine