Stack Overflow

This is a discussion on Stack Overflow within the C Programming forums, part of the General Programming Boards category; So I'm doing a pretty easy assignment to figure out what's the minimum amount of steps required for a Knight ...

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    19

    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. #2
    Registered User
    Join Date
    Sep 2010
    Posts
    19
    Anyone ?

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Sep 2010
    Posts
    19
    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. #5
    Registered User
    Join Date
    Sep 2010
    Posts
    19
    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. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,494
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Sep 2010
    Posts
    19
    Quote Originally Posted by Salem View Post
    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 =)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack overflow
    By alperen1994 in forum C Programming
    Replies: 5
    Last Post: 04-06-2009, 11:11 AM
  2. Stack Overflow
    By madmardigan53 in forum C++ Programming
    Replies: 2
    Last Post: 08-10-2003, 12:32 PM
  3. stack overflow
    By Unregistered in forum C Programming
    Replies: 29
    Last Post: 08-05-2002, 02:57 PM
  4. stack overflow...need help
    By Unregistered in forum C Programming
    Replies: 12
    Last Post: 06-18-2002, 01:54 PM
  5. stack overflow?
    By Leeman_s in forum C++ Programming
    Replies: 13
    Last Post: 05-02-2002, 05:27 PM

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