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
@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 :)
@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.
@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]
@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: 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.
@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.
@MuchaZ: Te wymienione przypadki są jednak tylko podzbiorem pozycji niemożliwych. IMO algorytmicznie zadanie nierealizowalne, choć teoretycznie rozstrzygalne (bo szachy to gra skończona)
Macierz przed rozpoczęciem gry:
źródło: comment_CujoeYNNzjdTNXDQT2EDTeXkJdxfsJDi.jpg
PobierzNa 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 :)
Algorytm to sprawdzający:
(nieoptymalny, a my nie o tym)
function
@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
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]
[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.
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.
Te wymienione przypadki są jednak tylko podzbiorem pozycji niemożliwych. IMO algorytmicznie zadanie nierealizowalne, choć teoretycznie rozstrzygalne (bo szachy to gra skończona)