Hello, I've written a knight's tour program and handed in a working version of it already using a bunch of if statements for each possible move. I really wanted to use a couple of arrays for the moves and consolidate my code more, but I ran out of time. I do really want to get it working using the arrays for the moves however. I really thought that I had them set up correctly in the movePosition(), but I'm missing something (probably has to do with my for loop), but I can't seem to get my head around the missing/wrong logic I used with it. Any suggestions or what I should look at? I can post my working program (if statements) if needed, but this is what I've gotten so far with the arrays:

bool knightsTour::checkPosition (int r, int c, int size) //validates position
{
    boardSize = size;

    if((r < 0 || c < 0) || (r >= boardSize || c >= boardSize))      //within bounds                                                                    
        return false;
    else                                                                                                                   
        if((board[r][c]) == 0)
            return true;  //not occupied                         
        else                                                                                                                             
            return false;//occupied            
}

void knightsTour::movePosition(int r, int c, int size, int count)
{
    board[r][c] = count;
    int moveRow[8] = {2,2,-2,-2,1,1,-1,-1};
    int moveCol[8] = {1,-1,1,-1,2,-2,2,-2};

        if (count == size * size)
        { 
            print(size);
            return;
        }

    for(int x = 0; x < 8; x++)
    {
        if(checkPosition(r + moveRow[x], c + moveCol[x], size))
        {
            count++;
            movePosition(r + moveRow[x], c + moveCol[x], size, count);
            if(count < (size * size))
            {
                int row = (r + moveRow[x]);
                int col = (c + moveCol[x]);
                board[row][col] = 0;
                count--;
            }
        }

        if(count < (size * size))
        {
            board[r][c] = 0;
            count--;
        }
    }
}//end movePosition()

Edited 3 Years Ago by mike_2000_17: Fixed formatting

You are recalling the function so it will never run the if statement I commented.

for(int x = 0; x < 8; x++)
{
	if(checkPosition(r + moveRow[x], c + moveCol[x], size))
	{
		count++;
		movePosition(r + moveRow[x], c + moveCol[x], size, count);
		if(count < (size * size)) //this never runs
		{
			int row = (r + moveRow[x]);
			int col = (c + moveCol[x]);
			board[row][col] = 0;
			count--;
		}
	}

	if(count < (size * size))
	{
		board[r][c] = 0;
		count--;
	}
}

You are recalling the function so it will never run the if statement I commented.

for(int x = 0; x < 8; x++)
{
    if(checkPosition(r + moveRow[x], c + moveCol[x], size))
    {
        count++;
        movePosition(r + moveRow[x], c + moveCol[x], size, count);
        if(count < (size * size)) //this never runs
        {
            int row = (r + moveRow[x]);
            int col = (c + moveCol[x]);
            board[row][col] = 0;
            count--;
        }
    }

    if(count < (size * size))
    {
        board[r][c] = 0;
        count--;
    }
}

end quote.

I have it set up the exact same way, except I use individual if statements for each move, rather than arrays and a for loop, and it runs with no problem. The only thing that is really different is that I used 2 arrays (one for row, one for column) within a for loop to execute through all moves. The statement will run, the function is just calling another version of itself, then the rest of it executes (recursion). It's got to be something to do with my for loop, it's most likely causing an infinite recursion, therefore a stack overflow:

void knightsTour::movePosition(int r, int c, int size, int count)
{
    board[r][c] = count;

    // JEY ADDED THIS CODE
    if (count == size * size) { 
        print(size);
        return;
    }

        if(checkPosition(r + 2, c + 1, size))
        {
            count++;
            movePosition(r + 2, c + 1, size, count);
            if(count < (size * size))
            {
                board[r + 2][c + 1] = 0;
                count--;
            }
        }

        if(checkPosition(r + 2, c - 1, size))
        {
            count++;
            movePosition(r + 2, c - 1, size, count);
            if(count < (size * size))
            {
                board[r + 2][c - 1] = 0;
                count--;
            }
        }

        if(checkPosition(r + 1, c + 2, size))
        {
            count++;
            movePosition(r + 1, c + 2, size, count);
            if(count < (size * size))
            {
                board[r + 1][c + 2] = 0;
                count--;
            }
        }

        if(checkPosition(r + 1, c - 2, size))
        {
            count++;
            movePosition(r + 1, c - 2, size, count);
            if(count < (size * size))
            {
                board[r + 1][c - 2] = 0;
                count--;
            }
        }

        if(checkPosition(r - 2, c + 1, size))
        {
            count++;
            movePosition(r - 2, c + 1, size, count);
            if(count < (size * size))
            {   
                board[r - 2][c + 1] = 0;
                count--;
            }
        }

        if(checkPosition(r - 2, c - 1, size))
        {
            count++;
            movePosition(r - 2, c - 1, size, count);

            if(count < (size * size))
            {
                board[r - 2][c - 1] = 0;
                count--;
            }
        }

        if(checkPosition(r - 1, c + 2, size))
        {
            count++; 
            movePosition(r - 1, c + 2, size, count);
            if(count < (size * size))
            {
                board[r - 1][c + 2] = 0;
                count--;
            }
        }

        if(checkPosition(r - 1, c - 2, size))
        {
            count++;
            movePosition(r - 1, c - 2, size, count);
            if(count < (size * size))
            {
                board[r - 1][c - 2] = 0;
                count--;
            }
        }

        if(count < (size * size))
        {
            board[r][c] = 0;
            count--;
        }

}//end movePosition()

Edited 3 Years Ago by mike_2000_17: Fixed formatting

Just to double check is this a program that will run through the "map" and will move the knight to all accessible open squares?

Just to double check is this a program that will run through the "map" and will move the knight to all accessible open squares?

Yes, sorry I should have clarified that in my original post. I just assumed that everyone knew what the knights tour problem was.

This article has been dead for over six months. Start a new discussion instead.