knight tour (chess program)

kai85 · #1 20-Mar-2005, 05:18

Hi I’m trying to write this program for the knight’s tour...(surly u’ve heard of it?)
First things first... I know it’s long , don’t lose interest because of this topics length!
(it’s a nice problem for all u problem seekers out there.... I dunno maybe it’s easy but......)
Well what my program does is as follows:
It receives the column and row to move the knight to at the beginning..and then it chooses the other moves ,and fills up the chess board with the knights moves and prints the output.
But how does it choose these moves? Well each time it should choose the best chess house(the best chess house is the the house that can be least accessed by other houses..(don’t give up yet.. ill try to explain better...)

THE BEST CHESS HOUSE:

I’ve defined an 8*8 array called accessibility ! the value in each of the accessibility elements is the amount of elements which can access that certain element(element==chess house) (for example accessibility [0][0] = 2,this means that it can only be accessed by the knight from 2 other houses ,accessibility[2][1] and accessibility [1][2].)
So the program should choose the least accessible house each time to move the knight to.. but the problem is what should it do if two houses have the same accessibility value? Which should it choose?
Simple it has to choose the house that should the knight be moved to that house,in its next move has the least accessibility house to choose from.
Well I hope I explained good enough....
Now the problem I have is in this function I’ve defined ... I don’t know whether I should have a base case in it !it works kinda like a recursive function...im compiling with vc++ and the error it give is stack overflow ....

kai85 · #2 20-Mar-2005, 05:41

this is my first time in sending a program... lets see if it works

CPP / C++ / C Code:

#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
int f( int,  int,const int [][8],const int [][8], int [],int []);
int p,q;
int main()
{
	int h=1,lowest1,lowest2;
	int accessibility[8][8]={{2,3,4,4,4,4,3,2},
	{3,4,6,6,6,6,4,3},
	{4,6,8,8,8,8,6,4},
	{4,6,8,8,8,8,6,4},
	{4,6,8,8,8,8,6,4},
	{4,6,8,8,8,8,6,4},
	{3,4,6,6,6,6,4,3},
	{2,3,4,4,4,4,3,2}};
	int array[8][8]={0};
	int horizontal[]={2,1,-1,-2,-2,-1,1,2};//the vertical and horizontal 
	                                       //arrays help make the l shaped moves.
        int vertical[]={-1,-2,-2,-1,1,2,2,1};
	int currentrow,currentcolumn,x,y,movenumber;
	
	cout<<"Enter a row and a column for the horse's start position:"<<endl;
	cin>>currentrow>>currentcolumn;
	array[currentrow][currentcolumn]=h,
         accessibility[currentrow][currentcolumn] -=1;
	
	
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<array[i][j]<<' ';
		if(j==7)
			cout<<endl<<endl;}

	}
	
	
	for (int z=0;z<63;z++)//this step is repeated 63 times .. for the 63 
                                      // moves in which the program has to choose the 
			              //least accessible chesshouse
	
	{
		int lowest=9;
		for(int i=0;i<8;i++){
			movenumber=i;
			x=currentrow+vertical[movenumber] 
			 y= currentcolumn+horizontal[movenumber];
			
			if(x>-1 && x<8 && y>-1 && y<8)   //so the knight doesn't 
				                                      //go out of the  chess 
                                                                     //board
			{
			 	
                            if(array[x][y] == 0 && accessibility[x][y] <= lowest)
//to make sure the knight  doesn't go to the same houses
				
				{                                                   
					
					
					
				    if (accessibility[x][y] == lowest)
                    //if the accessibility elements have the same value
					{
{						lowest1=f(x,y,accessibility,array,horizontal, vertical);//call to the f function
						                                                        //to find the house that should 
						                                                        //the horse be moved to, has the least 
						                                                        //accessibility option in it's next move!
lowest2=f(p,q, accessibility,array,horizontal, vertical);
						if (lowest1 < lowest2)
						lowest=accessibility[x][y],	p=x,q=y;
					
					}
			     
					
				    else	lowest=accessibility[x][y], p=x,q=y;
				}	   
				
				
			}	
		}
	
	
		
		array[p][q]=h+1,h++,accessibility[p][q] -=1,
                currentrow=p,currentcolumn=q;

	}
   
	
	
	cout<<endl<<endl<<endl<<endl;
	for(i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<array[i][j]<<' ';
		if(j==7)
			cout<<endl<<endl;}

	}

	cout<<endl<<endl<<endl<<endl;
	for(i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<accessibility[i][j]<<' ';
		if(j==7)
			cout<<endl<<endl;}

	}


   getch();
   return 0;
}


