Programming Problem

[jmcoreymv]

Im taking AP Comp Sci, and I got passed this assignment where I have to make a knight move around a chessboard from any given starting point and get as far as it could. I did that, but then I got to thinking, how would I program it to get to all the squares on the board. One way I came up with that I was pretty sure would work, isnt working correctly, maybe somebody can see something wrong with my code

#include<iostream.h>
#include<apmatrix.h>

void PrintMatrix(apmatrix<int>grid);//displays the matrix on the screen
void StartingPoint();//gathers the starting position from the user
void TraceMove(apmatrix<int>board,int row,int col);//defines the recursion algorithem

const int MAXROW=8,MAXCOL=8;//sets the dimension for the board
int counter=0;//starts the counter of the current square position
int x,y;//initializes x and y variables (current location of knight)

int main(){
apmatrix<int>board(9,9,0);//initializes a 9x9 matrix to 0 values
StartingPoint();
TraceMove(board,x,y);
return(0);
}
void StartingPoint(){
cout<<"Please enter starting row (1-"<<MAXROW<<"): ";
cin>>x;
cout<<"Please enter starting column (1-"<<MAXCOL<<"): ";
cin>>y;
}
void PrintMatrix(apmatrix<int>grid){
for(int row=1;row<=MAXROW;row++){
for(int col=1;col<=MAXCOL;col++){
if(grid[row][col]<=9)
cout<<"0"<<grid[row][col]<<" ";
else
cout<<grid[row][col]<<" ";}
cout<<endl;}

}

void TraceMove(apmatrix<int>board,int row,int col){
if(row>=1 && row<=MAXROW && col>=1 && col<=MAXCOL){//boundary check
if(board[row][col]==0){//check to see if its been used
board[row][col]=++counter;
if(counter==64)
PrintMatrix(board);
else{
TraceMove(board,row+1,col-2);
TraceMove(board,row+2,col-1);
TraceMove(board,row+2,col+1);
TraceMove(board,row+1,col+2);
TraceMove(board,row-1,col+2);
TraceMove(board,row-2,col+1);
TraceMove(board,row-2,col-1);
TraceMove(board,row-1,col-2);
}
}
}
}

 

[blahblah99]

This problem is a more of a linear algebra problem than a programming problem because once you figure out the state-transistion matrix, you can implement the function easily and call it recursively until you run into an ending condition (ie, all spaces on board have been touched by the knight). Using this method, you can control the knight into moving to any space with least number of moves.



or you can do it by brute force. Since the knight can only move in the form of an L, it has 8 directions to move. Have a variable called knightmove[xsize][ysize] in which each element of that 2dim array is 1 if the knight has landed on that space, 0 otherwise and another variable called current[x][y] for current position.

Then pick another number from 1-8 to see which direction the knight is going to move. Check if its a valid space on the board and that knightmove[x][y] isn't 1. If its not 1, move it into that space and update current[x][y].

I havn't looked at your code cause I'm too lazy to read through all that swahili but I'm assuming that what I said above is what your trying to implement in that code. I'd personally would go with the first method since it you'll know where the knight will be at all times.

 

[blahblah99]

This problem is a more of a linear algebra problem than a programming problem because once you figure out the state-transistion matrix, you can implement the function easily and call it recursively until you run into an ending condition (ie, all spaces on board have been touched by the knight). Using this method, you can control the knight into moving to any space with least number of moves.



or you can do it by brute force. Since the knight can only move in the form of an L, it has 8 directions to move. Have a variable called knightmove[xsize][ysize] in which each element of that 2dim array is 1 if the knight has landed on that space, 0 otherwise and another variable called current[x][y] for current position.

Then pick another number from 1-8 to see which direction the knight is going to move. Check if its a valid space on the board and that knightmove[x][y] isn't 1. If its not 1, move it into that space and update current[x][y].

I havn't looked at your code cause I'm too lazy to read through all that swahili but I'm assuming that what I said above is what your trying to implement in that code. I'd personally would go with the first method since it you'll know where the knight will be at all times.

 

[blahblah99]

This problem is a more of a linear algebra problem than a programming problem because once you figure out the state-transistion matrix, you can implement the function easily and call it recursively until you run into an ending condition (ie, all spaces on board have been touched by the knight). Using this method, you can control the knight into moving to any space with least number of moves.



or you can do it by brute force. Since the knight can only move in the form of an L, it has 8 directions to move. Have a variable called knightmove[xsize][ysize] in which each element of that 2dim array is 1 if the knight has landed on that space, 0 otherwise and another variable called current[x][y] for current position.

