Recursive Knight's Tour Not Passing Copies of Array

[Jtpetch]

Hi, I'm supposed to write an algorithm to go through each possible solution (bruteforcing) and find every true solution to a Knight's Tour (5x5, starting at 3,3 (2,2 in the array.))

I've got most of it down and working, however, whenever I run the program, it only returns 128 answers (surely there are more), and the answers are 8 groups of 16 duplicates. This was later confirmed by watching the memory address of each "correct" solution in debug, and every group of 16 boards' memory addresses were indeed the same.

I'm not sure why this is happening, as what (I believe) should be happening is that each recursive call of the function gets a copy of the previous function's board.

This is the solver function I came up with:

  int solveBoard(Board board, int row, int col, int& solutionNum, int currentMoveNum = 1) {
	//Boundary Check
	if (row<0 || row>BOARD_SIZE - 1 || col<0 || col>BOARD_SIZE - 1) return 0;

	//End of Board Check
	if (currentMoveNum == BOARD_SIZE*BOARD_SIZE + 1) {
		++solutionNum;
		printBoard(board, solutionNum);
		return 1;
	}

	//Set Knight at Current Space (if possible)
	if (board.boardArray[row][col] == 0) board.boardArray[row][col] = currentMoveNum;
	else return 0;

	//MOVEMENT
	//DOWN 
	//Down 2 right 1
	solveBoard(board, row + 2, col + 1, solutionNum, currentMoveNum + 1);
	//Down 2 left 1
	solveBoard(board, row + 2, col - 1, solutionNum, currentMoveNum + 1);
	//Down 1 right 2
	solveBoard(board, row + 1, col + 2, solutionNum, currentMoveNum + 1);
	//Down 1 left 2
	solveBoard(board, row + 1, col - 2, solutionNum, currentMoveNum + 1);

	//UP
	//Up 2 right 1
	solveBoard(board, row - 2, col + 1, solutionNum, currentMoveNum + 1);
	//Up 2 left 1
	solveBoard(board, row - 2, col - 1, solutionNum, currentMoveNum + 1);
	//Up 1 right 2
	solveBoard(board, row - 1, col + 2, solutionNum, currentMoveNum + 1);
	//Up 1 left 2
	solveBoard(board, row - 1, col - 2, solutionNum, currentMoveNum + 1);

	//Return amount of solutions if algorithm is complete
	if (currentMoveNum == 1) return solutionNum;
}

And this is the struct I used to (hopefully) pass the array by value each time:

struct Board
{
	int boardArray[BOARD_SIZE][BOARD_SIZE] = { 0 };
};

I'm not sure where I'm going wrong here, and would love some help. Is the struct not working like I thought? Am I just going about this the wrong way?
Thank you so much for any help!

[Moschops]

Each time you pass Board by value, the copy of Board that gets created contains a whole new copy of the pointer named boardArray. With the same value. So pointing at the same memory. The data it points to is not copied.

Every copy of boardArray will be pointing at the same memory. They all share one set of actual data.

[ne555]

> the pointer named boardArray
boardArray is not a pointer, but an array of arrays of int.
the data is copied.

Every copy of boardArray will be at a different memory address. They all have their own set of data.


> This was later confirmed by watching the memory address of each "correct"
> solution in debug, and every group of 16 boards' memory addresses were indeed
> the same.
I don't know what you saw, you should show the commands that you've executed.
Also, provide a minimal example that does reproduce your issue

[Moschops]

So it is. I am getting too blasé about this again. Time to quit.

[Jtpetch]

I was incorrect about my observations on the output. There are indeed duplicates, and only 128, however, they do not appear to be groups of 16. This is some of the output (pastebin because long): https://pastebin.com/raw/7n7PhqDm

I didn't perform any commands. I was just running in debug mode, in VS 2015, with a breakpoint where I print the board, and the memory address displayed for each board was the same, even when the values changed.
EG:

{boardArray=0x004fd588 {0x004fd588 {19, 14, 9, 4, 21}, 0x004fd59c {8, 3, 20, 15, 10}, 0x004fd5b0 {13, ...}, ...} }

{boardArray=0x004fd588 {0x004fd588 {23, 2, 13, 8, 21}, 0x004fd59c {12, 7, 22, 3, 14}, 0x004fd5b0 {17, ...}, ...} }

Thank you for the replies, by the way!

[ne555]

memory may be reused.
you've got a dfs algorithm, new boards are created at each step, but when you reach a dead end or the solution they will be destroyed and a new one will use that (now free) space.

you'll have at most 25 boards at different address, ¿or was it really only one address?


Edit: about the repeated solutions
you don't end when you fill the board (when you write the 25 movement) but one step later.

	if (board.boardArray[row][col] == 0) board.boardArray[row][col] = currentMoveNum; //filled the board
	else return 0;

	//¿try to move?
	solveBoard(board, row + 2, col + 1, solutionNum, currentMoveNum + 1); 
	solveBoard(board, row + 2, col - 1, solutionNum, currentMoveNum + 1);
	solveBoard(board, row + 1, col + 2, solutionNum, currentMoveNum + 1);
	solveBoard(board, row + 1, col - 2, solutionNum, currentMoveNum + 1);

	solveBoard(board, row - 2, col + 1, solutionNum, currentMoveNum + 1);
	solveBoard(board, row - 2, col - 1, solutionNum, currentMoveNum + 1);
	solveBoard(board, row - 1, col + 2, solutionNum, currentMoveNum + 1);
	solveBoard(board, row - 1, col - 2, solutionNum, currentMoveNum + 1);

when checking for a solution you only care that you are not outside the board, and several of those (all illegal) moves fulfill that condition