Suggestion for Section - 5.4 Pruning the Search

[technusm1]

Suggestion for Section - 5.4 Pruning the Search

[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.