Stack Overflow

[jsmith1992]

Hello everyone! I am having a hard time fixing a stack overflow issue. I seem to have accidentally created an infinite recursion and I need a way out. I believe all I need is to ++row; somewhere but I'm stuck, maybe a new pair of eyes can spot it? Here is my code:

#include <iostream>
#include <iomanip>

using namespace std;

const int boardSize = 8;
const char QUEEN = 'Q';
const char UNDEFINED = 'X';

char board[8][8];
void initializeCurrentPath();
void attempt(int n, int row, int column);
void addToCurrentPath(int row, int column);
void removeFromCurrentPath(int row, int column);
bool currentPathSuccess(int n, int row, int column);
bool currentPathStillViable(int row, int column);
void processSuccessfulPath(int n);

int main()
{

	initializeCurrentPath();
	for (int k = 0; k < boardSize; ++k)
		attempt(boardSize, 0, k);

	system("pause");
	return 0;
}

void initializeCurrentPath()
{

	int r = 0;
	int c = 0;

	while(r < 8)
	{

		c = 0;

		while(c < 8)
		{
			board[r][c] = UNDEFINED;
			++c;
		}
		++r;
	}
}

void attempt (int n, int row, int column)
{

	addToCurrentPath(row, column);
	if (currentPathSuccess(n, row, column))
		processSuccessfulPath(n);
	else if (currentPathStillViable(row, column))
		for (int k = 1; k <= n; ++k)
			attempt(n, row, k);
	removeFromCurrentPath(row, column);
}

void addToCurrentPath(int row, int column)
{

	board[row][column] = QUEEN;
}

void removeFromCurrentPath(int row, int column)
{

	board[row][column] = UNDEFINED;
}

bool currentPathSuccess(int n, int row, int column)
{

	bool success = true;

	if(n > row)
		return false;
	for(int r = row, c = column + 1; c < boardSize && success; ++c)//right
	{
		if(board[r][c] == QUEEN)
			success = false;
	}

	for(int r = row + 1, c = column + 1; r < boardSize && c < boardSize && success; ++r, ++c)//downRight
	{
		if(board[r][c] == QUEEN)
			success = false;
	}
	
	for(int r = row + 1, c = column; r < boardSize && success; ++r)//down
	{
		if(board[r][c] == QUEEN)
			success = false;
	}

	for(int r = row + 1, c = column - 1; r < boardSize && c >= 0 && success; ++r, --c)//downLeft
	{
		if(board[r][c] == QUEEN)
			success = false;
	}

	for(int r = row, c = column - 1; c >= 0 && success; --c)//left
	{
		if(board[r][c] == QUEEN)
			success = false;
	}

	for(int r = row - 1, c = column - 1; r >= 0 && c >= 0 && success; --r, --c)//upLeft
	{
		if(board[r][c] == QUEEN)
			success = false;
	}

	for(int r = row - 1, c = column; r >= 0 && success; --r)//up
	{
		if(board[r][c] == QUEEN)
			success = false;
	}

	for(int r = row - 1, c = column + 1; r >= 0 && c < boardSize && success; --r, ++c)//upRight
	{
		if(board[r][c] == QUEEN)
			success = false;
	}

return success;
}

bool currentPathStillViable(int row, int column)
{

	bool viable = true;

	for(int r = row, c = column + 1; c < boardSize && viable; ++c)//right
	{
		if(board[r][c] == QUEEN)
			viable = false;
	}

	for(int r = row + 1, c = column + 1; r < boardSize && c < boardSize && viable; ++r, ++c)//downRight
	{
		if(board[r][c] == QUEEN)
			viable = false;
	}
	
	for(int r = row + 1, c = column; r < boardSize && viable; ++r)//down
	{
		if(board[r][c] == QUEEN)
			viable = false;
	}

	for(int r = row + 1, c = column - 1; r < boardSize && c >= 0 && viable; ++r, --c)//downLeft
	{
		if(board[r][c] == QUEEN)
			viable = false;
	}

	for(int r = row, c = column - 1; c >= 0 && viable; --c)//left
	{
		if(board[r][c] == QUEEN)
			viable = false;
	}

	for(int r = row - 1, c = column - 1; r >= 0 && c >= 0 && viable; --r, --c)//upLeft
	{
		if(board[r][c] == QUEEN)
			viable = false;
	}

	for(int r = row - 1, c = column; r >= 0 && viable; --r)//up
	{
		if(board[r][c] == QUEEN)
			viable = false;
	}

	for(int r = row - 1, c = column + 1; r >= 0 && c < boardSize && viable; --r, ++c)//upRight
	{
		if(board[r][c] == QUEEN)
			viable = false;
	}

return viable;
}

void processSuccessfulPath(int n)
{

	int r = 0;
	int c = 0;

	while(r < 8)
	{

		c = 0;

		while(c < 8)
		{
			cout << board[r][c];
			++c;
		}

		cout << endl;
		++r;
	}
}

[roberts]

for (int k = 1; k <= n; ++k)
attempt(n, row, k);
removeFromCurrentPath(row, column);
}