Then pick another number from 1-8 to see which direction the knight is going to move. Check if its a valid space on the board and that knightmove[x][y] isn't 1. If its not 1, move it into that space and update current[x][y].

I havn't looked at your code cause I'm too lazy to read through all that swahili but I'm assuming that what I said above is what your trying to implement in that code. I'd personally would go with the first method since it you'll know where the knight will be at all times.

 

[Burner]

I really don't feel like looking at your code, but this is probably the easiest way unless you want to figure out the matrix stuff. Keep a list of places you have been to. Look around your current position and see where you can go. If you can go somewhere then go there. Once you can't go to a new place in 1 move, then see what places you can goto in two moves, after that 3 and 4 and so on until you have covered the entire board.

 

[m0ti]

The solution is typical back tracking...

You've got an 8x8 array representing the board filled with zeros.

Here's some pseudo code, you call the function with your starting coordinates

int numVisited = 0;
Stack solution;

int NextMove(int x, int y) {
if (x<0 || x > 7 || y < 0 || y > 7 || array[x][y] == 1)
return 0; // alredy visited this position or illegal position
else {
array[x][y] = 1;
numVisited++;
}
if (numVisited == 64) { // yeah, ugly, Global Variable, but you can fiddle around with the implementaion, it's 4 AM just writing some quick dirty code. do it in C++ or Java or something and you can put it all inside an object
push (x,y) onto solution;
return 1;
}
for each knight movement from the current position to (x1,y1) // legal or not
if (nextMove(x1,y1) == 1) {
push(x,y) onto solution;
return 1;
}
array[x][y] = 0; // backtracking from this position. the current state is a dead end, so going back to the previous legal state.
numVisited--; // meaning that we will have to revisit this particular position sometime in the future.
return 0; // no solution found in this state
}

There you go. It automatically searches through the whole board, stopping when a solution is found. By the way, you are guaranteed to find a solution since one does exist, and your starting position in the sequence is irrelevent. Hope that this helps.

 

[m0ti]

I didn't really take a look at your code the first time. What you forgot to do is undo your steps at the end. After all if in the current state of the board there is no solution, then we'd better leave the current position free, so that other states can try getting there through this position. That's why your code isn't working. In your code, you only continue from a square if its value is non zero. Since you only ever change it from zero to something else, and never go back (and backup the counter, too, btw), you can only examine each square at most once.

Good luck.

 

[Sahakiel]

Hm... I went up to C++ and basically called it quits after. Too much burnout. I can somewhat read the code, but I have a few questions:

