Astar-like algorithm with unknown endstate

Question

A-star is used to find the shortest path between a startnode and an endnode in a graph. What algorithm is used to solve something were the target state isn't specifically known and we instead only have a criteria for the target state?

For example, can a sudoku puzzle be solved with an Astar-like algorithm? We dont know how the endstate will look like (which number is where) but we do know the rules of sudoku, a criteria for a winning state. Therefore I have a startnode and just a criteria for the endnode, which algorithm to use?

Answer 1

A* requires a graph, a cost function for traversal of that graph, a heuristic as to whether a node in the graph is closer to the goal than another, and a test whether the goal is reached.

Searching a Sudoku solution space doesn't really have a traversal cost to minimize, only a global cost ( the number of unsolved squares ), so all traversals would be equal cost, so A* doesn't really help - any cell you could assign costs one move and moves you one closer to the goal, so A* would be no better than choosing the next step at random.

It might be possible to apply an A* search based on the estimated/measured cost of applying the different techniques at each point, which would then try to find a path through the solution space with the least computational cost. In that case the graph would not just be the solution states of the puzzle, but you'd be choosing between the techniques to apply at that point - you'd know an estimate of the cost of a transition, but not where that transition 'goes', except that if successful, it's one step closer to the goal.

Answer 2

Yes, A* can be used when a specific goal state cannot be identified. (Pete Kirkham's answer implies this, but doesn't emphasise it much.)

When a specific goal state can't be identified, it's sometimes harder to come up with a useful heuristic lower bound on the remaining cost needed to complete a partial solution -- and the efficiency of A* depends on choosing an effective heuristic. But it doesn't mean it can't be applied. Any problem that can be solved on a computer can be solved using a breadth-first search, plus an array of flags indicating whether a state has been seen before; which is the same as A* with a heuristic lower bound that is always zero. (Of course, this is not the most efficient algorithm for solving many problems.)

Answer 3

You dont have to know the exact target endstate. It all comes down to the heuristic function, when it returns 0 you could assume to have found (at least) one of the valid endstates.

So during the a*, instead of checking if current_node == target_node, check if current_node.h() returns 0. If so, it should be infinitely close and/or overlapping the goal/endstate.