why bruteforce losts its fuctionlaity at some point in this code?

[istemihan]

I am trying to solve a puzzle again! this is the link: http://www.puzzleup.com/2015/puzzle/?9

my method requires vectors. Because I use this method: http://i.stack.imgur.com/Z2oaV.png

I valued all the corners, and I track each iteration thrugh the end(15 th corner). I start from 1 and record all the corners I ve been through in the possibilities 2d array.


My problem is this: The code actually iterates fine till a point. 1,2 2,4 4,3 3,1 1,5 5,6 6,8 8,7 7,5 7,3 7,5 7,3 7,5 7,3 ....

it seems it losts his iteration capability in 10th iteration. I am on this for almost one week and still have not came up with anything. So I found this forum and asking for your help. If you see what I do not see, please share with me and I will be grateful. Thanks.

#include <iostream>
#include <vector>
#include <cmath>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

/*
possibilities will keep the possible combinations, routes like {1,4}{4,8}{8,7} etc till it arrives to 15
*/

vector< vector<int> > possibilities;

vector< vector<int> >::iterator row;

vector<int>::iterator col;


int cubes[15][6] = { {2,3,5,0,0,0}, {1,4,6,0,0,0}, {1,4,7,0,0,0}, {2,3,8,0,0,0}, 
{1,6,7,0,0,0}, {2,5,8,0,0,0}, {3,5,8,0,0,0}, {4,6,7,9,10,13}, {8,11,12,0,0,0}, 
{8,11,14,0,0,0}, {9,10,15,0,0,0}, {9,13,15,0,0,0}, {8,12,14,0,0,0}, 
{10,13,15,0,0,0}, {11,12,14,0,0,0} };

int counterSet, i, j, temp, temp2, counter, sizeOfVec;

int routeCheck(int a, int b)
{
	//
		//
		if(!possibilities.empty())
		{
			//
			for(i=0; i< (int)possibilities.size(); i++)
			{
				//
				if(((possibilities[i][0] == a) && (possibilities[i][1] == b)) ||
 ((possibilities[i][0] == b) && (possibilities[i][1] == a)))
				{
					//
					return 0;
				}
			}
			return 1;
		}
		else
		{
			//
			return 1;
		}

}

void routeKeeper(int a, int b)
{
	//
	if(routeCheck(a,b) == 1)
	{
		//
		possibilities.push_back({a,b});
	}
}

void createRouteMap(int start, int end)
{
	//
	temp = j;
	
	for(j=0; j<6; j++)
	{

		if(cubes[start-1][j]==end)   // if it is destination
		{
			//
			counter+=1;
			cout << "counter is: " << counter << endl;
			j++;
		}
		else if( (routeCheck(start, cubes[start-1][j])==1) && (cubes[start-1][j] != end) &&
 (cubes[start-1][j] != 0)  )
		{
			//
			routeKeeper(start, cubes[start-1][j]);
			for(row = possibilities.begin() ; row != possibilities.end() ; row++)
			{
				//
				for(col = row->begin(); col != row->end(); col++)
				{
					//
					cout << *col << ",";
				}
			}
			cout << endl;
			createRouteMap(cubes[start-1][j], end);
			possibilities.erase(possibilities.end());
		}
	}
	j=temp;
	
}


int main(int argc, char** argv) {

	counter = 0;
	createRouteMap(1, 15);
	cout<< counter << endl;

		
	system("pause");
	return 0;
}

[Ericool]

have you heard about graph nodes and uniform search , dijistra or a-star ?

[istemihan]

No I have not. However, I made a research and I think I can not apply that into my situation.

[ne555]

>. 1,2 2,4 4,3 3,1 1,5 5
there is no edge between 2 and 4, or between 3 and 1, or between 1 and 5.