apmatrix<int>board(9,9,0);//initializes a 9x9 matrix to 0 values
why initialize to 9x9 when MAXROW and MAXCOL is 8 and 8?
Also, I think it basically makes always true the statement " if(grid[row][col]<=9) " and never gets to your endl; If you were trying to catch it at index 10, I do believe with a for loop, it'll never execute if it's not true and since you cut it off at 8, it won't reach 9 anyways. A do-while, however, will <edit> execute the last false statement it receives </edit>.
Your double for's for displaying the matrix start at index 1,1 which isn't the first index, 0,0. I'm pretty sure arrays start at index 0.
As for your TraceMove function, I'm getting a headache and flashbacks to 52 hour programming sprees followed by burnout. All I'm gonna ask is why does a recursive function call itself 8 times in a row? If you're scanning the 8 ways a knight can move, you're gonna want to call them one at a time and kill the whole branch if that one function works. Recursive functions are highly memory intensive, too. If you really want to use a recursive function, the best way may be to make TraceMove return a 1 if false. Then, you do If(TraceMove(board,row+1,col-2)) { If TraceMove(board,row+2,col-1) {If TraceMove(board,row+2,col+1)... and so forth. Very long and very big headache.
My $0.02.

 

[m0ti]

Yeah, I didn't notice that either.

In C style syntax, array indices start from 0. Therefore, you should have declared your array as being 8 by 8 and legal values are from 0 to 7.

Actually, you do need to go over the 8 recursive calls with ifs in between them as noted. It's completely equivalent to the "for each knight movement from the current position to (x1,y1)" I wrote, which is albeit in pseudo-code (and more readable), though it is easily implemented in other languages in that form (LISP for example). In any case, let us know if you've had any success.

 

[jmcoreymv]

As far as the array indexing goes, I know it starts at 0 but the assignment specifically said make it a 9x9 and just dont use the 0 indexes, so thus I check for and print out only 1-8 indexes. I dont know why they do it like that, but i have to follow it because my teacher is anal. Im kind of lost as far as what you guys are saying, I tried to localize the counter variable to its no longer global but it still isnt working right. The board is not referenced either, everytime the recursive function calls itself, it makes a copy of the board and should only print the last copy that gets to 64. Heres the new thing I tried that didnt work.

void TraceMove(apmatrix<int>board,int row,int col, int counter){
if(row>=1 && row<=MAXROW && col>=1 && col<=MAXCOL){//boundary check
if(board[row][col]==0){//check to see if its been used
board[row][col]=++counter;
if(counter==64){
PrintMatrix(board);
}else{
TraceMove(board,row+1,col-2,counter);
TraceMove(board,row+2,col-1,counter);
TraceMove(board,row+2,col+1,counter);
TraceMove(board,row+1,col+2,counter);
TraceMove(board,row-1,col+2,counter);
TraceMove(board,row-2,col+1,counter);
TraceMove(board,row-2,col-1,counter);
TraceMove(board,row-1,col-2,counter);
}
}
}
}

 

[Sahakiel]

Quite frankly, it's a bit difficult to debug another programmer's code. Our minds are wired differently. But, from my standpoint, and given how I would implement this idea, I see a problem in your TraceMove being called 8 times in a row. If one of those calls results in a successful move, I do not see why you would want to check the others. I can only guess at the output you're getting, but I think that your TraceMove is checking all 8 possibilites and moving on each one that works. This would result in your first move hitting, say, 8 moves (middle of board) to 7 moves and so forth, each move resulting in an independent knight. I seriously think you need to seperate the 8 TraceMove calls with nested if's or if-else's. Actually, for loops may be better. Alter your TraceMove to a for loop to scan all 8 moves. Then, if all 8 are filled, TraceMove to each one to check those. You would have to modify TraceMove to accept a second counter which tells it how many moves ahead to check. So, imagine on the first scan, TraceMove with a counter 1 and it comes up negative, all moved to before. So, you increment counter and TraceMove 2, which would call up the first possible move, move there, scan from there, and return a result. If the result is, yes, found a path, return a 0. Then, if it hasn't found a result, you return a 1 which can be used in an If statement to see if the parent function should call another child. The main thing you want to avoid is calling recursive functions over and over regardless of whether the desired results has been found.

On another note, if I'm following the sequence correctly, your knight may get stuck somewhere and not be able to get out. It would take a concrete mathematical proof to support or disprove that, and it's really way out of my league.

 

[m0ti]

Ok, here we go, no stack, incredibly stupid way of handling arrays (make it 9x9??? don't use the 0's???).

Btw, it's been a while since I've written C++, more a Java person myself, so there'll be some minor bugs to fix no doubt.

And you should probably make the code a little nicer to read, too.

In your main, after you've gotten the starting location X,Y, call NextMove(X,Y,1). After that, do your print board where the movements are stored in solution (1st index to 64th index).

int numVisited = 0;
int solution[65][3]; // not using 0 index here either! (mumbles G-d Damn waste of space!)

int NextMove(int x, int y, int positionInSolution) {
if (x<1 || x > 8 || y < 1 || y > 8 || array[x][y] == 1)
return 0; // alredy visited this position or illegal position (changed to support 9x9 no 0 index)

array[x][y] = 1;
numVisited++;

if (numVisited == 64)
return push(x,y,positionInSolution);

positionInSolution;
if (nextMove(x+1, y+2, positionInSolution+1) == 1)
return push(x,y,positionInSolution);
if (nextMove(x+1, y-2, positionInSolution+1) == 1)
return push(x,y,positionInSolution);
if (nextMove(x-1, y+2, positionInSolution+1) == 1)
return push(x,y,positionInSolution);
if (nextMove(x-1, y-2, positionInSolution+1) == 1)
return push(x,y,positionInSolution);
if (nextMove(x+2, y+1, positionInSolution+1) == 1)
return push(x,y,positionInSolution);
if (nextMove(x+2, y-1, positionInSolution+1) == 1)
return push(x,y,positionInSolution);
if (nextMove(x-2, y+1, positionInSolution+1) == 1)
return push(x,y,positionInSolution);
if (nextMove(x-2, y-1, positionInSolution+1) == 1)
return push(x,y,positionInSolution);

array[x][y] = 0; // backtracking from this position. the current state is a dead end, so going back to the previous legal state.
numVisited--; // meaning that we will have to revisit this particular position sometime in the future.
return 0; // no solution found in this state
}

int push(int x, y, positionInSolution) {
//push (x,y) onto solution
solution[positionInSolution][1] = x; // starting at index 1 and not 0
solution[positionInSolution][2] = y;
return 1;
}