From 8af6de90355ad54fd261ca8a7c88801a317a188c Mon Sep 17 00:00:00 2001
From: Arthur de Jong <arthur@arthurdejong.org>
Date: Sat, 12 Nov 2016 13:56:07 +0100
Subject: 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.
---
x.py | 43 ++++++++++++++++++++-----------------------
1 file changed, 20 insertions(+), 23 deletions(-)
diff --git a/x.py b/x.py
index 1da6979..58c5dfa 100644
--- a/x.py
+++ b/x.py
@@ -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)
--
cgit v1.2.3