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

Problem skoczka szachowego

Projekt uruchamiany pod Visual Studio 2008.



// skoczek_szachowy.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <iomanip>

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;
}