You send k to attempt and attempt receives it as column. n goes through as is. I'm not seeing where this loop will ever have a conclusion since k is always getting set to 1 and n will always be n. If n is 2, then every time this loop is encountered, k = 1, n = 2, always and forever.

You're only hope of not getting into an endless loop is if the preceding two lines:

	if (currentPathSuccess(n, row, column))
		processSuccessfulPath(n);

Evaluate true more times than it evaluates false.

[jsmith1992]

n is what passes boardSize to the attempt function. Within currentPathSuccess, is the code

if(n > row)
    return false;

so when row reaches 7 the program will check one more time for success to be true and if it is true then it will print the "board". The problem I'm having is adding 1 to row after each time currentPathSuccess fails.

[jsmith1992]

I was thinking that if I changed the for statement in the main to this then row would reach 7 and end the infinite recursion but I am still getting stack overflow.

	for (int k = 0, r = 0; k < boardSize; ++k, ++r)
	{
		attempt(boardSize, r, k);
	}

[roberts]

Have you watched the variables change? Some of my debugging involves couting variable states to stdout or a file.

[jsmith1992]

Yes I have, for some reason my compiler (Visual Studios 2010) is executing in this sequence:

1. addToCurrentPath;
2. if (currentPathSuccess(n, row, column)) ...
3. else if (currentPathStillViable(row, column)) ...
4. removeFromCurrentPath(row, column);

then back to attempt(n, row, k); rather than addToCurrentPath(row, column)

if that makes any sense..

void attempt (int n, int row, int column)
{

	addToCurrentPath(row, column);
	if (currentPathSuccess(n, row, column))
		processSuccessfulPath(n);
	else if (currentPathStillViable(row, column))
		for (int k = 1; k <= n; ++k)
			attempt(n, row, k);// to here
	removeFromCurrentPath(row, column);// from here
}

[Moschops]

For purposes of explicitness (it is covered above), here's what the stack looks like.... those variables never change.

#0  0x00000000004009e8 in currentPathSuccess (n=Cannot access memory at address 0x7fffff5feffc) at 112.cpp:74
#1  0x0000000000400946 in attempt (n=8, row=0, column=1) at 112.cpp:53
#2  0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#3  0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#4  0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#5  0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#6  0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#7  0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#8  0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#9  0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#10 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#11 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#12 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#13 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#14 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#15 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#16 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#17 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#18 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#19 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#20 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#21 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57
#22 0x0000000000400984 in attempt (n=8, row=0, column=1) at 112.cpp:57

[jsmith1992]

Now for the dumb question, How would I fix that? I can't seem to find a way around it.

[Moschops]

Presumably each attempt is actually supposed to be on a different combination of row and column?

[jsmith1992]

Yes and no, I am writing a program to solve the eight queens challenge. So it will place a queen and if that queen is safe it will stay and the program moves to the next column. If the queen is not safe the queen is removed and the program moves to the next row. This happens until eight queens are placed safely on the 8x8 board, or in this case the 2D array. When the last queen is placed the program outputs the results to the screen.

[jsmith1992]

so this is how the "board" is initialized

XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX

first queen ('Q') is placed

1.
QXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX

second and third attempt fail, fourth attempt success

2 - 4
QQXXXXXX QXXXXXXX QXXXXXXX
XXXXXXXX XQXXXXXX XXXXXXXX
XXXXXXXX XXXXXXXX XQXXXXXX
XXXXXXXX XXXXXXXX XXXXXXXX
XXXXXXXX XXXXXXXX XXXXXXXX
XXXXXXXX XXXXXXXX XXXXXXXX
XXXXXXXX XXXXXXXX XXXXXXXX
XXXXXXXX XXXXXXXX XXXXXXXX

if all attempts fail in one column the attempt terminates, the previous queen is removed, and a new queen is placed one row down. Then the process continues until there is a solution.
(sorry about the ugly tables)

[ne555]

So it will place a queen and if that queen is safe it will stay and the program moves to the next column.
If the queen is not safe the queen is removed and the program moves to the next row.

put_queen(row, col);
if( is_it_safe(row, col) )
    keep_going(1, col+1);
else{
    remove_queen(row, col);
    keep_going(row+1, col);
}

This happens until eight queens are placed safely on the 8x8 board, or in this case the 2D array.
When the last queen is placed the program outputs the results to the screen.

if( how_many == 8 ){ //base case
  print_board();
  return;
}

There is a problem with that algorithm.
Suppose that e4 was a safe position, but later you can't fill the 8 queens. Then maybe it shouldn't be a queen in e4.
if all attempts fail in one column the attempt terminates, the previous queen is removed, and a new queen is placed one row down. Then the process continues until there is a solution.

if( row>8 )
  fail(); //¿how does it comunicate with the queen in the previous row? 

When you fix that, it will print all the possible layouts or just one. Try to do both.

Next, just count the number of ways in a nxn board

[jsmith1992]

I thought it was terminated via the recursion. Once k > n that function would terminate, go back to the previous attempt, returning viable as false and removing the queen with removeFromCurrentPath. Now that I think about it I'm not quite sure it is actually doing that..