Problem with Backtracking!

vincent90 (7)
Hello, i have a homework to do, and im really messed up!

I need to do the knight's game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
void Echiquier::Placer_Cavalier(int i,int j)
{
	int x = i;
	int y = j;

			if(oMatrice_[i][j] == 0)
			{
				
				BloquerCase(x,y);

				if(iCoup_ == iMAXCASES)
				{	
					Afficher();
				}
				else
                                //Try to find the better position
				Déplacement_Cavalier(x,y);
					       Afficher();			
// Recursive function	
Placer_Cavalier(iPos_Algo_X,iPos_Algo_Y);
				DébloquerCases(x,y);
		}
}


Check if there is a number( knight as pass by), if its in the chess board
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
void Echiquier::Déplacement_Cavalier(int x,int y)
{
	iPos_Algo_X = 100;
	iPos_Algo_Y = 100;
	int temp = 100; 

	if(EstValide(x+1,y+2)) 
	{
		if(oMatrice_[x+1][y+2] == 0) {
		if(temp > Algorithme(x+1,y+2) && temp != 0)
		{
		iPos_Algo_X = x+1;
		iPos_Algo_Y = y+2;
		}
		}
	}

	if(EstValide(x-1, y+2))
	{
		if(oMatrice_[x-1][y+2] == 0) {
		if(temp > Algorithme(x-1, y+2) && temp != 0)
		{
			iPos_Algo_X = x-1;
			iPos_Algo_Y = y+2;
		}
		}
	}

	if(EstValide(x+2, y+1)) 
	{
		if(oMatrice_[x+2][y+1] == 0) {
		if( temp > Algorithme(x+2, y+1) && temp != 0)
		{
			iPos_Algo_X = x+2;
			iPos_Algo_Y = y+1;
		}
		}
	}
	if(EstValide(x+2, y-1)) 
	{
		if(oMatrice_[x+2][y-1] == 0) {
		if(temp > Algorithme(x+2, y-1)  && temp != 0)
		{
			iPos_Algo_X = x+2;
			iPos_Algo_Y = y-1;
		}
		}
	}

	if(EstValide(x+1, y-2)) 
	{
		if(oMatrice_[x+1][y-2] == 0) {
		if( temp > Algorithme(x+1, y-2) && temp != 0)
		{
			iPos_Algo_X = x+1;
			iPos_Algo_Y = y-2;
		}
		}
	}
	if(EstValide(x-1, y-2)) 
	{
		if(oMatrice_[x-1][y-2] == 0) {
		if(temp > Algorithme(x-1, y-2) && temp != 0)
		{

			iPos_Algo_X = x-1;
			iPos_Algo_Y = y-2;
		}
		}
	}

	if(EstValide(x-2, y+1))
	{
		if(oMatrice_[x-2][y+1] == 0) {
		if(temp > Algorithme(x-2, y+1) && temp != 0)
		{
			iPos_Algo_X = x-2;
			iPos_Algo_Y = y+1;
		}
		}
	}
	if(EstValide(x-2, y-1))
	{
		if(oMatrice_[x-2][y-1] == 0) {
		//
		if(temp > Algorithme(x-2, y-1) && temp != 0)
		{
			iPos_Algo_X = x-2;
			iPos_Algo_Y = y-1;
		}
		}
		
	}

}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
int Echiquier::Algorithme(int x, int y)
{
	int i = 0;

	if(EstValide(x+1,y+2)) 
	{
		
		i++;
	}

	if(EstValide(x-1, y+2))
	{
		i++;
	}

	if(EstValide(x+2, y+1)) 
	{
		i++;
	}
	if(EstValide(x+2, y-1)) 
	{
		i++;
	}

	if(EstValide(x+1, y-2)) 
	{
		i++;
	}
	if(EstValide(x-1, y-2)) 
	{
		i++;
	}

	if(EstValide(x-2, y+1))
	{
		i++;
	}
	if(EstValide(x-2, y-1))
	{
		i++;
	}
	return i++;

}


Im using the Warndoffs algo

Warnsdorff’s algorithm will do for any initial position of the knight on the board. All the possible squares which may be reached in one move from this position are located, and the number of moves that the knight would be able to make from each of these squares is found.[13] Then, the algorithm dictates that the knight move to the square that has the least number of possible following moves. The process is then repeated until each square has been visited.[12][14]



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
Echiquier::Echiquier()
{   
	oMatrice_.SetNbLignes(iGRANDEUR_);
	oMatrice_.SetNbColonnes(iGRANDEUR_);

	for(int i=0; i<7;i++)
		for(int j=0; j<7;j++)
			oMatrice_[i][j]=0;
	SetNbTemps(0);
	iCoup_ = 1;
}


bool Echiquier::EstValide(int x, int y)
{
	if( x >= 0 && x <= 7 && y >= 0 && y <= 7)
	{
		if(oMatrice_[x][y] == 0)
		{
			return true;
		}
	}else
	{
	return false;
	}
}
void Echiquier::BloquerCase(int x,int y)
{
	oMatrice_[x][y]= iCoup_;
	iCoup_++;
}
void Echiquier::DébloquerCases(int x,int y)
{
	oMatrice_[x][y]= 0;
	iCoup_--;
}

void Echiquier::Afficher()
{
	system("cls");
	for(int i=0;i<8;i++)
	{
		for(int j=0; j<8;j++)
		{
			cout << oMatrice_[i][j];
			cout <<"|";
		}
		cout<<endl;
	}

}

void Echiquier::SetNbTemps(__int64 iTemps)
{
	iTempsTotal_ = iTemps;
}

__int64 Echiquier::GetNbtemps() const
{
	return iTempsTotal_;
}

void Echiquier::TrouverSolution(int i, int j)
{
	this->oPreciseTimer.StartTimer();
	Placer_Cavalier(i,j);
}


Somehow, the recursive of backtracking is NOT working,.. im really lost here and i could really use a helping hand...
Topic archived. No new replies allowed.