GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 20-Mar-2005, 05:18
kai85 kai85 is offline
...is NOT a boy!
 
Join Date: Jan 2005
Posts: 58
kai85 is on a distinguished road

knight tour (chess program)


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 ....
  #2  
Old 20-Mar-2005, 05:41
kai85 kai85 is offline
...is NOT a boy!
 
Join Date: Jan 2005
Posts: 58
kai85 is on a distinguished road
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?
}






  #3  
Old 20-Mar-2005, 09:03
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold
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
  #4  
Old 20-Mar-2005, 12:30
WaltP's Avatar
WaltP WaltP is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Midwest US
Posts: 3,435
WaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to all
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.
__________________

Definition: Politics
Latin, from
poly meaning many and
tics meaning blood sucking parasites
-- Tom Smothers
  #5  
Old 21-Mar-2005, 01:40
kai85 kai85 is offline
...is NOT a boy!
 
Join Date: Jan 2005
Posts: 58
kai85 is on a distinguished road

accessibility?


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 ....
  #6  
Old 22-Mar-2005, 01:46
kai85 kai85 is offline
...is NOT a boy!
 
Join Date: Jan 2005
Posts: 58
kai85 is on a distinguished road
10 characters long?
  #7  
Old 23-Mar-2005, 01:55
LuciWiz's Avatar
LuciWiz LuciWiz is offline
Moderator
 
Join Date: Jul 2004
Location: Cluj-Napoca (Romania)
Posts: 1,037
LuciWiz is just really niceLuciWiz is just really niceLuciWiz is just really niceLuciWiz is just really nice
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
__________________
Please read these Guidelines before posting on the forum

"A person who never made a mistake never tried anything new."
Einstein
  #8  
Old 24-Mar-2005, 09:28
kai85 kai85 is offline
...is NOT a boy!
 
Join Date: Jan 2005
Posts: 58
kai85 is on a distinguished road
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?
  #9  
Old 24-Mar-2005, 09:41
LuciWiz's Avatar
LuciWiz LuciWiz is offline
Moderator
 
Join Date: Jul 2004
Location: Cluj-Napoca (Romania)
Posts: 1,037
LuciWiz is just really niceLuciWiz is just really niceLuciWiz is just really niceLuciWiz is just really nice
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
__________________
Please read these Guidelines before posting on the forum

"A person who never made a mistake never tried anything new."
Einstein
  #10  
Old 25-Mar-2005, 06:48
iamsodumb iamsodumb is offline
New Member
 
Join Date: Mar 2005
Location: Mumbai
Posts: 27
iamsodumb is on a distinguished road
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
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

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 13: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 14:31
Need help with a C program (Long) McFury C Programming Language 3 29-Apr-2004 20:06

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 10:43.


vBulletin, Copyright © 2000 - 2017, Jelsoft Enterprises Ltd.