diff options
| author | Arthur de Jong <arthur@arthurdejong.org> | 2016-11-12 13:56:07 +0100 |
|---|---|---|
| committer | Arthur de Jong <arthur@arthurdejong.org> | 2016-11-12 13:56:07 +0100 |
| commit | 8af6de90355ad54fd261ca8a7c88801a317a188c (patch) | |
| tree | 58507d71d43f2c7766c4772e0e9ecae582a15424 | |
| parent | 7616a608d437a58fad087f04b3f068bd9cf6d58b (diff) | |
Use queue to do breadth-first traversal
This results in the best (shortest) solution to be found first and is much quicker in finding all solutions.
| -rw-r--r-- | x.py | 43 |
1 files changed, 20 insertions, 23 deletions
@@ -101,28 +101,25 @@ def score_move(move, moves): return float(before + 1) / length -def _find_solutions(board, visited, moves): - # find possible moves and see if we get somewhere new - possible = [] - for move, newboard in possible_moves(board): - if is_solution(newboard): - yield moves + [(move, newboard)] - return - found = visited.get(newboard) - if found is None or found > len(moves): - possible.append((score_move(move, moves), move, newboard)) - visited[newboard] = len(moves) - # try highest likelyhood first - possible.sort() - # make each move and check recursively - for score, move, newboard in possible: - for solution in _find_solutions( - newboard, visited, moves + [(move, newboard)]): - yield solution - - def find_solutions(board): board = clean_board(board) - visited = {board: 0} - for solution in _find_solutions(board, visited, []): - yield solution + visited = set([board]) + queue = [] + queue.insert(0, [('', board)]) + while queue: + moves = queue.pop() + board = moves[-1][1] + # find possible moves and see if we get somewhere new + possible = [] + for move, newboard in possible_moves(board): + if is_solution(newboard): + yield moves[1:] + [(move, newboard)] + elif newboard not in visited: + possible.append( + (score_move(move, moves), moves + [(move, newboard)])) + visited.add(newboard) + # try highest likelyhood first + possible.sort() + # add new solutions to find to queue + for score, moves in possible: + queue.insert(0, moves) |