Bekt · November 24, 2018 07:41 · Nov 24, 2018
diff --git a/pegs.py b/pegs.py
@@ -0,0 +1,66 @@
+"""
+11/24/2018
+
+Dumb backtracking-based solver for the Cracker Barrel Triangle Peg game.
+  http://recmath.org/pegsolitaire/CBTips.html
+
+This solution is generic to any N-row triangle.
+Doesn't assume any heuristic and also very memory intensive.
+"""
+
+def build_moves(n):
+    """Returns 1d array of all possible moves for each peg."""
+    board = [[True] * i for i in range(1, n+1)]
+    ok = lambda cell: cell[0] >= 0 and cell[1] >= 0 and cell[0] < len(board) \
+            and cell[1] < len(board[cell[0]])
+    convert = lambda cell: ((cell[0] * (cell[0] + 1)) // 2) + cell[1]
+    moves = []
+    for r in range(len(board)):
+        for c in range(len(board[r])):
+            steps = [
+                ( (r, c+1), (r, c+2) ),
+                ( (r, c-1), (r, c-2) ),
+                ( (r+1, c), (r+2, c) ),
+                ( (r-1, c), (r-2, c) ),
+                ( (r+1, c+1), (r+2, c+2) ),
+                ( (r-1, c-1), (r-2, c-2) ),
+            ]
+            steps = [step for step in steps if ok(step[0]) and ok(step[1])]
+            moves.append([(convert(step[0]), convert(step[1])) for step in steps])
+    return moves
+
+
+def backtrack(moves, pegs, memo={}, count=0, jumps=[]):
+    if len(pegs) == 1:
+        return count, jumps
+    mn = float('inf'), None
+    for peg, steps in enumerate(moves):
+        for step in steps:
+            edge, dest = step
+            if peg not in pegs or edge not in pegs or dest in pegs:
+                continue
+            pe = set(pegs)
+            pe.add(dest)
+            pe.remove(edge)
+            pe.remove(peg)
+            h = str(pe)
+            if h in memo:
+                continue
+            jo = list(jumps)
+            jo.append((peg, edge, dest))
+            memo[h], jo = backtrack(moves, pe, memo, count+1, jo)
+            if memo[h] < mn[0]:
+                mn = memo[h], jo
+    return mn
+
+
+def solve(n, empty):
+    moves = build_moves(n)
+    pegs = set({i for i in range(len(moves))}) - empty
+    return backtrack(moves, pegs)
+
+
+if __name__ == '__main__':
+    n = 5
+    count, jumps = solve(n, empty={0})
+    print('N: {}, Jumps: {}\n{}'.format(n, len(jumps), jumps))
diff --git a/z_out.txt b/z_out.txt
@@ -0,0 +1,7 @@
+$ py3 pegs.py
+N: 5, Jumps: 13
+[(3, 1, 0), (5, 4, 3), (0, 2, 5), (6, 3, 1), (9, 5, 2), (11, 7, 4), (12, 8, 5), (1, 4, 8), (2, 5, 9), (14, 9, 5), (5, 8, 12), (13, 12, 11), (10, 11, 12)]
+
+$ py3 pegs.py
+N: 6, Jumps: 19
+[(3, 1, 0), (5, 4, 3), (0, 2, 5), (6, 3, 1), (8, 7, 6), (9, 5, 2), (10, 6, 3), (1, 3, 6), (16, 11, 7), (6, 7, 8), (12, 8, 5), (2, 5, 9), (14, 9, 5), (18, 17, 16), (15, 16, 17), (20, 19, 18), (17, 18, 19), (19, 13, 8), (5, 8, 12)]
No results found