Suggestion for Section - 5.4 Pruning the Search

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: ```C++ #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.