1. Stack Overflow

So I'm doing a pretty easy assignment to figure out what's the minimum amount of steps required for a Knight Piece in chess to get to a certain point in the grid.

the input file gives me the size of the grid, starting row,starting column, ending row, ending column.

So I chose to do breadth first search to do this.

I also created a struct called coordinates so that I can save the possible ways the knight can move from the current position and I put them into a queue.

However, using this huge input file my code always gets a stack overflow when my queue has around 12794 inserted.

The code is really simple, the bulk of it is enqueing the different possible ways of the knight moving

row = A, Column = B
(A-2,B-1),(A-2,B+1)
(A+2,B-1),(A+2,B+1)
(A-1,B-2),(A+1,B-2)
(A-1,B+2),(A+1,B+2)

here's the code

[C] knight - Pastebin.com

also here's the input file, name it goldknight.in

goldknight.in - Pastebin.com

You'll notice the stack overflow on the 3rd case

I think that it might be that i'm allocating it wrong or that the memory is running out and I need to free up the space not being used.

Help =)

2. Anyone ?

3. Knight's Tour works on a standard chess board. Have you entertained the idea that non-standard boards may not have a solution? Pastebin is down right now apparently. You could have just posted your code here, and you'd have had people actually look at it. That is why we have code tags after all.

Quzah.

4. Code:
```#include <stdlib.h>
#include <stdio.h>

struct coordinates{

int moves;
int row;
int column;
struct coordinates* next;
struct coordinates* previous;

}coordinates;

int gridSize,C1,C2,R1,R2,amountOfMoves;
int queueAmount=0;
struct coordinates* queue;
struct coordinates* queueEnd;

void queuePosibleMoves(int,int,int);
void startDequeingCheck();

main(){
int i,amountOfTestCases;
FILE* fp;
FILE* fout;

fp= fopen("goldknight.in","r");
fout = fopen("goldknight.out","w");

fscanf(fp,"%i",&amountOfTestCases);

for(i=0;i<amountOfTestCases;i++){
fscanf(fp,"%i",&gridSize);
fscanf(fp,"%i",&R1);
fscanf(fp,"%i",&C1);
fscanf(fp,"%i",&R2);
fscanf(fp,"%i",&C2);

queue = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd = queue;

queuePosibleMoves(R1,C1,1);

printf("Case #%i: %i\n\n",i+1,amountOfMoves);
queueAmount=0;

}

return 0;
}

void queuePosibleMoves(int currentRow,int currentColumn,int moves){
struct coordinates* temp;
struct coordinates* temp2;
int p=0;

if(queueAmount >1){
temp2 = queue;
queue = queue->next;
//free(temp2);
}

// This will do all 8 possible ways

//creates the queue if there is no queue
if(queueEnd == queue){
queue->moves = moves;
queue->row = currentRow-2;
queue->column = currentColumn-1;
temp = (struct coordinates*)malloc(sizeof(coordinates));
queue->next = temp;
queueEnd->next->previous  = queueEnd;
queueEnd = temp;
p = 1;
queueAmount++;
}

//p is the indicator that the queue does exist
if(p == 0){
if(currentRow-2 > 0 && currentRow-2 <= gridSize && currentColumn-1 > 0 && currentColumn-1 <= gridSize){
temp = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd->moves = moves;
queueEnd->row = currentRow-2;
queueEnd->column = currentColumn-1;
queueEnd->next = temp;
queueEnd->next->previous = queueEnd;
queueEnd = temp;
queueAmount++;
}
}

if(currentRow-2 > 0 && currentRow-2 <= gridSize && currentColumn+1 > 0 && currentColumn+1 <= gridSize){
temp = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd->moves = moves;
queueEnd->row = currentRow-2;
queueEnd->column = currentColumn+1;
queueEnd->next = temp;
queueEnd->next->previous = queueEnd;
queueEnd = temp;
queueAmount++;
}

if(currentRow+2 > 0 && currentRow+2 <= gridSize && currentColumn-1 > 0 && currentColumn-1 <= gridSize){
temp = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd->moves = moves;
queueEnd->row = currentRow+2;
queueEnd->column = currentColumn-1;
queueEnd->next = temp;
queueEnd->next->previous = queueEnd;
queueEnd = temp;
queueAmount++;
}

if(currentRow+2 > 0 && currentRow+2 <= gridSize && currentColumn+1 > 0 && currentColumn+1 <= gridSize){
temp = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd->moves = moves;
queueEnd->row = currentRow+2;
queueEnd->column = currentColumn+1;
queueEnd->next = temp;
queueEnd->next->previous = queueEnd;
queueEnd = temp;
queueAmount++;
}

if(currentRow-1 > 0 && currentRow-1 <= gridSize && currentColumn-2 > 0 && currentColumn-2 <= gridSize){
temp = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd->moves = moves;
queueEnd->row = currentRow-1;
queueEnd->column = currentColumn-2;
queueEnd->next = temp;
queueEnd->next->previous = queueEnd;
queueEnd = temp;
queueAmount++;
}

if(currentRow+1 > 0 && currentRow+1 <= gridSize && currentColumn-2 > 0 && currentColumn-2 <= gridSize){
temp = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd->moves = moves;
queueEnd->row = currentRow+1;
queueEnd->column = currentColumn-2;
queueEnd->next = temp;
queueEnd->next->previous = queueEnd;
queueEnd = temp;
queueAmount++;
}

if(currentRow-1 > 0 && currentRow-1 <= gridSize && currentColumn+2 > 0 && currentColumn+2 <= gridSize){
temp = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd->moves = moves;
queueEnd->row = currentRow-1;
queueEnd->column = currentColumn+2;
queueEnd->next = temp;
queueEnd->next->previous = queueEnd;
queueEnd = temp;
queueAmount++;
}

if(currentRow+1 > 0 && currentRow+1 <= gridSize && currentColumn+2 > 0 && currentColumn+2 <= gridSize){
temp = (struct coordinates*)malloc(sizeof(coordinates));
queueEnd->moves = moves;
queueEnd->row = currentRow+1;
queueEnd->column = currentColumn+2;
queueEnd->next = temp;
queueEnd->next->previous = queueEnd;
queueEnd = temp;
queueAmount++;
}

startDequeingCheck();
}

void startDequeingCheck(){
queueAmount--;

//checks if it's inside the boundaries

if(queue->row >0 && queue->column >0 && queue->row <=gridSize && queue->column <=gridSize){
//checks if it has found the final position

if(queue->row == R2 && queue->column == C2){
amountOfMoves = queue->moves;
return;
}

//else enqueue all the posibilities of the current position
queuePosibleMoves(queue->row,queue->column,queue->moves+1);

}else{

startDequeingCheck();
}

}```

