Recursion issue and backtracking (checkerboard jumps)

[mk92595]

.

[CptJY]

Can you tell me why you use a recursive function.
The king can only move one space in any direction ?

[coder777]

First of all you need to make sure that something like board[row - 1][col + 1] is valid. For instance it would be invalid if row - 1 < 0.

One way to ensure this is to make a frame with occupied fields around the real field. The starting point would be {1,1}.

The next proble is that you leave 'traces'. If you move in one direction there shouldn't be a trace from the other direction:

Try this:

	addChecker('|', row, col); // mark the current position as occupied (and just the current)
	if (board[row - 1][col + 1] == 'W') //top left
	{
		total = 1 + numJumps(row - 1, col + 1);
	}
	else if (board[row - 1][col - 1] == 'W') //top right
	{
		total = std::max(1 + numJumps(row - 1, col - 1), total);
	}
...
	addChecker('W', row, col); // free the current position 

You can make total a local varibale. It is/should not be used anywhere else.

[mpark4656]

This kind of problem usually requires you to "simulate" all possible combinations of moves that king can make and get the best move that results in the highest number of jumps.

The simplest way to do it is to recursively call a function to simulate all possible moves (similar to what you did) and return a move that results in the highest number of jumps.

With no optimization, this algorithm is very expensive. I used it to implement Tic Tac Toe AI and because the board is only 3X3, it was pretty quick, but try something like this on a larger board and you will see it lagging.

I'm quite new to this as well, so I don't have good optimized code, but you can try implementing this. I will only provide the pseudocode, so you will have to do the bulk of the work.

struct Move
{
    int direction
    // 4      1
    //     K  
    // 3      2
    
    int numberOfJumps;

    // Add any other attributes/operations such as constructors and overloaded operator<
}


Move getBestMove( Board board )
{
    // This is the base case for this recursion
    if( king is stuck ) {
        // In this case, direction doesn't matter since king can't jump
        return Move with 0 numberOfJumps;
    }

    // This container will store all 4 moves simulated on the current board
    std::vector<Move> moves;

    // This is where you will simulate all 4 moves recursively. i is the direction
    for( int i = 1 ; i <= 4 ; i++ ) {
        if( king can jump in i direction ) {
            // Create Move instance with direction initialized to i
            Move move( i );

            // Move the king in the i direction on the board
            board.makeMove( i );

            // Call this function recursively, storing the number of jumps king has made
            move.numberOfJumps = 1 + getBestMove( board ).numberOfJumps;

            // Undo the jump. Remember, we shouldn't change the actual board
            board.undoMove( opposite i );

            // Store this move in moves
            moves.push_back( move );
        }
    }

    // Now, look in the moves and return the move with the highest number of jumps
    return *max_element( moves.begin() , moves.end() );
}

Eventually, the function will return Move that has the direction which will eventually yield the highest number of jumps and also it specifies the highest number of jumps.

Like I said, this isn't the best algorithm, but it is easy to implement and understand IMO and if the board is small enough, you can use it.

EDIT: Completely overlooked the fact that this is for checker. Changed the code accordingly

[somcom3x]

Cutting it pretty close to the due date aren't you?
You need to change your else ifs to just if statements (as coder777 explained about traces)

Then add back the backtrack (undo the move). This ensures the maximum number of jumps is made without them interfering with one another. I was stuck on this for a little while as well.

You also need to add logic to determine if the move is legal and the max function as coder777 mentioned. I wanted to add that you also need to make sure that the row/col is not over the maximum ( r < 7 || c < 7).

Also, your comments based on what your function if statements do are incorrect.

EDIT: Derp, comments based on your if statements.^

[mk92595]

Figured it out by myself.

Thanks anyways.