solve sudoku puzzle using A*(A-Star) search

Question

i want to solve sudoku puzzle using A* Search. how to define g(n) and h(n)?? what should h and g be??

i want to code that in python but any pseudo code would be appreciated

Answer 1

A* is a graph search algorithm that finds a shortest path between a source to a destination (or set of destinations).

To use A* on your problem, you need to reduce it to shortest path problem.

In your case it could be by defining a state graph - where each node in the graph is a partially full sudoku table, and an edge indicates you can move from one state to the other.

Formally:

G = (V,E)
V = { s | for each valid state s of the sudoku board}
E = { (u,v) | can move from state u to state v by adding one number }

Now, you need to find a shortest path from the starting state (your given board), to a target state (a full valid board).