Following is pseudocode for the algorithm used by the scan:
Solve-State(state, prev_states, ret) if (state == empty_state) Push(ret, state) return SOLVED for each move possible on state new_state <- apply(state, move) if (new_state in prev_states) ; Do nothing else add new_state to prev_states if (Solve-State(new_state, prev_states, ret) == SOLVED) Push(ret, state) return SOLVED return UNSOLVED Freecell-Solver(init_state) if (Solve-State(init_state, Null, ret) == SOLVED) print "State was solved" while (state <- Pop(ret)) print state else print "I could not solve this board";
The algorithm uses recursion to trace the solution
and it stores all the states it encountered in a state
collection (called prev_states
in the
pseudocode), so they won't be checked again.