9 Replies - 615 Views - Last Post: 07 April 2013 - 02:50 PM Rate Topic: -----

#1 Yash M Sawant  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 20-December 12

I am only able to get only one solution starting from 0,0

Posted 03 April 2013 - 03:18 AM

The problem is from the famous knight tour in a chess 8x8 usual grid.
The program wrote by me is able to get only one solution (open) from (0,0) and thus by symmetry (0,7) , (7,0) and (7,7) and hence i have four open solution.
What is the problem???
Is This A Good Question/Topic? 0
  • +

Replies To: I am only able to get only one solution starting from 0,0

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9572
  • View blog
  • Posts: 36,253
  • Joined: 12-June 08

Re: I am only able to get only one solution starting from 0,0

Posted 03 April 2013 - 05:38 AM

Quote

What is the problem???

You didn't code the rest of the solutions? We don't know since we haven't seen your code, or your explain how you tried to tackle the other solutions.
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3662
  • View blog
  • Posts: 11,466
  • Joined: 05-May 12

Re: I am only able to get only one solution starting from 0,0

Posted 03 April 2013 - 05:40 AM

It's a little hard to tell what the problem is without seeing your code, or pseudo code of how your code works.
Was This Post Helpful? 0
  • +
  • -

#4 Yash M Sawant  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 20-December 12

Re: I am only able to get only one solution starting from 0,0

Posted 03 April 2013 - 06:43 AM

I believe that rearranging the path may lead to another solution
In this program there is a use of stack data structure
So, Program starts with INITIALX and INITIALY both equal to zero for the 0th row and 0th column
CHESSBOARD[INITIALX][INITIALY] is set to 1 as the starting path in chess for knight
Push the stack with 0 value as the we follow 0 path for the position 1 but this is not necessary
it is placed for the convenience for the other path to be follow.
Now Helper(INITIALX,INITIALY) is called and control landed to the helper function
As you can see the first statement if(TOP==63) is not true solutioncompletiontoggle is not set to true, globalcount is the variable for counter how many times the helper is called during the solution getting process.
We follow path 1 if path 1 is valid path for the position INITIALX,INITIALY the path 1 is traversed and we push 1 to the global SOLUTIONSTACK and GridClear() clears the grid 8x8 according to the SOLUTIONSTACK
we then call recursive call to Helper(x-2,y+1) and Helper goes on executing PATH 1,2,3,4,5,6,7 or 8 till we got to a place in grid where there is no legal move for the any of the path so we delete the top of stack and follow the path immediately
follow the path where it had been reached a deadend.
Are you understanding this we follow path1 path2 ... in the ascending order
suppose we call recursive from path4 and on reaching the next recursive call no path satisfies so deletion of the stack i.e. 4 takes place and control reaches back at the end of path4 Helper(x+2,y+1);X
X is the postion where control reaches and next path i.e. path5 is checked and so on.
for INTIALX=INITIALY=0 we got solution
but for any other it takes almost infinite times.
Please, improve the logic of the program.
Thank You!
Yash M.Sawant

//
//  main.cpp
//  TourOfKnightInChess
//
//  Created by Yash M Sawant on 11/12/12.
//  Last Debugged Date: 14/12/12.

/*
    I believe that rearranging the path may lead to another solution
	In this program there is a use of stack data structure
	So, Program starts with INITIALX and INITIALY both equal to zero for the 0th row and 0th column
	CHESSBOARD[INITIALX][INITIALY] is set to 1 as the starting path in chess for knight
	Push the stack with 0 value as the we follow 0 path for the position 1 but this is not necessary 
	it is placed for the convenience for the other path to be follow.
	Now Helper(INITIALX,INITIALY) is called and control landed to the helper function 
	As you can see the first statement if(TOP==63) is not true solutioncompletiontoggle is not set to true, globalcount is the variable for counter how many times the helper is called during the solution getting process.
	We follow path 1 if path 1 is valid path for the position INITIALX,INITIALY the path 1 is traversed and we push 1 to the global SOLUTIONSTACK and GridClear() clears the grid 8x8 according to the SOLUTIONSTACK
	we then call recursive call to Helper(x-2,y+1) and Helper goes on executing PATH 1,2,3,4,5,6,7 or 8 till we got to a place in grid where there is no legal move for the any of the path so we delete the top of stack and follow the path immediately 
	follow the path where it had been reached a deadend.
	Are you understanding this we follow path1 path2 ... in the ascending order
	suppose we call recursive from path4 and on reaching the next recursive call no path satisfies so deletion of the stack i.e. 4 takes place and control reaches back at the end of path4 Helper(x+2,y+1);X  
	X is the postion where control reaches and next path i.e. path5 is checked and so on.
	for INTIALX=INITIALY=0 we got solution
	but for any other it takes almost infinite times.
	Please, improve the logic of the program.
	Thank You!
	Yash M.Sawant	

*/

