Problem skoczka szachowego. Algorytm w C++

[cytat=Problem skoczka szachowego]Znaleźć taką drogę aby poruszając się ruchem konika szachowego, odwiedzić wszystkie pola na szachownicy. W każdym polu konik może stanąć tylko raz[/cytat] [b]Projekt uruchamiany pod Visual Studio 2008.[/b] [code=cpp] // skoczek_szachowy.cpp : Defines the entry point for the console application. // #include “stdafx.h” #include #include using namespace std; //========================================================= const int n=5; int pozx, pozy; int lp, i, j; bool q; // czy uist. rozwiazanie int plansza[n][n]; int tab_ruchow[8][2]={{-1,-2},{-1,2},{1,-2},{1,2},{-2,-1},{-2,1},{2,-1},{2,1}}; char czy_koniec; int liczba_wyw_fun;

Dodaj artykuł aby odblokować treść

[cytat=Problem skoczka szachowego]Znaleźć taką drogę aby poruszając się ruchem konika szachowego, odwiedzić wszystkie pola na szachownicy. W każdym polu konik może stanąć tylko raz[/cytat]

[b]Projekt uruchamiany pod Visual Studio 2008.[/b]

[code=cpp] // skoczek_szachowy.cpp : Defines the entry point for the console application. //

#include “stdafx.h” #include #include

using namespace std;

//=========================================================

const int n=5; int pozx, pozy; int lp, i, j; bool q; // czy uist. rozwiazanie int plansza[n][n]; int tab_ruchow[8][2]={{-1,-2},{-1,2},{1,-2},{1,2},{-2,-1},{-2,1},{2,-1},{2,1}}; char czy_koniec; int liczba_wyw_fun;

void gotoxy(int x, int y); void rysuj_ruch();

//=========================================================

void ruch_skoczka(int i, int w, int k) { liczba_wyw_fun++; int x,y,j; j=-1; do { j++; q = false; x = w+tab_ruchow[j][0]; y = k+tab_ruchow[j][1]; // nowa pozycja //cout«“n wybor nowej pozycji, x="«x«” y="«y«endl; if(x>=0 && x<n && y>=0 && y<n && plansza[x][y]==0) { // wolne pola i na planszy plansza[x][y] = i; // nowa tymczasowa pozycja //cout«“n wykonanie nowego ruchu nr “«i«” x="«x«” y="«y«endl; getchar(); if(i<lp) { // jezeli sa jeszcze wolne miejsca na planszy ruch_skoczka(i+1,x,y); //kolejny ruch, arg.: kolejny ruch, ost. poz. x i if(q == false) { plansza[x][y]=0; //jezleli q=0, nie ma jeszcze ostatniego rozwiazania, o // jezeli q=1, jest rozwiazanie, pozycje nie sa usuwane, nie maja ust. wart } } else { q = true; cout«“nostateczne roz: “«plansza[x][y]«“n”; // jest ostateczne rozwiazanie } } } while(q == false && j<7); // jezeli j=7 ostatni krok wyb. nowej poz. zakonczony, nie ko // powracamy do poprz. wyw proc. ktora pamieta sprawdzone ruchy i sp

}

//=========================================================

int _tmain(int argc, _TCHAR* argv[]) { //int tablica[8][8]; //for(int i=0; i<8; i++) { // for(int j=0; j<8; j++) { // tablica[i][j]=0; // } //}

//tablica[1][2]=3;
//cout<<tablica[1][2];

do {
	liczba_wyw_fun=0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			plansza[i][j]=0;
			cout<<"npodaj wsp. x pozycji startowej (0-4) "; cin>>pozx;
			cout<<"npodaj wsp. y pozycji startowej (0-4) "; cin>>pozy;
			plansza[pozx][pozy]=1;
			lp=n*n;
			ruch_skoczka(2,pozx,pozy);
			if(q == true) {
				for(int i=0; i<n; i++) {
					cout<<"n";
					for(int j=0; j<n; j++) {
						cout<<setw(3)<<plansza[i][j]; //setw(3) - manipulator, pole aby bylo zawsze okreslonej wielkosci, zeby sie nie rozjezdzalo
					}
				}
			} else {
				cout<<"nnie ma rozwiazania";					
			}
			cout<<"nliczba wywolan funkcji: "<<liczba_wyw_fun;
			//rysuj_ruch(); gotoxy(6,0);
			cout<<"nczy kontynuowac t/n";
			cin>>czy_koniec;
		}
	}
} while(czy_koniec=='t');


cout<<"nn";
system("pause");
return 0;

} [/code]