Witam. Mam taki problem. Jest taka gra:
*
* *
* * *
0
0
Przepraszam, wcisnalem publikuj zamiast podglad.
Mianowicie jest taka gra, ze jest 15 pol ulozonych w piramidke jak wyzej i jest 14 pionkow. Tionki ustawia sie na planszy tak zeby zostalo jedno puste pole. I gra polega na tym, zeby metoda zbijania przestakiwac pionki, a te przeskoczone usuwac. np:
-
- o ---> o o * - pionek 1 przeskoczyl drugi i znalazl sie na 3 pustym polu. Pionek przeskoczony jest usuwany.
I teraz mozna zbijac w 3 liniach. Poziomo, po prawym ukosie i po lewym ukosie. I teraz Caly problem polega na tym zeby zbijac tak aby zostalo jak najmniej pionkow na koncu gry. Najlepszym rozwiazaniem jest pozostawienie 1 pionka.
I teraz jak napisac program, jaki bedzie jego algorytm, aby rozpisal wszystkie mozliwe kombinacje gry i zeby mozna bylo znaleŹĆ wszystkie te ktore maja 1 pionek na koncu gry.
0
Możliwości jest tak niewiele, że metodą siłową powinno zadziałać bezproblemowo.
Czyli zwykła rekurencja, w której metoda zwracana liczbę pozostałych pionków przy danym ruchu i minimalizująca wynik:
coś w stylu:
int nastepnyRuch()
{
int minimumKoncowychPionkow=liczbaPozostałychPionkow();
for(kolejne pionki)
for(kolejne ruchy dla tego pionka)
{
WykonajRuch(tenRuch);
minimumKoncowychPionkow = min(minimumKoncowychPionkow, nastepnyRuch());
CofnijRuch(tenRuch);
}
return minimumKoncowychPionkow;
}
0
Chyba nie za bardzo rozumiem (przepraszam od niedawna programuje), chodzi o to zeby mozna bylo znaleŹĆ kombinacje ruchow jaka nalezy wykonac, aby zostal jeden pionek na koncu. Zeby jakos zapisac ruchy jakie trzeba wykonac.
0
Ten pseudo kod, który ci podałem wystarczy by to zrobić. Rozpisując nieco dokładniej:
int nastepnyRuch()
{
int minimumKoncowychPionkow=liczbaPozostałychPionkow();
for(kolejne pionki)
for(kolejne ruchy dla tego pionka)
{
WykonajRuch(tenRuch);
int minimumDlaTegoRuchu = nastepnyRuch();
if( minimumKoncowychPionkow > minimumDlaTegoRuchu )
{
zapamietajRuchJakoNajbardziejOptymalny(tenRuch);
minimumKoncowychPionkow = minimumDlaTegoRuchu;
}
CofnijRuch(tenRuch);
if( minimumKoncowychPionkow == 1)
break; // nie ma po co szukać dalej
}
return minimumKoncowychPionkow;
}
Swoją drogą, jeśli nie rozumiesz co mam na myśli, to może wziąłeś problem, który w tej chwili wykracza poza twoje możliwości.
Przyjrzyj się dokładnie, ten kod (nie jest optymalny) przeszukuje wszystkie możliwe ruchy i wybiera ten ciąg ruchów, który daje najlepszy rezultat.
0
Aha, chyba mniej wiecej rozumiem, ale mam kilka watpliwosci i niejasnosci.
Mianowicie jak zaimplementowac w petli for przechodzenie przez kolejne ruchy dla danego pionka i w ogóle poruszanie sie po calej planszy. Ja myslalem o jakiejs globalnej tablicy 15 zmiennych bool w ktorej true oznaczaloby ze jest pionek na polu, a false ze go nie ma. Nie wiem czy to dobry pomysl.
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
i teraz przeszukiwanie dozwolonych ruchow jako serie if-ow. Najpierw rozpisac to na trzy typy linni - poziome, prawo ukosne i lewo ukosne:
4 5 6
7 8 9 10
11 12 13 14 15
6 9 13
3 5 8 12
1 2 4 7 11
4 8 13
2 5 9 14
1 3 6 10 15
i teraz ifami:
if (p4 && p5 && !p6)
{
p4 = !p4;
p5 = !p5;
p6 = !p6;
}
itd. Nie wiem czy to troche nie zagmastwane..
0
wygląda na to, że idziesz dobrym tropem niestety napisałeś to w taki sposób, że trudno mieć pewność czy jest w 100% dobrze, za dużo skrótów myślowych.
0
Aha. Jesli cos nie jasne moge wytlumaczyc. Ale teraz mi sie wydaje ze ppomusl z seria ifow nie jest dobry bo program nigdy nie przeszuka wszystkich rozwiazan tylko te ktore beda najblizej wyszczegolnione w ifach..
0
Wiec napisalem taka funkcje ale ona jakos dziwnie sie zachowuje, nie wiem do konca czemu. Ale najpierw dam jej kod:
int nastepnyRuch()
{
using std::cout;
int liczbaPionkowNaPlanszy = liczbaPozostalychPionkow();
static int poziom;
cout << poziom << std::endl;
poziom++;
for (int i = 1; i <= 36; i++)
{
if (!wykonajRuch(i))
continue;
if (nastepnyRuch() == 1)
{
zapiszRuch(i);
liczbaPionkowNaPlanszy = 1;
}
cofnijRuch(i);
}
poziom--;
cout << poziom << std::endl;
return liczbaPionkowNaPlanszy;
}
Opisze o co chodzi. Na poczatku funkcja pobiera od funkcji liczbaPozostalychPionkow() liczbe pionkow jaka jest na planszy. Dalej ten kod z poziomami to diagnostyka tylko i wylacznie. Dalej mamy petle for w ktorej przechodzi ona przez 36 - wszystkie mozliwe ruchy jakie mozna wykonac w grze. Funckja bool wykonajRuch(int n) zwraca true jesli dalo sie wykonac ruch. Jesli sie nie dalo mamy warunek w if ktory jest spelniony kiedy nie mamy ruchu do wykonania. Wtedy nie trzeba nic robic i mamy dlatego continue ktore przechodzi do sprawdzania nastepnego ruchu. Dalej jesli w nastepnym ruchu liczba pionkow jest 1 to zapisuje ruch a liczbe pionkow zmienia na 1 dla zwrocenia poprzedniemu wywolaniu. dalej cofamy wykonany ruch aby moc sprawdzic nastepne mozliwosci manewru.
Z ta funkcja jest cos nie tak. Dla maksymalnego obciazenia (14 z 15 pionkow ustawione na planszy) wyskakuje Stack Overflow co jest dziwne bo funkcja nie powinna sie az tyle razy wywolywac. Ale jak sprawdzilem za pomoca zmiennej poziom wywoluje sie w pewnym momencie dla 14 pionkow niemalze w nieskonczonosc, nie wiem czemu. Dla mniejszego obciazenia daje sie uruchomic, zwraca wlasciwa kolejnosc (tzn w odwrotnej kolejnosci ale to jest do poprawienia kiedys) ale procz tego zwraca jakies cos dziwnego. Prosze o jakies wskazowki. Dla pelnego obrazu moge dac pelny kod:
// _v0.5_piramida.cpp -- program znajdujacy wszystkie rozwiazania gry logicznej i wypisujacy je na ekranie
#include <iostream>
int nastepnyRuch();
int liczbaPozostalychPionkow();
bool wykonajRuch(int n);
void zapiszRuch(int n);
void cofnijRuch(int n);
bool p[15] = { false, false, false, false, false, false, false, false, false, false, false, false, false, false, false };
int main()
{
using std::cout;
using std::cin;
using std::endl;
cout << " 0" << endl;
cout << " 1 2" << endl;
cout << " 3 4 5" << endl;
cout << " 6 7 8 9" << endl;
cout << "10 11 12 13 14" << endl;
// cout << "Wybierz pole puste (0-14): ";
// int pole;
// cin >> pole;
// p[pole] = false;
p[1] = p[2] = p[4] = p[11] = p[6] = p[7] = p[8] = true;
nastepnyRuch();
return 0;
}
int nastepnyRuch()
{
using std::cout;
int liczbaPionkowNaPlanszy = liczbaPozostalychPionkow();
static int poziom;
cout << poziom << std::endl;
poziom++;
for (int i = 1; i <= 36; i++)
{
if (!wykonajRuch(i))
continue;
if (nastepnyRuch() == 1)
{
zapiszRuch(i);
liczbaPionkowNaPlanszy = 1;
}
cofnijRuch(i);
}
poziom--;
cout << poziom << std::endl;
return liczbaPionkowNaPlanszy;
}
int liczbaPozostalychPionkow()
{
int licznik = 0;
for (int i = 0; i < 15; i++)
if (p[i])
licznik++;
return licznik;
}
bool wykonajRuch(int n)
{
switch(n)
{
case 1: if (p[3] && p[4] && !p[5])
{
p[3] = !p[3];
p[4] = !p[4];
p[5] = !p[5];
return true;
}
break;
case 2: if (p[5] && p[4] && !p[3])
{
p[5] = !p[5];
p[4] = !p[4];
p[3] = !p[3];
return true;
}
break;
case 3: if (p[6] && p[7] && !p[8])
{
p[6] = !p[6];
p[7] = !p[7];
p[8] = !p[8];
return true;
}
break;
case 4: if (p[7] && p[8] && !p[9])
{
p[7] = !p[7];
p[8] = !p[8];
p[9] = !p[9];
return true;
}
break;
case 5: if (p[9] && p[8] && !p[7])
{
p[9] = !p[9];
p[8] = !p[8];
p[7] = !p[7];
return true;
}
break;
case 6: if (p[8] && p[7] && !p[6])
{
p[8] = !p[8];
p[7] = !p[7];
p[6] = !p[6];
return true;
}
break;
case 7: if (p[10] && p[11] && !p[12])
{
p[10] = !p[10];
p[11] = !p[11];
p[12] = !p[12];
return true;
}
break;
case 8: if (p[11] && p[12] && !p[13])
{
p[11] = !p[11];
p[12] = !p[12];
p[13] = !p[13];
return true;
}
break;
case 9: if (p[12] && p[13] && !p[14])
{
p[12] = !p[12];
p[13] = !p[13];
p[14] = !p[14];
return true;
}
break;
case 10: if (p[14] && p[13] && !p[12])
{
p[14] = !p[14];
p[13] = !p[13];
p[12] = !p[12];
return true;
}
break;
case 11: if (p[13] && p[12] && !p[11])
{
p[13] = !p[13];
p[12] = !p[12];
p[11] = !p[11];
return true;
}
break;
case 12: if (p[12] && p[11] && !p[10])
{
p[12] = !p[12];
p[11] = !p[11];
p[10] = !p[10];
return true;
}
break;
case 13: if (p[5] && p[8] && !p[12])
{
p[5] = !p[5];
p[8] = !p[8];
p[12] = !p[12];
return true;
}
break;
case 14: if (p[12] && p[8] && !p[5])
{
p[12] = !p[12];
p[8] = !p[8];
p[5] = !p[5];
return true;
}
break;
case 15: if (p[2] && p[4] && !p[7])
{
p[2] = !p[2];
p[4] = !p[4];
p[7] = !p[7];
return true;
}
break;
case 16: if (p[4] && p[7] && !p[11])
{
p[4] = !p[4];
p[7] = !p[7];
p[11] = !p[11];
return true;
}
break;
case 17: if (p[11] && p[7] && !p[4])
{
p[11] = !p[11];
p[7] = !p[7];
p[4] = !p[4];
return true;
}
break;
case 18: if (p[7] && p[4] && !p[2])
{
p[7] = !p[2];
p[4] = !p[4];
p[2] = !p[2];
return true;
}
break;
case 19: if (p[0] && p[1] && !p[3])
{
p[0] = !p[0];
p[1] = !p[1];
p[3] = !p[3];
return true;
}
break;
case 20: if (p[1] && p[3] && !p[6])
{
p[1] = !p[1];
p[3] = !p[3];
p[6] = !p[6];
return true;
}
break;
case 21: if (p[3] && p[6] && !p[10])
{
p[3] = !p[3];
p[6] = !p[6];
p[10] = !p[10];
return true;
}
break;
case 22: if (p[10] && p[6] && !p[3])
{
p[10] = !p[10];
p[6] = !p[6];
p[3] = !p[3];
return true;
}
break;
case 23: if (p[6] && p[3] && !p[1])
{
p[6] = !p[6];
p[3] = !p[3];
p[1] = !p[1];
return true;
}
break;
case 24: if (p[3] && p[1] && !p[0])
{
p[3] = !p[3];
p[1] = !p[1];
p[0] = !p[0];
return true;
}
break;
case 25: if (p[3] && p[7] && !p[12])
{
p[3] = !p[3];
p[7] = !p[7];
p[12] = !p[12];
return true;
}
break;
case 26: if (p[12] && p[7] && !p[3])
{
p[12] = !p[12];
p[7] = !p[7];
p[3] = !p[3];
return true;
}
break;
case 27: if (p[1] && p[4] && !p[8])
{
p[1] = !p[1];
p[4] = !p[4];
p[8] = !p[8];
return true;
}
break;
case 28: if (p[4] && p[8] && !p[13])
{
p[4] = !p[4];
p[8] = !p[8];
p[13] = !p[13];
return true;
}
break;
case 29: if (p[13] && p[8] && !p[4])
{
p[13] = !p[13];
p[8] = !p[8];
p[4] = !p[4];
return true;
}
break;
case 30: if (p[8] && p[4] && !p[1])
{
p[8] = !p[8];
p[4] = !p[4];
p[1] = !p[1];
return true;
}
break;
case 31: if (p[0] && p[2] && !p[5])
{
p[0] = !p[0];
p[2] = !p[2];
p[5] = !p[5];
return true;
}
break;
case 32: if (p[2] && p[5] && !p[9])
{
p[2] = !p[2];
p[5] = !p[5];
p[9] = !p[9];
return true;
}
break;
case 33: if (p[5] && p[9] && !p[14])
{
p[5] = !p[5];
p[9] = !p[9];
p[14] = !p[14];
return true;
}
break;
case 34: if (p[14] && p[9] && !p[5])
{
p[14] = !p[14];
p[9] = !p[9];
p[5] = !p[5];
return true;
}
break;
case 35: if (p[9] && p[5] && !p[2])
{
p[9] = !p[9];
p[5] = !p[5];
p[2] = !p[2];
return true;
}
break;
case 36: if (p[5] && p[2] && !p[0])
{
p[5] = !p[5];
p[2] = !p[2];
p[0] = !p[0];
return true;
}
break;
}
return false;
}
void zapiszRuch(int n)
{
using std::cout;
using std::endl;
switch(n)
{
case 1: cout << "3 -> 5 (4)" << endl;
break;
case 2: cout << "5 -> 3 (4)" << endl;
break;
case 3: cout << "6 -> 8 (7)" << endl;
break;
case 4: cout << "7 -> 9 (8)" << endl;
break;
case 5: cout << "9 -> 7 (8)" << endl;
break;
case 6: cout << "8 -> 6 (7)" << endl;
break;
case 7: cout << "10 -> 12 (11)" << endl;
break;
case 8: cout << "11 -> 13 (12)" << endl;
break;
case 9: cout << "12 -> 14 (13)" << endl;
break;
case 10: cout << "14 -> 12 (13)" << endl;
break;
case 11: cout << "13 -> 11 (12)" << endl;
break;
case 12: cout << "12 -> 10 (11)" << endl;
break;
case 13: cout << "5 -> 12 (8)" << endl;
break;
case 14: cout << "12 -> 5 (8)" << endl;
break;
case 15: cout << "2 -> 7 (4)" << endl;
break;
case 16: cout << "4 -> 11 (7)" << endl;
break;
case 17: cout << "11 -> 4 (7)" << endl;
break;
case 18: cout << "7 -> 2 (4)" << endl;
break;
case 19: cout << "0 -> 3 (1)" << endl;
break;
case 20: cout << "1 -> 6 (3)" << endl;
break;
case 21: cout << "3 -> 10 (6)" << endl;
break;
case 22: cout << "10 -> 3 (6)" << endl;
break;
case 23: cout << "6 -> 1 (3)" << endl;
break;
case 24: cout << "3 -> 0 (1)" << endl;
break;
case 25: cout << "3 -> 12 (7)" << endl;
break;
case 26: cout << "12 -> 3 (7)" << endl;
break;
case 27: cout << "1 -> 8 (4)" << endl;
break;
case 28: cout << "4 -> 13 (8)" << endl;
break;
case 29: cout << "13 -> 4 (8)" << endl;
break;
case 30: cout << "8 -> 1 (4)" << endl;
break;
case 31: cout << "0 -> 5 (2)" << endl;
break;
case 32: cout << "2 -> 9 (5)" << endl;
break;
case 33: cout << "5 -> 14 (9)" << endl;
break;
case 34: cout << "14 -> 5 (9)" << endl;
break;
case 35: cout << "9 -> 2 (5)" << endl;
break;
case 36: cout << "5 -> 0 (2)" << endl;
break;
}
}
void cofnijRuch(int n)
{
switch(n)
{
case 1: p[3] = !p[3];
p[4] = !p[4];
p[5] = !p[5];
break;
case 2: p[5] = !p[5];
p[4] = !p[4];
p[3] = !p[3];
break;
case 3: p[6] = !p[6];
p[7] = !p[7];
p[8] = !p[8];
break;
case 4: p[7] = !p[7];
p[8] = !p[8];
p[9] = !p[9];
break;
case 5: p[9] = !p[9];
p[8] = !p[8];
p[7] = !p[7];
break;
case 6: p[8] = !p[8];
p[7] = !p[7];
p[6] = !p[6];
break;
case 7: p[10] = !p[10];
p[11] = !p[11];
p[12] = !p[12];
break;
case 8: p[11] = !p[11];
p[12] = !p[12];
p[13] = !p[13];
break;
case 9: p[12] = !p[12];
p[13] = !p[13];
p[14] = !p[14];
break;
case 10: p[14] = !p[14];
p[13] = !p[13];
p[12] = !p[12];
break;
case 11: p[13] = !p[13];
p[12] = !p[12];
p[11] = !p[11];
break;
case 12: p[12] = !p[12];
p[11] = !p[11];
p[10] = !p[10];
break;
case 13: p[5] = !p[5];
p[8] = !p[8];
p[12] = !p[12];
break;
case 14: p[12] = !p[12];
p[8] = !p[8];
p[5] = !p[5];
break;
case 15: p[2] = !p[2];
p[4] = !p[4];
p[7] = !p[7];
break;
case 16: p[4] = !p[4];
p[7] = !p[7];
p[11] = !p[11];
break;
case 17: p[11] = !p[11];
p[7] = !p[7];
p[4] = !p[4];
break;
case 18: p[7] = !p[2];
p[4] = !p[4];
p[2] = !p[2];
break;
case 19: p[0] = !p[0];
p[1] = !p[1];
p[3] = !p[3];
break;
case 20: p[1] = !p[1];
p[3] = !p[3];
p[6] = !p[6];
break;
case 21: p[3] = !p[3];
p[6] = !p[6];
p[10] = !p[10];
break;
case 22: p[10] = !p[10];
p[6] = !p[6];
p[3] = !p[3];
break;
case 23: p[6] = !p[6];
p[3] = !p[3];
p[1] = !p[1];
break;
case 24: p[3] = !p[3];
p[1] = !p[1];
p[0] = !p[0];
break;
case 25: p[3] = !p[3];
p[7] = !p[7];
p[12] = !p[12];
break;
case 26: p[12] = !p[12];
p[7] = !p[7];
p[3] = !p[3];
break;
case 27: p[1] = !p[1];
p[4] = !p[4];
p[8] = !p[8];
break;
case 28: p[4] = !p[4];
p[8] = !p[8];
p[13] = !p[13];
break;
case 29: p[13] = !p[13];
p[8] = !p[8];
p[4] = !p[4];
break;
case 30: p[8] = !p[8];
p[4] = !p[4];
p[1] = !p[1];
break;
case 31: p[0] = !p[0];
p[2] = !p[2];
p[5] = !p[5];
break;
case 32: p[2] = !p[2];
p[5] = !p[5];
p[9] = !p[9];
break;
case 33: p[5] = !p[5];
p[9] = !p[9];
p[14] = !p[14];
break;
case 34: p[14] = !p[14];
p[9] = !p[9];
p[5] = !p[5];
break;
case 35: p[9] = !p[9];
p[5] = !p[5];
p[2] = !p[2];
break;
case 36: p[5] = !p[5];
p[2] = !p[2];
p[0] = !p[0];
break;
}
}
0
Juz wiem czemu wywala pozostale smieci. Chodzi o rozgalezienia. Jezeli np mamy pionki na polach 0 2 9 przy oznaczeniach:
0
1 2
3 4 5
6 7 8 9
10 11 12 13 14
to mamy mozliwosc pojscia:
0 -> 5 (2)
i teraz rozgalezienie: mozemy pojsc:
9 -> 2 (5)
ale i:
5 -> 14 (9)
i on to wszystko miesza ze soba, nie wiem teraz jak to rozdzielic, wszystko sie komplikuje....
0
michal_23 napisał(a)
Wiec napisalem taka funkcje ale ona jakos dziwnie sie zachowuje, nie wiem do konca czemu. Ale najpierw dam jej kod:
int nastepnyRuch()
{
using std::cout;
int liczbaPionkowNaPlanszy = liczbaPozostalychPionkow();
static int poziom;
cout << poziom << std::endl;
poziom++;
for (int i = 1; i <= 36; i++)
{
if (!wykonajRuch(i))
continue;
if (nastepnyRuch() == 1)
{
zapiszRuch(i);
liczbaPionkowNaPlanszy = 1;
}
cofnijRuch(i);
}
poziom--;
cout << poziom << std::endl;
return liczbaPionkowNaPlanszy;
}
Opisze o co chodzi. Na poczatku funkcja pobiera od funkcji liczbaPozostalychPionkow() liczbe pionkow jaka jest na planszy. Dalej ten kod z poziomami to diagnostyka tylko i wylacznie. Dalej mamy petle for w ktorej przechodzi ona przez 36 - wszystkie mozliwe ruchy jakie mozna wykonac w grze. Funckja bool wykonajRuch(int n) zwraca true jesli dalo sie wykonac ruch. Jesli sie nie dalo mamy warunek w if ktory jest spelniony kiedy nie mamy ruchu do wykonania. Wtedy nie trzeba nic robic i mamy dlatego continue ktore przechodzi do sprawdzania nastepnego ruchu. Dalej jesli w nastepnym ruchu liczba pionkow jest 1 to zapisuje ruch a liczbe pionkow zmienia na 1 dla zwrocenia poprzedniemu wywolaniu. dalej cofamy wykonany ruch aby moc sprawdzic nastepne mozliwosci manewru.
Z ta funkcja jest cos nie tak. Dla maksymalnego obciazenia (14 z 15 pionkow ustawione na planszy) wyskakuje Stack Overflow co jest dziwne bo funkcja nie powinna sie az tyle razy wywolywac. Ale jak sprawdzilem za pomoca zmiennej poziom wywoluje sie w pewnym momencie dla 14 pionkow niemalze w nieskonczonosc, nie wiem czemu. Dla mniejszego obciazenia daje sie uruchomic, zwraca wlasciwa kolejnosc (tzn w odwrotnej kolejnosci ale to jest do poprawienia kiedys) ale procz tego zwraca jakies cos dziwnego. Prosze o jakies wskazowki. Dla pelnego obrazu moge dac pelny kod:
// _v0.5_piramida.cpp -- program znajdujacy wszystkie rozwiazania gry logicznej i wypisujacy je na ekranie
#include <iostream>
int nastepnyRuch();
int liczbaPozostalychPionkow();
bool wykonajRuch(int n);
void zapiszRuch(int n);
void cofnijRuch(int n);
bool p[15] = { false, false, false, false, false, false, false, false, false, false, false, false, false, false, false };
int main()
{
using std::cout;
using std::cin;
using std::endl;
cout << " 0" << endl;
cout << " 1 2" << endl;
cout << " 3 4 5" << endl;
cout << " 6 7 8 9" << endl;
cout << "10 11 12 13 14" << endl;
// cout << "Wybierz pole puste (0-14): ";
// int pole;
// cin >> pole;
// p[pole] = false;
p[1] = p[2] = p[4] = p[11] = p[6] = p[7] = p[8] = true;
nastepnyRuch();
return 0;
}
int nastepnyRuch()
{
using std::cout;
int liczbaPionkowNaPlanszy = liczbaPozostalychPionkow();
static int poziom;
cout << poziom << std::endl;
poziom++;
for (int i = 1; i <= 36; i++)
{
if (!wykonajRuch(i))
continue;
if (nastepnyRuch() == 1)
{
zapiszRuch(i);
liczbaPionkowNaPlanszy = 1;
}
cofnijRuch(i);
}
poziom--;
cout << poziom << std::endl;
return liczbaPionkowNaPlanszy;
}
int liczbaPozostalychPionkow()
{
int licznik = 0;
for (int i = 0; i < 15; i++)
if (p[i])
licznik++;
return licznik;
}
bool wykonajRuch(int n)
{
switch(n)
{
case 1: if (p[3] && p[4] && !p[5])
{
p[3] = !p[3];
p[4] = !p[4];
p[5] = !p[5];
return true;
}
break;
case 2: if (p[5] && p[4] && !p[3])
{
p[5] = !p[5];
p[4] = !p[4];
p[3] = !p[3];
return true;
}
break;
case 3: if (p[6] && p[7] && !p[8])
{
p[6] = !p[6];
p[7] = !p[7];
p[8] = !p[8];
return true;
}
break;
case 4: if (p[7] && p[8] && !p[9])
{
p[7] = !p[7];
p[8] = !p[8];
p[9] = !p[9];
return true;
}
break;
case 5: if (p[9] && p[8] && !p[7])
{
p[9] = !p[9];
p[8] = !p[8];
p[7] = !p[7];
return true;
}
break;
case 6: if (p[8] && p[7] && !p[6])
{
p[8] = !p[8];
p[7] = !p[7];
p[6] = !p[6];
return true;
}
break;
case 7: if (p[10] && p[11] && !p[12])
{
p[10] = !p[10];
p[11] = !p[11];
p[12] = !p[12];
return true;
}
break;
case 8: if (p[11] && p[12] && !p[13])
{
p[11] = !p[11];
p[12] = !p[12];
p[13] = !p[13];
return true;
}
break;
case 9: if (p[12] && p[13] && !p[14])
{
p[12] = !p[12];
p[13] = !p[13];
p[14] = !p[14];
return true;
}
break;
case 10: if (p[14] && p[13] && !p[12])
{
p[14] = !p[14];
p[13] = !p[13];
p[12] = !p[12];
return true;
}
break;
case 11: if (p[13] && p[12] && !p[11])
{
p[13] = !p[13];
p[12] = !p[12];
p[11] = !p[11];
return true;
}
break;
case 12: if (p[12] && p[11] && !p[10])
{
p[12] = !p[12];
p[11] = !p[11];
p[10] = !p[10];
return true;
}
break;
case 13: if (p[5] && p[8] && !p[12])
{
p[5] = !p[5];
p[8] = !p[8];
p[12] = !p[12];
return true;
}
break;
case 14: if (p[12] && p[8] && !p[5])
{
p[12] = !p[12];
p[8] = !p[8];
p[5] = !p[5];
return true;
}
break;
case 15: if (p[2] && p[4] && !p[7])
{
p[2] = !p[2];
p[4] = !p[4];
p[7] = !p[7];
return true;
}
break;
case 16: if (p[4] && p[7] && !p[11])
{
p[4] = !p[4];
p[7] = !p[7];
p[11] = !p[11];
return true;
}
break;
case 17: if (p[11] && p[7] && !p[4])
{
p[11] = !p[11];
p[7] = !p[7];
p[4] = !p[4];
return true;
}
break;
case 18: if (p[7] && p[4] && !p[2])
{
p[7] = !p[2];
p[4] = !p[4];
p[2] = !p[2];
return true;
}
break;
case 19: if (p[0] && p[1] && !p[3])
{
p[0] = !p[0];
p[1] = !p[1];
p[3] = !p[3];
return true;
}
break;
case 20: if (p[1] && p[3] && !p[6])
{
p[1] = !p[1];
p[3] = !p[3];
p[6] = !p[6];
return true;
}
break;
case 21: if (p[3] && p[6] && !p[10])
{
p[3] = !p[3];
p[6] = !p[6];
p[10] = !p[10];
return true;
}
break;
case 22: if (p[10] && p[6] && !p[3])
{
p[10] = !p[10];
p[6] = !p[6];
p[3] = !p[3];
return true;
}
break;
case 23: if (p[6] && p[3] && !p[1])
{
p[6] = !p[6];
p[3] = !p[3];
p[1] = !p[1];
return true;
}
break;
case 24: if (p[3] && p[1] && !p[0])
{
p[3] = !p[3];
p[1] = !p[1];
p[0] = !p[0];
return true;
}
break;
case 25: if (p[3] && p[7] && !p[12])
{
p[3] = !p[3];
p[7] = !p[7];
p[12] = !p[12];
return true;
}
break;
case 26: if (p[12] && p[7] && !p[3])
{
p[12] = !p[12];
p[7] = !p[7];
p[3] = !p[3];
return true;
}
break;
case 27: if (p[1] && p[4] && !p[8])
{
p[1] = !p[1];
p[4] = !p[4];
p[8] = !p[8];
return true;
}
break;
case 28: if (p[4] && p[8] && !p[13])
{
p[4] = !p[4];
p[8] = !p[8];
p[13] = !p[13];
return true;
}
break;
case 29: if (p[13] && p[8] && !p[4])
{
p[13] = !p[13];
p[8] = !p[8];
p[4] = !p[4];
return true;
}
break;
case 30: if (p[8] && p[4] && !p[1])
{
p[8] = !p[8];
p[4] = !p[4];
p[1] = !p[1];
return true;
}
break;
case 31: if (p[0] && p[2] && !p[5])
{
p[0] = !p[0];
p[2] = !p[2];
p[5] = !p[5];
return true;
}
break;
case 32: if (p[2] && p[5] && !p[9])
{
p[2] = !p[2];
p[5] = !p[5];
p[9] = !p[9];
return true;
}
break;
case 33: if (p[5] && p[9] && !p[14])
{
p[5] = !p[5];
p[9] = !p[9];
p[14] = !p[14];
return true;
}
break;
case 34: if (p[14] && p[9] && !p[5])
{
p[14] = !p[14];
p[9] = !p[9];
p[5] = !p[5];
return true;
}
break;
case 35: if (p[9] && p[5] && !p[2])
{
p[9] = !p[9];
p[5] = !p[5];
p[2] = !p[2];
return true;
}
break;
case 36: if (p[5] && p[2] && !p[0])
{
p[5] = !p[5];
p[2] = !p[2];
p[0] = !p[0];
return true;
}
break;
}
return false;
}
void zapiszRuch(int n)
{
using std::cout;
using std::endl;
switch(n)
{
case 1: cout << "3 -> 5 (4)" << endl;
break;
case 2: cout << "5 -> 3 (4)" << endl;
break;
case 3: cout << "6 -> 8 (7)" << endl;
break;
case 4: cout << "7 -> 9 (8)" << endl;
break;
case 5: cout << "9 -> 7 (8)" << endl;
break;
case 6: cout << "8 -> 6 (7)" << endl;
break;
case 7: cout << "10 -> 12 (11)" << endl;
break;
case 8: cout << "11 -> 13 (12)" << endl;
break;
case 9: cout << "12 -> 14 (13)" << endl;
break;
case 10: cout << "14 -> 12 (13)" << endl;
break;
case 11: cout << "13 -> 11 (12)" << endl;
break;
case 12: cout << "12 -> 10 (11)" << endl;
break;
case 13: cout << "5 -> 12 (8)" << endl;
break;
case 14: cout << "12 -> 5 (8)" << endl;
break;
case 15: cout << "2 -> 7 (4)" << endl;
break;
case 16: cout << "4 -> 11 (7)" << endl;
break;
case 17: cout << "11 -> 4 (7)" << endl;
break;
case 18: cout << "7 -> 2 (4)" << endl;
break;
case 19: cout << "0 -> 3 (1)" << endl;
break;
case 20: cout << "1 -> 6 (3)" << endl;
break;
case 21: cout << "3 -> 10 (6)" << endl;
break;
case 22: cout << "10 -> 3 (6)" << endl;
break;
case 23: cout << "6 -> 1 (3)" << endl;
break;
case 24: cout << "3 -> 0 (1)" << endl;
break;
case 25: cout << "3 -> 12 (7)" << endl;
break;
case 26: cout << "12 -> 3 (7)" << endl;
break;
case 27: cout << "1 -> 8 (4)" << endl;
break;
case 28: cout << "4 -> 13 (8)" << endl;
break;
case 29: cout << "13 -> 4 (8)" << endl;
break;
case 30: cout << "8 -> 1 (4)" << endl;
break;
case 31: cout << "0 -> 5 (2)" << endl;
break;
case 32: cout << "2 -> 9 (5)" << endl;
break;
case 33: cout << "5 -> 14 (9)" << endl;
break;
case 34: cout << "14 -> 5 (9)" << endl;
break;
case 35: cout << "9 -> 2 (5)" << endl;
break;
case 36: cout << "5 -> 0 (2)" << endl;
break;
}
}
void cofnijRuch(int n)
{
switch(n)
{
case 1: p[3] = !p[3];
p[4] = !p[4];
p[5] = !p[5];
break;
case 2: p[5] = !p[5];
p[4] = !p[4];
p[3] = !p[3];
break;
case 3: p[6] = !p[6];
p[7] = !p[7];
p[8] = !p[8];
break;
case 4: p[7] = !p[7];
p[8] = !p[8];
p[9] = !p[9];
break;
case 5: p[9] = !p[9];
p[8] = !p[8];
p[7] = !p[7];
break;
case 6: p[8] = !p[8];
p[7] = !p[7];
p[6] = !p[6];
break;
case 7: p[10] = !p[10];
p[11] = !p[11];
p[12] = !p[12];
break;
case 8: p[11] = !p[11];
p[12] = !p[12];
p[13] = !p[13];
break;
case 9: p[12] = !p[12];
p[13] = !p[13];
p[14] = !p[14];
break;
case 10: p[14] = !p[14];
p[13] = !p[13];
p[12] = !p[12];
break;
case 11: p[13] = !p[13];
p[12] = !p[12];
p[11] = !p[11];
break;
case 12: p[12] = !p[12];
p[11] = !p[11];
p[10] = !p[10];
break;
case 13: p[5] = !p[5];
p[8] = !p[8];
p[12] = !p[12];
break;
case 14: p[12] = !p[12];
p[8] = !p[8];
p[5] = !p[5];
break;
case 15: p[2] = !p[2];
p[4] = !p[4];
p[7] = !p[7];
break;
case 16: p[4] = !p[4];
p[7] = !p[7];
p[11] = !p[11];
break;
case 17: p[11] = !p[11];
p[7] = !p[7];
p[4] = !p[4];
break;
case 18: p[7] = !p[2];
p[4] = !p[4];
p[2] = !p[2];
break;
case 19: p[0] = !p[0];
p[1] = !p[1];
p[3] = !p[3];
break;
case 20: p[1] = !p[1];
p[3] = !p[3];
p[6] = !p[6];
break;
case 21: p[3] = !p[3];
p[6] = !p[6];
p[10] = !p[10];
break;
case 22: p[10] = !p[10];
p[6] = !p[6];
p[3] = !p[3];
break;
case 23: p[6] = !p[6];
p[3] = !p[3];
p[1] = !p[1];
break;
case 24: p[3] = !p[3];
p[1] = !p[1];
p[0] = !p[0];
break;
case 25: p[3] = !p[3];
p[7] = !p[7];
p[12] = !p[12];
break;
case 26: p[12] = !p[12];
p[7] = !p[7];
p[3] = !p[3];
break;
case 27: p[1] = !p[1];
p[4] = !p[4];
p[8] = !p[8];
break;
case 28: p[4] = !p[4];
p[8] = !p[8];
p[13] = !p[13];
break;
case 29: p[13] = !p[13];
p[8] = !p[8];
p[4] = !p[4];
break;
case 30: p[8] = !p[8];
p[4] = !p[4];
p[1] = !p[1];
break;
case 31: p[0] = !p[0];
p[2] = !p[2];
p[5] = !p[5];
break;
case 32: p[2] = !p[2];
p[5] = !p[5];
p[9] = !p[9];
break;
case 33: p[5] = !p[5];
p[9] = !p[9];
p[14] = !p[14];
break;
case 34: p[14] = !p[14];
p[9] = !p[9];
p[5] = !p[5];
break;
case 35: p[9] = !p[9];
p[5] = !p[5];
p[2] = !p[2];
break;
case 36: p[5] = !p[5];
p[2] = !p[2];
p[0] = !p[0];
break;
}
}
Nie wiedziałem, że switch może być taki długi.
0
To jest przykład bardo złego stylu programowania. A co będzie, jeśli ktoś powie: "Ok uprośmy problem i zmniejszmy bok planszy o 1" albo "niech bok będzie miał długość 8".
Na dodatek, jeśli gdzieś zrobiłeś błąd to znalezienie go będzie prawdziwą mordęgą.
Załóżmy, że plansza wygląda tak:
0: 1: 2: 3: 4:
0: *
1: * *
2: * * *
3: * * * *
4: * * * * *
x i y oznaczają pozycję pionka, więc sprawdzanie kolejnych ruchów wygląda tak:
// w lewo
if( x>=2 && // ruch musi być wewnątrz planszy
plansza[x-1][y] && // pionek musi mieć co przeskoczyć
!plansza[x-2][y] ) // pionek musi mieć wolne miejsce na skok
{
plansza[x][y] = false; // skok z
plansza[x-2][y] = true; // skok do
plansza[x-1][y] = false; // bicie
... // tu rekurencja i sprawdzanie skutków tego ruchu
// cofanie ruchu by odtworzyć planszę
plansza[x][y] = true; // skok z
plansza[x-2][y] = false; // skok do
plansza[x-1][y] = true; // bicie
}
// w prawo
if( x+2<=y && // ruch musi być wewnątrz planszy
plansza[x+1][y] && // pionek musi mieć co przeskoczyć
!plansza[x+2][y] ) // miejsce na skok
{
....
}
// w lewo w górę
if( x-2>=y && // ruch musi być wewnątrz planszy
plansza[x-1][y-1] && // pionek musi mieć co przeskoczyć
!plansza[x-2][y-2] ) // miejsce na skok
{
....
}
// w prawo w górę
if( y-2>=x &&// ruch musi być wewnątrz planszy
plansza[x][y-1] && // pionek musi mieć co przeskoczyć
!plansza[x][y-2] ) // miejsce na skok
{
....
}
// w prawo w dół
if( y+2<RozmiarPlanszy && // ruch musi być wewnątrz planszy
plansza[x][y+1] && // pionek musi mieć co przeskoczyć
!plansza[x][y+2] ) // miejsce na skok
{
....
}
// w lewo w dół
if( y+2<RozmiarPlanszy && x >=2 // ruch musi być wewnątrz planszy
plansza[x-1][y+1] && // pionek musi mieć co przeskoczyć
!plansza[x-2][y+2] ) // miejsce na skok
{
....
}
0
Takie podejscie bardzo komplikuje sprawe. Poniewaz do obslugi takiej planszy potrzebne beda 3 petle for ktore beda wykonywac lacznie 150 krokow:
for (nX = 0; nX <= 4; nX++)
for (nY = 0; nY <= 4; nY++)
for (i = 1; i <= 6; i++)
{ ... }
Dodatkowo calosc programu stanie sie zagmatwana. Poprzednia wersja wykonywala na jedno wywolanie funkcji 36 ruchow.
0
gadasz głupoty.
Po pierwsze pętle wyglądają tak:
for (nY = 0; nY < WiekoscPlanszy; nY++)
for (nX = 0; nX < nY; nX++)
if(plansza[nX][nY]) // czy tam jest pionek
{ .... }
Po drugie zestaw if-ów bardzo ograniczy rekurencje i ruchów do wykonania będzie mało.
Po trzecie tak czy tak cały czas mówimy o metodzie brutal force, więc i tak zawsze musisz odszukać wszystkie możliwe ruchy i je przetestować, a taki zapis jest o wiele czytelniejszy niż ten zapis ze switch case (prawdziwy koszmar). Już sama różnica w liczbie linii sugeruje, że twój kod to jest proszenie się o kłopoty.
Swoją drogą to po zastanowieniu dochodzę do wniosku, że jeszcze można uprościć mój kod (zredukować liczbę linii) stosują uogólnione metodę sprawdzania czy dany ruch jest możliwy.
0
Ale wydaje mi sie, ze switch tez bedzie potrzebny (z 6 case'ami) bo jest 6 mozliwych ruchow do wykonania (w gore, w dol, w prawo, w lewo, w lewo-gora, w prawo-dol; w prawo-gora i lewo-dol nie ma bo takie ruchy sa nie dozwolone, w tej perspektywie tego nie widac, ale to jest przeskakiwanie dwoch linii). Jesli sie nie zastosuje switch'a to bedzie niejednoznacznosc jesli np. dla jednego pionka bedzie mozna wykonac kilka ruchow. Przy cofaniu to sie moze zemscic.
0
człowieku rusz trochę głową i popatrz na ostatni kod, który ci dałem, a nawet go gęsto okrasiłem komentarzami.