Suggestion for Section - 5.4 Pruning the Search

[technusm1]

It would be better if code could be included in this section to provide a better understanding of the problem of counting the paths in 7x7 grid.

I am posting my own code below for solving this problem. Hopefully it is useful to someone trying to understand how things work:

#include <iostream>

// SECTION: Function declarations
int count_paths(int sx, int sy, int ex, int ey);

// SECTION: global constants
const int n = 7;
// better to use a data structure with O(1) insertion and O(1) retrieval time. Using anything else results in a huge performance penalty
int visited[n][n] = {0};
int visited_cells_count = 0;

// SECTION: driver code
int main(int argc, char const *argv[])
{
	// Multiplying counted paths by 2 because of optimization - 1
	std::cout << (2*count_paths(0, 0, n-1, n-1)) << '\n';
	return 0;
}

int count_paths(int sx, int sy, int ex, int ey) {
	int result = 0;
	bool can_move_left, can_move_right, can_move_up, can_move_down;
	visited[sx][sy] = 1;
	visited_cells_count += 1;
	if (sx == ex && sy == ey) {
		if (visited_cells_count == n*n) {
			// The starting and ending points are same, and we have traversed all cells of the grid, so this counts as 1 path
			result = 1;
		} else {
			// Optimization 2: If all elements are not covered (i.e. visited_cells_count != n*n), the path is not valid, so we return 0
			result = 0;
		}
	} else {
		can_move_left = ((sx - 1 >= 0) && !visited[sx - 1][sy]);
		// Optimization 1: We can move either to right, or downwards from the first cell.
		// Since number of paths (going right) == number of paths (going down), we can skip one branch entirely.
		// This halves the number of recursions.
		can_move_right = (!((sx == 0) && (sy == 0)) && (sx + 1 < n) && !visited[sx + 1][sy]);
		can_move_up = ((sy - 1 >= 0) && !visited[sx][sy - 1]);
		can_move_down = ((sy + 1 < n) && !visited[sx][sy + 1]);

		// Optimization 3 and 4: if the path cannot continue forward but can turn either left or right, the grid splits into two parts
		// that both contain unvisited squares. It is clear that we cannot visit all squares anymore, so we can terminate the search.
		if (((can_move_left && can_move_right) && !can_move_up && !can_move_down) || ((can_move_up && can_move_down) && !can_move_left && !can_move_right)) {
			result = 0;
		} else {
			// move left
			if (can_move_left) {
				result += count_paths(sx - 1, sy, ex, ey);
			}
			// move right
			if (can_move_right) {
				result += count_paths(sx + 1, sy, ex, ey);
			}

			// move up
			if (can_move_up) {
				result += count_paths(sx, sy - 1, ex, ey);
			}
			// move down
			if (can_move_down) {
				result += count_paths(sx, sy + 1, ex, ey);
			}
		}
	}
	visited[sx][sy] = 0;
	visited_cells_count -= 1;
	return result;
}

Thank you for your hard work.

[dhern023]

@technusm1 You're almost there, but this code returns 0 for even valued n. You can see it for yourself if you print out the matrix and set each visited assignment to visited cells count.

void coutMatrix(std::vector< std::vector<int>> matrix, int rows, int cols)
{
    for (int i < 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (j != 0)
            {
                std::cout << "\t";
            }
            std::cout << matrix[i][j];
        }
        std::cout << "\n";
    }
}

//adjust these lines
        // Flip these two
	visited_cells_count += 1; // ------------------can be over n*n for even valued
	visited[sx][sy] = visited_cells_count; //------------------ optional to see the path (1 -> n*n)
	if (sx == ex && sy == ey) {
                coutMatrix(visited, n, n); // --------------- optional to see the path (1 -> n*n)
		if (visited_cells_count == n*n) {
			// The starting and ending points are same, and we have traversed all cells of the grid, so this counts as 1 path
			result = 1;
		} else {
			// Optimization 2: If all elements are not covered (i.e. visited_cells_count != n*n), the path is not valid, so we return 0
			result = 0;
		}
	}	

[dhern023]

By the way, this problem is a subset of a larger problem, which is finding all the Hamiltonian paths on a grid graph.