#include <stdio.h>

#define CHESSGRID 64
int SOLUTIONSTACK[CHESSGRID];
int TOP=-1,INITIALX=0,INITIALY=0;
int CHESSBOARD[8][8]={0};
int globalcount=0;
bool solutioncompletiontoggle=false;
void StackPush(int );
void StackDel();
void Helper(int x,int y);
void GridClear();


#define PATH1 if(x-2<=7&&x-2>=0&&y+1<=7&&y+1>=0&&CHESSBOARD[x-2][y+1]==0&&solutioncompletiontoggle==false){StackPush(1);GridClear();Helper(x-2,y+1);}
#define PATH2 if(x-1<=7&&x-1>=0&&y+2<=7&&y+2>=0&&CHESSBOARD[x-1][y+2]==0&&solutioncompletiontoggle==false){StackPush(2);GridClear();Helper(x-1,y+2);}
#define PATH3 if(x+1<=7&&x+1>=0&&y+2<=7&&y+2>=0&&CHESSBOARD[x+1][y+2]==0&&solutioncompletiontoggle==false){StackPush(3);GridClear();Helper(x+1,y+2);}
#define PATH4 if(x+2<=7&&x+2>=0&&y+1<=7&&y+1>=0&&CHESSBOARD[x+2][y+1]==0&&solutioncompletiontoggle==false){StackPush(4);GridClear();Helper(x+2,y+1);}
#define PATH5 if(x+2<=7&&x+2>=0&&y-1<=7&&y-1>=0&&CHESSBOARD[x+2][y-1]==0&&solutioncompletiontoggle==false){StackPush(5);GridClear();Helper(x+2,y-1);}
#define PATH6 if(x+1<=7&&x+1>=0&&y-2<=7&&y-2>=0&&CHESSBOARD[x+1][y-2]==0&&solutioncompletiontoggle==false){StackPush(6);GridClear();Helper(x+1,y-2);}
#define PATH7 if(x-1<=7&&x-1>=0&&y-2<=7&&y-2>=0&&CHESSBOARD[x-1][y-2]==0&&solutioncompletiontoggle==false){StackPush(7);GridClear();Helper(x-1,y-2);}
#define PATH8 if(x-2<=7&&x-2>=0&&y-1<=7&&y-1>=0&&CHESSBOARD[x-2][y-1]==0&&solutioncompletiontoggle==false){StackPush(8);GridClear();Helper(x-2,y-1);}
			

int main()
{
	INITIALX=0;
	INITIALY=0;
	CHESSBOARD[INITIALX][INITIALY]=1;
	StackPush(0);
	Helper(INITIALX,INITIALY);
	printf("Deletion of Stack Counter %d",globalcount);
	GridClear();
	return 0;
}
/*
 @param x is the position x of the 8x8 Grid of the Chessboard
 @param y is the position y of the 8x8 Grid of the Chessboard
 */
void Helper(int x,int y)
{
	
	
	if(TOP==63)
		
	{
		solutioncompletiontoggle=true;
		return;
	}
	else
	{
		    PATH1
			PATH2
			PATH3
			PATH4
			PATH5
			PATH6
			PATH7
			PATH8
			if(solutioncompletiontoggle==false)
			{
	            StackDel();
				GridClear();
			    return;
            }
	}
}



/*
 @param item is the item to be inserted in the stack
 */
void StackPush(int item)
{

	*(SOLUTIONSTACK+(++TOP))=item;
}

void StackDel()
{
	*(SOLUTIONSTACK+TOP)=NULL;
	TOP--;
}
void GridClear()

{
	int x,y;

	x=INITIALX;
	y=INITIALY;
	for(int i=0;i<8;i++)
		for(int j=0;j<8;j++)
			CHESSBOARD[i][j]=0;
    
	CHESSBOARD[INITIALX][INITIALY]=1;
	for(int i=1;i<=TOP;i++)
	{
		switch(*(SOLUTIONSTACK+i))
		{
            case 1:	x=x-2;
				y=y+1;
				CHESSBOARD[x][y]=i+1;
				break;
            case 2:	x=x-1;
				y=y+2;
				CHESSBOARD[x][y]=i+1;
				break;
            case 3:	x=x+1;
				y=y+2;
				CHESSBOARD[x][y]=i+1;
				break;
            case 4: x=x+2;
				y=y+1;
				CHESSBOARD[x][y]=i+1;
				break;
            case 5: x=x+2;
				y=y-1;
				CHESSBOARD[x][y]=i+1;
				break;
            case 6: x=x+1;
				y=y-2;
				CHESSBOARD[x][y]=i+1;
				break;		
            case 7: x=x-1;
				y=y-2;
				CHESSBOARD[x][y]=i+1;
				break;
            case 8: x=x-2;
				y=y-1;
				CHESSBOARD[x][y]=i+1;
				break;
		}
		
	}
}