> int cubes[15][6] = { {2,3,5,0,0,0}
I have no idea what you are trying to represent there.

[esolve]

what is that?

[istemihan]

@ne555 actually, it is what in the possibilities vector, the route between the corners. starts from first corner and tries to go the first element that it is tied to and these are 2,3 and 5. 0s are unrelated. goes from 1 to 2 so possibilities's firs element is {1,2}, and from 2 goes to 4 so second element is {2,4} and so on...

it works untill reaches to 8th element in cube, means 6th corner. I do not know why. you can exemine the createRouteMap function, I think you will understand.

[ne555]

> starts from first corner and tries to go the first element that it is tied to and these are 2,3 and 5
According to your drawing http://i.stack.imgur.com/Z2oaV.png 1 is connected to 2, 4 and 8

[ne555]

Limit the scope of your variables.
line 68 for(int j=0; j<6; j++) and you could get rid of lines 66 and 97


You are using a global variable `j' to iterate the list of neighbours. In each recursive call you are using the same variable, so in order to keep going from the previous place you've decided to use yet another global variable `temp' to store the value of `j'

your trick does not work because the recursion is not only 1 level depth, `temp' was being overwritting and then setting `j' to an incorrect value.

[istemihan]

@ne555 you are totally right, but how can I overcome this? uniform searchs are not useful for this situation because there is no sub levels in cube, all the corners are connected to each other there is ne hierrarchical structure.

[istemihan]

Solved!!!

I am sharing the final code that works correctly. I made a small change, instead of keeping the j of each iteration in global temp, I used jKeeper[15] which keeps each j of each iteration.

#include <iostream>
#include <vector>
#include <cmath>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

/*
possibilities will keep the possible combinations, routes like {1,4}{4,8}{8,7} etc till it arrives to 15
*/

vector< vector<int> > possibilities;

vector< vector<int> > possibilitiesUsed;

vector< vector<int> >::iterator row;

vector<int>::iterator col;

int jKeeper[15] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};


int cubes[15][6] = { {4,6,2,0,0,0}, {1,3,7,0,0,0}, {2,4,8,0,0,0}, {1,3,5,0,0,0},
 {4,6,8,0,0,0}, {1,5,7,0,0,0}, {2,6,8,0,0,0}, {3,5,7,9,10,11}, {8,12,15,0,0,0},
 {8,13,15,0,0,0}, {8,12,13,0,0,0}, {9,11,14,0,0,0}, {10,11,14,0,0,0},
 {12,13,15,0,0,0}, {9,10,14,0,0,0} };

int counterSet, i, j=0, temp, temp2, counter, sizeOfVec, depth=0;

int routeCheck(int a, int b)
{
	//
		//
		if(!possibilities.empty())
		{
			//
			for(i=0; i< (int)possibilities.size(); i++)
			{
				//
				if(((possibilities[i][0] == a) && (possibilities[i][1] == b)) ||
 ((possibilities[i][0] == b) && (possibilities[i][1] == a)))
				{
					//
					return 0;
				}
			}
			return 1;
		}
		else
		{
			//
			return 1;
		}

}

int routeCheck2(int a, int b)
{
	//
		//
		if(!possibilitiesUsed.empty())
		{
			//
			for(i=0; i< (int)possibilitiesUsed.size(); i++)
			{
				//
				if(((possibilitiesUsed[i][0] == a) && (possibilitiesUsed[i][1] == b))
 || ((possibilitiesUsed[i][0] == b) && (possibilitiesUsed[i][1] == a)))
				{
					//
					return 0;
				}
			}
			return 1;
		}
		else
		{
			//
			return 1;
		}

}

void routeKeeper(int a, int b)
{
	//

		possibilities.push_back({a,b});

	
}

void createRouteMap(int start, int end)
{
	//
	//temp = j;
	//
	for(j=0; j<6; j++)
	{
		jKeeper[depth] = j;
		if(cubes[start-1][j]==end)   // if it is destination
		{
			//
			counter+=1;
			cout << "counter is: " << counter << endl;
			j++;
		}
		else if( (routeCheck(start, cubes[start-1][j]) == 1) && (cubes[start-1][j] != end)
 && (cubes[start-1][j] != 0) )
		{
			//
			routeKeeper(start, cubes[start-1][j]);
			for(row = possibilities.begin() ; row != possibilities.end() ; row++)
			{
				//
				for(col = row->begin(); col != row->end(); col++)
				{
					//
					cout << *col << ",";
				}
			}
			cout << endl;
			//possibilitiesUsed.push_back({start, cubes[start-1][j]});
			depth+=1;			
			createRouteMap(cubes[start-1][j], end);
			depth-=1;
			j=jKeeper[depth];
			possibilities.erase(possibilities.end());
			
		}	
		
	}
	//possibilitiesUsed.clear();
	
	
}


int main(int argc, char** argv) {

	counter = 0;
	createRouteMap(1, 15);
	cout<< counter << endl;

		
	system("pause");
	return 0;
}

[ne555]

> I am sharing the final code that works correctly.
it is missing some paths, by instance

1,2,2,3,3,8,8,10,10,13,13,11,11,8,8,5,5,4,4,1,1,6,6,7,7,8,8,9,9,12,12,14,

they seem to be a little longer than the ones that are reported, wonder if you fell short on your `jKeeper' array

your code gives 1608 paths, making `j' local gives 1800 (there are no repetitions)



> I used jKeeper[15] which keeps each j of each iteration.
there is no need to do such trick. Just keep your variable locals, function calls will not affect them