A* search for Sudoku

Question

I have a homework problem for an Artificial Intelligence course that I am having trouble answering.

Consider solving the Sudoku problem using A* search. The start state has some number of cells filled in, and the successors of each state are all legal ways an additional cell can be filled in. At any time we know exactly the number of cells that remain to filled.

Therefore, if K cells remain to be filled at node n, we know that h(n) = K. Thus if we set our heuristic function h(n) to be h(n)=K, we will have perfect heuristic knowledge in A.

Explain the mistake in the above statement.

I understand that this heuristic is entirely pointless since if there was some function that could find legal successors you might as well run a depth first search but what exactly is wrong with the above statement.

Answer 1

This isn't an answer, but it's too long for a comment...

Using that remaining-distance metric, you can certainly implement an A* search and it will give the correct result, but it will be extremely inefficient. The reason is that it's really a Dijkstra search disguised as A*. Worse than that, as Shawn notes, it's really a simple breadth-first search.

The reason it has decayed to Dijkstra is because your metric gives no clues as to which is the best direction to take through the state space. Each step from a particular intermediate state is just filling in one digit in one cell - precisely as cheap/costly as filling in any other possible digit/cell at that point and with no clue as to which successor states (with the same number of empty cells) are closer to a correct solution. All paths from that intermediate state to the solution are the same length, including the ones leading through illegal states to a broken solution.

This is legal in the sense that the distance metric is a lower bound to the remaining distance to a solution. But it's not just a lower bound, it's an exact distance. Your "perfect heuristic" isn't guiding the search towards the solution in any useful way beyond what Dijkstra could do.

The reason it has decayed to a breadth-first search is the same thing, but in terms of the weights of edges already traversed so far. Every path from the start to any intermediate state has the same number of edges and the same total cost (same number of cells filled in). Every edge effectively has weight one, and there are no short-cuts for Dijkstra to exploit.

In practice, Sodoku solvers usually use backtracking depth-first search with relatively cheap checks (if there are two of the same digit in any cell, row or block, this state is impossible as are all possible successor states) to avoid searching impossible parts of the search space. There's not much guidance you can get on which intermediate states are better without spending more on the heuristics and search algorithm than you gain by pruning the search tree further, and besides, backtracking search with that simple pruning is very fast.

Answer 2

The "legal successor" is not same as "valid successor". Eg. if single cell can contain N numbers, based on current state of the field, then each of them is "legal successor". But only one of them is "valid successor" (assuming it has only one solution).

But I don't agree that it describes number of unfilled cells as perfect heuristic. But that is just my feeling.

And shouldn't you be asking this your professor?

Answer 3

This does not seem correct:

Therefore, if K cells remain to be filled at node n, we know that h(n) = K.

We don't know that h(n) = K unless we know that the puzzle is solvable from node n.