This post has been edited by modi123_1: 03 April 2013 - 06:47 AM
Reason for edit:: highlight the text and just click the 'code' button in the text editor

Was This Post Helpful? 0
  • +
  • -

#5 Yash M Sawant  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 20-December 12

Re: I am only able to get only one solution starting from 0,0

Posted 07 April 2013 - 10:42 AM

#include <stdio.h>

#define CHESSGRID 64
int SOLUTIONSTACK[CHESSGRID];
int TOP=-1,INITIALX=0,INITIALY=0;
int CHESSBOARD[8][8]={0};
int globalcount=0;
bool solutioncompletiontoggle=false;
void StackPush(int );
void StackDel();
void Helper(int x,int y);
void GridClear();


#define PATH1 if(x-2<=7&&x-2>=0&&y+1<=7&&y+1>=0&&CHESSBOARD[x-2][y+1]==0&&solutioncompletiontoggle==false){StackPush(1);GridClear();Helper(x-2,y+1);}
#define PATH2 if(x-1<=7&&x-1>=0&&y+2<=7&&y+2>=0&&CHESSBOARD[x-1][y+2]==0&&solutioncompletiontoggle==false){StackPush(2);GridClear();Helper(x-1,y+2);}
#define PATH3 if(x+1<=7&&x+1>=0&&y+2<=7&&y+2>=0&&CHESSBOARD[x+1][y+2]==0&&solutioncompletiontoggle==false){StackPush(3);GridClear();Helper(x+1,y+2);}
#define PATH4 if(x+2<=7&&x+2>=0&&y+1<=7&&y+1>=0&&CHESSBOARD[x+2][y+1]==0&&solutioncompletiontoggle==false){StackPush(4);GridClear();Helper(x+2,y+1);}
#define PATH5 if(x+2<=7&&x+2>=0&&y-1<=7&&y-1>=0&&CHESSBOARD[x+2][y-1]==0&&solutioncompletiontoggle==false){StackPush(5);GridClear();Helper(x+2,y-1);}
#define PATH6 if(x+1<=7&&x+1>=0&&y-2<=7&&y-2>=0&&CHESSBOARD[x+1][y-2]==0&&solutioncompletiontoggle==false){StackPush(6);GridClear();Helper(x+1,y-2);}
#define PATH7 if(x-1<=7&&x-1>=0&&y-2<=7&&y-2>=0&&CHESSBOARD[x-1][y-2]==0&&solutioncompletiontoggle==false){StackPush(7);GridClear();Helper(x-1,y-2);}
#define PATH8 if(x-2<=7&&x-2>=0&&y-1<=7&&y-1>=0&&CHESSBOARD[x-2][y-1]==0&&solutioncompletiontoggle==false){StackPush(8);GridClear();Helper(x-2,y-1);}
			

int main()
{
	INITIALX=0;
	INITIALY=0;
	CHESSBOARD[INITIALX][INITIALY]=1;
	StackPush(0);
	Helper(INITIALX,INITIALY);
	printf("Deletion of Stack Counter %d",globalcount);
        
	GridClear();
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){printf("%2d",CHESSBOARD[i][j]);
             }
            printf("\n");
        }
	return 0;
}
/*
 @param x is the position x of the 8x8 Grid of the Chessboard
 @param y is the position y of the 8x8 Grid of the Chessboard
 */
void Helper(int x,int y)
{
	
	
	if(TOP==63)
		
	{
		solutioncompletiontoggle=true;
		return;
	}
	else
	{
		    PATH1
			PATH2
			PATH3
			PATH4
			PATH5
			PATH6
			PATH7
			PATH8
			if(solutioncompletiontoggle==false)
			{
	            StackDel();
				GridClear();
			    return;
            }
	}
}



/*
 @param item is the item to be inserted in the stack
 */
void StackPush(int item)
{

	*(SOLUTIONSTACK+(++TOP))=item;
}

void StackDel()
{
	*(SOLUTIONSTACK+TOP)=NULL;
	TOP--;
}
void GridClear()