int f(int a,int b,const int accessibility[][8],const int array[][8],int horizontal[],int vertical[]){
	int x1,y1,lowest1=9,p1,q1,movenumber,lowest2,lowest3;	
	
	for(int i=0;i<8;i++){
			movenumber=i;
			x1=a+vertical[movenumber];
			y1=b+horizontal[movenumber];
			
			if(x1>-1 && x1<8 && y1>-1 && y1<8){
				
				if(array[x1][y1] == 0 && accessibility[x1][y1] <= lowest1){
					
					
					
					if (accessibility[x1][y1] == lowest1){

						lowest2=f(x1,y1,accessibility,array,horizontal, vertical);
						lowest3=f(p1,q1,accessibility,array,horizontal, vertical);
						if (lowest2 < lowest3)
						lowest1=accessibility[x1][y1],	p1=x1,q1=y1;
					
					}
			     
					
				    else	lowest1=accessibility[x1][y1], p1=x1,q1=y1;
				}	   

	


			}
	}
return lowest1;//should i make a base case here or is this enough?
}

davekw7x · #3 20-Mar-2005, 09:03

Quote:

Originally Posted by kai85

this is my first time in sending a program... lets see if it works

First post and you used code tags. Very satisfactory.

However, the code you posted will not compile. Lots of fatal errors. Check it again. Copy-and-paste from your text editor directly into the post.

Regards,

Dave

WaltP · #4 20-Mar-2005, 12:30

Another thing I'd recommend, use chess terms. The 8x8 layout is a board, each "house" is a square. This will remove the need for lengthy explanations of your terms -- everyone knows what a board is, noone's ever heard of an accessibility.

Ask specific questions, post the code that relates to the question (not all 100 lines we have to search thru) and explain in detail
1) what the code should do
2) what the code doesn't do
3) where you think the problem might be. Comments in the posted code help.

If you get errors during compile, start fixing them from the top down, 2-3 at a time. Many times fixing one thing will remove 70% of the errors.

Hope this helps.

kai85 · #5 21-Mar-2005, 01:40

Hi WaltP , thanx but as I’d said it was my first time ... I was actually more worrid about the tags....anyway here’s the answers I’ve come up with:

Quote:

1) what the code should do?
2) what the code doesn't do
3) where you think the problem might be. Comments in the posted code help.

I’d rather answer from top to bottem,well the problem is definitely in the f function I’ve defined....now I don’t know whether I should have a base case in it or not
Ok I’ll try to explain :

CPP / C++ / C Code:

if(array[x][y] == 0 && accessibility[x][y] <= lowest)
if(accessibility[x][y]= =lowest)
{
   lowest1=f(x,y,accessibility,array,horizontal, vertical);//call to the f function
                                                                    //to find the house that should 
                                                                    //the horse be moved to, has the least 
                                                                    //accessibility option in it's next move!
lowest2=f(p,q, accessibility,array,horizontal, vertical);
            if (lowest1 < lowest2)
            lowest=accessibility[x][y],  p=x,q=y;
          
          }

Well what t his piece of code does is that it first checks to see whether the knight has been in the array[x][y] square before or not(it shouldn’t go to the same squares)
And then it checks to see whether the [x][y] element in the accessibility
(BTW these are just names for arrays, what do u suppose I call this array? Would u rather I call it x, or y or ...???!!!)
array has the same value as lowest , if it does then it should check to if the knight was actually moved to that square then in its next move would it have a better option or not? thats where I call the f function 
now what this function does is that it supposes the knight was moved to that square now its gonna try to find the least accessible square on the board,which means the least element in the accessibility array ! and then returns that value to the main function so that its compared with lowest 2(lowest 1 is compared with lowest 2, the smaller one is to lowest)
The BIG problem is this: what if,the f function finds 2 elements which have the same value?then it should call itself again ... this why I think its gonna be a recursive one but I’m in doubts as to whether I should have a base case in it and if I did what would it be?
Sorry this post was soooooooooooooooo long, BTW I thought if I sent u the complete code then it would be better ... but the actuall problem is in the f function!!!!!!!!!!!!
And about the chess terms, I was gonna visit a chess site and find the correct terms to use, and i did but.....
if theres anything else u think I shouldve mentioned then ....

kai85 · #6 22-Mar-2005, 01:46

10 characters long?

LuciWiz · #7 23-Mar-2005, 01:55

Walt suggested you correct your errors from the top down. When compiling your code, this is the first error I get:

Code:

d:\Work\test\chess\chess.cpp(54): error C2146: syntax error : missing ';' before identifier 'y'

And I get it at this line:

CPP / C++ / C Code:

		for(int i=0;i<8;i++){
			movenumber=i;
			x=currentrow+vertical[movenumber]
			y= currentcolumn+horizontal[movenumber]; // this one

Fix it, and we'll take it one by one. Maybe after you fix the syntax errors, we can move to the logic.

Best regards,
Lucian

kai85 · #8 24-Mar-2005, 09:28

hi, thanks for replying lucian,
well the thing is i seem to have forgotten to put the semi colon after

CPP / C++ / C Code:

x=currentrow+vertical[movenumber]

in my post here, but in the actual code ,it's there...

but this time i compiled it and i didn't get any errors!

its just that the program doesn't execute(correct term?) properly,after i enter the row and column for the knights start position(lets suppose 0,0) i get the message
"press any key to continue..."
???
well?

LuciWiz · #9 24-Mar-2005, 09:41

Well, OK, but after fixing this, I still get errors. Post your error-free code. And please format it right. It's hard to follow as it is now. Also, please specify what input you want to give your program and the results you expect.

Best regards,
Lucian

iamsodumb · #10 25-Mar-2005, 06:48

This one should compile
Three }s were missing around line 110-115

