[MuchaZ]

Jakieś pomysły jak sprawdzić czy dana macierz dla partii szachów jest możliwa? Myślałem nad jakimś ograniczeniem sumy, ale przecież jeszcze trzeba sprawdzić możliwe ruchy... #matematyka #informatyka #zagadka #szachy

Macierz przed rozpoczęciem gry:

[p.....r]

@MuchaZ:
Na początek sprawdzenie czy zbiór pionków zawiera się w pełnym zbiorze pionków.
A poza tym.. to chyba każde ułożenie da się zrobić jeśli gracze będą robili bardzo głupie ruchy :)

[p.....r]

@MuchaZ

Algorytm to sprawdzający:
(nieoptymalny, a my nie o tym)

function sprawdzsume(pionek){
i=0;
foreach(macierz as element)
if(element==pionek)
i++;
return i;
}

//sprawdzenie pionków czarnych:
if(sprawdzsume(-1))>8 return błąd;

//sprawdzenie pionków białych:
if(sprawdzsume(1))>8 return błąd;

//sprawdzenie wież białych:
if(sprawdzsume(-4))>2 return błąd;

...

[Rincewind]

//sprawdzenie wież białych:

if(sprawdz_sume(-4))>2 return błąd;

@poobanter: Ejej, a co z promocją pionów? Każdego piona można promować na dowolną figurę, więc w szczególnym przypadku może być po 10 skoczków, gońców lub wież, albo 9 hetmanów. Tylko wtedy oczywiście brak pionów.

Albo 5 skoczków, 5 hetmanów i pion.

To nie takie trywialne.

[Rincewind]

@MuchaZ: Tak formalnie to trzeba by było sprawdzić, czy istnieje seria możliwych ruchów prowadząca do danego układu macierzy, ale to problem NP. Z takich prostych checków to na pewno żaden biały pion nie może znaleźć się w rzędzie 1, ani żaden czarny pion w rzędzie 8. To jest pewnik.

edit   Ponadto:
[1] Suma wszystkich figur i pionów (poza królem) nie może być większa od 15 dla każdej ze stron.
[2] Dla

[Rincewind]

@MuchaZ: Dodatkowo jeśli masz wskaźnik czyj jest teraz ruch, to w takim momencie przeciwnik nie może stać pod szachem. Ale to jest dość subtelne, bo to samo może oznaczać zakończenie partii. Z tym bym uważał.

[MuchaZ]

@Rincewind: Dzięki za szczegółową analizę problemu. ;)

[Rincewind]

@MuchaZ: Jeszcze kilka bardziej wyrafinowanych sytuacji – będę pisał o sytuacji białych, ale druga strona jest symetryczna:
[1] Jeśli stoją oba piony na b2, d2, to „czarny” goniec (poruszający się po czarnych polach) może stać tylko na c1, ewentualnie może go nie być.
[2] Analogiczna sytuacja dla pionów e2, g2 i „białego” gońca.
[3] Jeśli wszystkie piony stoją w rzędzie 2, to w rzędach 3+ mogą znajdować się tylko skoczki.

Jak

[Rincewind]

@MuchaZ: OK, to już przekombinowane, ale wciąż prawdziwe: nie może istnieć więcej niż 9 gońców tego samego „koloru” – 10 gońców na polach takiego samego koloru nigdy się nie zdarzy.

Ach, no i żaden biały pion nie może stać w rzędzie 8 (obowiązkowa promocja), i vice versa – żaden czarny pion nie może stać w rzędzie 1.

[Ragnarokk]

@MuchaZ:
Te wymienione przypadki są jednak tylko podzbiorem pozycji niemożliwych. IMO algorytmicznie zadanie nierealizowalne, choć teoretycznie rozstrzygalne (bo szachy to gra skończona)