{
	int x,y;

	x=INITIALX;
	y=INITIALY;
	for(int i=0;i<8;i++)
		for(int j=0;j<8;j++)
			CHESSBOARD[i][j]=0;
    
	CHESSBOARD[INITIALX][INITIALY]=1;
	for(int i=1;i<=TOP;i++)
	{
		switch(*(SOLUTIONSTACK+i))
		{
            case 1:	x=x-2;
				y=y+1;
				CHESSBOARD[x][y]=i+1;
				break;
            case 2:	x=x-1;
				y=y+2;
				CHESSBOARD[x][y]=i+1;
				break;
            case 3:	x=x+1;
				y=y+2;
				CHESSBOARD[x][y]=i+1;
				break;
            case 4: x=x+2;
				y=y+1;
				CHESSBOARD[x][y]=i+1;
				break;
            case 5: x=x+2;
				y=y-1;
				CHESSBOARD[x][y]=i+1;
				break;
            case 6: x=x+1;
				y=y-2;
				CHESSBOARD[x][y]=i+1;
				break;		
            case 7: x=x-1;
				y=y-2;
				CHESSBOARD[x][y]=i+1;
				break;
            case 8: x=x-2;
				y=y-1;
				CHESSBOARD[x][y]=i+1;
				break;
		}
		
	}
}

This post has been edited by JackOfAllTrades: 07 April 2013 - 12:08 PM
Reason for edit:: Added code tags

Was This Post Helpful? 0
  • +
  • -

#6 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6107
  • View blog
  • Posts: 23,661
  • Joined: 23-August 08

Re: I am only able to get only one solution starting from 0,0

Posted 07 April 2013 - 12:10 PM

Holy mother of macros! Wouldn't touch that with a 10-foot pole!

When you post your code...USE CODE TAGS!!!

:code:
Was This Post Helpful? 0
  • +
  • -

#7 Yash M Sawant  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 20-December 12

Re: I am only able to get only one solution starting from 0,0

Posted 07 April 2013 - 01:44 PM

I m just new to this...
Mr. Jack haven't you tried to execute it..

I m just new to this...
Mr. Jack haven't you tried to execute it..
Was This Post Helpful? 0
  • +
  • -

#8 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9572
  • View blog
  • Posts: 36,253
  • Joined: 12-June 08

Re: I am only able to get only one solution starting from 0,0

Posted 07 April 2013 - 01:50 PM

More like you should try to programmaticly create the solution and not hard code into macros.
Was This Post Helpful? 0
  • +
  • -

#9 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6107
  • View blog
  • Posts: 23,661
  • Joined: 23-August 08

Re: I am only able to get only one solution starting from 0,0

Posted 07 April 2013 - 02:42 PM

No, I did not try to execute it. What you've created is a debugging NIGHTMARE with all those macros. Just for shits and grins, I tried to compile. It doesn't.

$ gcc -Wall -pedantic --std=c99 -omog mother_of_god.c 
mother_of_god.c:6: warning: missing braces around initializer
mother_of_god.c:6: warning: (near initialization for ‘CHESSBOARD[0]’)
mother_of_god.c:8: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘solutioncompletiontoggle’
mother_of_god.c: In function ‘Helper’:
mother_of_god.c:53: error: ‘solutioncompletiontoggle’ undeclared (first use in this function)
mother_of_god.c:53: error: (Each undeclared identifier is reported only once
mother_of_god.c:53: error: for each function it appears in.)
mother_of_god.c:53: error: ‘true’ undeclared (first use in this function)
mother_of_god.c:58: error: ‘false’ undeclared (first use in this function)
mother_of_god.c: In function ‘StackDel’:
mother_of_god.c:88: warning: assignment makes integer from pointer without a cast



Try fixing the warnings and errors.
Was This Post Helpful? 0
  • +
  • -

#10 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6107
  • View blog
  • Posts: 23,661
  • Joined: 23-August 08

Re: I am only able to get only one solution starting from 0,0

Posted 07 April 2013 - 02:50 PM

Guess I'm feeling masochistic today.

Your first warning is for this line:

int CHESSBOARD[8][8]={0};


This is a two-dimensional array, and you're only initializing one dimension. Try this:

int CHESSBOARD[8][8]={ {0}, {0} };


Your true/false problem I fixed by #include <stdbool.h>.

This problem:

mother_of_god.c:88: warning: assignment makes integer from pointer without a cast


is for this line:

*(SOLUTIONSTACK+TOP)=NULL;


SOLUTIONSTACK is an array of integers, but you're using NULL, which is not necessarily an integer. In this case it's a pointer. Instead of NULL use 0.

After fixing these and running, this is the result, which means nothing to me:

Deletion of Stack Counter 0 1385534 3361922
5447 2372023 417
3956334635182110
48534057241116 5
593245524126 912
444958256215 627
3160514229 81364
50433061146328 7




Fixing the output functions gave me this:


$ ./mog
Deletion of Stack Counter 0
 1 38 55 34  3 36 19 22 
54 47  2 37 20 23  4 17 
39 56 33 46 35 18 21 10 
48 53 40 57 24 11 16  5 
59 32 45 52 41 26  9 12 
44 49 58 25 62 15  6 27 
31 60 51 42 29  8 13 64 
50 43 30 61 14 63 28  7


Don't know if that's right or not; I was not a CS major and never did this problem.

This post has been edited by JackOfAllTrades: 08 April 2013 - 01:58 AM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1