5. and this is the input

Code:
```100
5 5 5 4 4
11 10 10 2 8
20 19 19 3 5
14 6 14 14 8
19 13 11 2 3
10 5 3 4 3
10 2 7 9 6
11 2 10 11 11
9 9 2 8 4
11 8 6 7 8
10 2 2 4 9
17 3 6 16 12
11 1 7 8 9
12 12 3 7 1
20 1 3 5 9
12 10 3 10 11
20 7 2 14 9
15 9 10 5 7
12 11 9 12 5
16 8 3 12 2
20 19 3 10 2
9 3 5 4 7
6 4 3 6 1
10 6 5 3 1
19 7 13 6 2
20 11 2 17 16
19 1 14 4 7
18 17 4 17 17
17 15 17 5 16
8 8 2 8 2
5 5 4 2 4
17 8 1 9 9
17 17 3 12 7
6 6 1 6 3
10 6 2 3 1
10 7 5 1 7
4 1 4 1 1
6 1 6 2 1
11 4 5 11 6
9 8 7 2 6
11 11 7 11 11
16 1 8 12 9
17 13 5 2 10
6 5 1 6 2
15 1 11 4 4
12 4 11 12 9
10 9 9 1 7
12 6 6 3 2
12 1 7 11 5
7 2 5 6 7
7 6 6 5 4
5 5 3 1 4
6 5 3 6 6
4 3 1 1 2
8 3 4 6 4
8 5 5 6 4
6 3 3 4 2
15 4 7 10 1
5 3 1 3 1
11 11 7 9 10
13 10 10 8 4
5 5 4 3 1
19 15 1 13 13
8 5 7 2 4
17 11 4 11 1
11 3 1 3 7
11 9 1 6 2
12 11 12 7 7
9 6 8 9 6
16 4 2 6 1
17 14 2 13 13
20 19 7 3 2
17 9 10 7 3
14 11 2 9 5
5 3 5 4 5
12 3 6 10 11
4 3 3 1 3
6 6 1 6 3
8 6 7 3 1
13 5 11 10 4
7 5 4 1 2
12 3 12 5 9
15 13 6 9 8
12 8 12 10 8
7 6 6 7 7
16 9 2 10 6
13 4 13 11 9
12 5 12 9 10
4 3 3 4 2
12 9 9 12 2
8 5 7 8 1
7 5 5 2 7
7 5 4 3 5
4 1 3 1 4
19 8 19 15 8
4 2 3 4 1
5 4 4 5 5
15 2 1 8 13
11 8 9 9 7
12 9 3 11 4```

6. Well the first problem is you never call free() when you're done with a test.

So the memory footprint just balloons out of control (I just killed it when it went north of 1.5GB)

FYI, this is out of memory, not stack overflow.

7. Originally Posted by Salem
Well the first problem is you never call free() when you're done with a test.

So the memory footprint just balloons out of control (I just killed it when it went north of 1.5GB)

FYI, this is out of memory, not stack overflow.
yea, I solved the problem now.

I retardedly kept calling in the enqueue and dequeue function inside of themselves, so it just kept on stacking.

All i did to solve it was remove the

Code:
`	startDequeingCheck();`
inside the queuePosibleMoves function.

Then I dequeued in main if the queue still had elements.

Sometimes I forget the simplest of things =P

Thanks guys =)