Am descoperit o întrebare interesantă pe Softpedia:
Să se găsească numărul total de aranjări invalide a pieselor pe tabla de șah
Ce înţelegem prin “aranjare invalidă”? O stare – o poziţionare a pieselor de şah care nu ar fi putut rezulta dintr-un joc care să fi urmat regulile. Câteva exemple care vin în minte sunt:
- cei doi regi poziţionaţi unul lângă altul
- o tură, regină sau un nebun în faţa pionilor proprii – fără ca vreun pion să fi fost mutat
- existenţa a doi nebuni de aceeaşi culoare (ignorând posibilitatea de promovare a pionilor pentru simplitate)
- existenţa a mai mult de 2 regine sau 4 ture (ignorând posibilitatea de promovare a pionilor, din nou)
- întreaga linie de pioni negri plasată pe un rând mai jos decât întreaga linie de pioni albi (negri pe C1-C8 în timp ce toţi cei albi sunt pe D1-D8)
Nu se cere generarea tuturor situaţiilor concrete, ci doar o estimare a complexităţii unui asemenea algoritm. Ballpark estimate, cel mai probabil. Eu unul recunosc că nu-mi dau seama cum s-ar putea face aşa ceva, da’ poate mai e cineva plictisit căruia i se pare interesantă problema :)
Nu-s complet sigur de chestie, da’ mă gândesc că s-ar putea să existe o soluție algebrică, una care de altfel ar fi destul de tare.
Complexitatea spațiului mutărilor valide posibile este, din câte știu, calculată și cunoscută. În mod similar pot fi calculate toate mutările posibile, valide sau invalide. De asemenea, având în vedere că șahul are consistența sa, s-ar putea să existe o relație de ortogonalitate între spațiul mutărilor valide și cel al mutărilor invalide (sau cel în care s-a ajuns la o mutare invalidă), deci din cele două complexități cunoscute s-ar putea găsi o relație care să dea complexitatea mutărilor invalide.
Altfel, cu backtracking și nici chiar cu căutări mai inteligente nu cred că merge.
Complexitatea setului complet de partide posibile este cunoscuta, dar este prea mare pentru a efectua calculul efectiv. Conform lui Claude Shannon ea este de 10^123 – era linkul pe topicul citat.
Păi ideea unei soluții algebrice e tocmai să nu găsești o formulă muncitorească (găsită prin căutări în spațiul mutărilor), ci una care să se folosească de proprietățile jocului de șah și din care să poți deriva implicit și stările interzise.