CPP / C++ / C Code:

#include<iostream>
//#include<conio.h>
#include<iomanip.h>
using namespace std;
int f( int,  int,const int [][8],const int [][8], int [],int []);
int p,q;
int main()
{
  int h=1,lowest1,lowest2;
  int accessibility[8][8]={{2,3,4,4,4,4,3,2},
  {3,4,6,6,6,6,4,3},
  {4,6,8,8,8,8,6,4},
  {4,6,8,8,8,8,6,4},
  {4,6,8,8,8,8,6,4},
  {4,6,8,8,8,8,6,4},
  {3,4,6,6,6,6,4,3},
  {2,3,4,4,4,4,3,2}};
  int array[8][8]={0};
  int horizontal[]={2,1,-1,-2,-2,-1,1,2};//the vertical and horizontal
                                         //arrays help make the l shaped moves.
        int vertical[]={-1,-2,-2,-1,1,2,2,1};
  int currentrow,currentcolumn,x,y,movenumber;

  cout<<"Enter a row and a column for the horse's start position:"<<endl;
  cin>>currentrow>>currentcolumn;
  array[currentrow][currentcolumn]=h,
         accessibility[currentrow][currentcolumn] -=1;


  for(int i=0;i<8;i++){
    for(int j=0;j<8;j++){
      cout<<array[i][j]<<' ';
    if(j==7)
      cout<<endl<<endl;}

  }


  for (int z=0;z<63;z++)//this step is repeated 63 times .. for the 63
                                      // moves in which the program has to choose the
                    //least accessible chesshouse

  {
    int lowest=9;
    for(int i=0;i<8;i++){
      movenumber=i;
      x=currentrow+vertical[movenumber];
       y= currentcolumn+horizontal[movenumber];

      if(x>-1 && x<8 && y>-1 && y<8)   //so the knight doesn't
                                              //go out of the  chess
                                                                     //board
      {
                            if(array[x][y] == 0 && accessibility[x][y] <= lowest)
//to make sure the knight  doesn't go to the same houses

        {



            if (accessibility[x][y] == lowest)
                    //if the accessibility elements have the same value
          {
{            lowest1=f(x,y,accessibility,array,horizontal, vertical);//call to the f function
                                                                    //to find the house that should
                                                                    //the horse be moved to, has the least
                                                                    //accessibility option in it's next move!
lowest2=f(p,q, accessibility,array,horizontal, vertical);
            if (lowest1 < lowest2){
            lowest=accessibility[x][y];  p=x;  q=y;

            }


            else  lowest=accessibility[x][y];  p=x;  q=y;
        }


      }
    }



    array[p][q]=h+1,h++,accessibility[p][q] -=1,
                currentrow=p,currentcolumn=q;

  }



  cout<<endl<<endl<<endl<<endl;
  for(i=0;i<8;i++){
    for(int j=0;j<8;j++){
      cout<<array[i][j]<<' ';
    if(j==7)
      cout<<endl<<endl;}

  }

  cout<<endl<<endl<<endl<<endl;
  for(i=0;i<8;i++){
    for(int j=0;j<8;j++){
      cout<<accessibility[i][j]<<' ';
      if(j==7)
      cout<<endl<<endl;}
      }
    }
  }

//   getch();
   return 0;
}


int f(int a,int b,const int accessibility[][8],const int array[][8],int horizontal[],int vertical[]){
  int x1,y1,lowest1=9,p1,q1,movenumber,lowest2,lowest3;

  for(int i=0;i<8;i++){
      movenumber=i;
      x1=a+vertical[movenumber];
      y1=b+horizontal[movenumber];

      if(x1>-1 && x1<8 && y1>-1 && y1<8){

        if(array[x1][y1] == 0 && accessibility[x1][y1] <= lowest1){



          if (accessibility[x1][y1] == lowest1){

            lowest2=f(x1,y1,accessibility,array,horizontal, vertical);
            lowest3=f(p1,q1,accessibility,array,horizontal, vertical);
            if (lowest2 < lowest3)
            lowest1=accessibility[x1][y1],  p1=x1,q1=y1;

          }


            else  lowest1=accessibility[x1][y1], p1=x1,q1=y1;
        }




      }
  }
return lowest1;//should i make a base case here or is this enough?
}

well as far as the logic is concerened... I leave it to experts

Arjun Arikeri

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 08:44
[TUTORIAL] Calling an external program in C (Linux)	dsmith	C Programming Language	4	22-Apr-2005 14:30
fltk-2.0 cvs	Plumb	FLTK Forum	20	13-Nov-2004 08:10
Knight tour (arrays help needed)	dilmv	C++ Forum	7	18-Oct-2004 15:31
Need help with a C program (Long)	McFury	C Programming Language	3	29-Apr-2004 21:06

knight tour (chess program)

accessibility?