Thread: 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 =)

Anyone ?

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();
	}

}

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

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 =)