[Python] Python: Implementing Depth-First Search for Freecell Solitaire

I've been trying so solve the Freecell Solitaire game with a DFS for well over a month now with only partial success. I'm a novice, with a non-CS background, that used classes and recursion for the first to solve a problem, mainly trying to imitate what I found through Google-searches and Stack Overflow posts. (general comments on code clarity etc are more than welcome)

The code for the game is here: https://pastebin.com/39KGZAW1, which I hope is understandable. The idea behind it is:

• Create instances of the Board (class), something like snapshots in the game
• Find all possible moves
• Create one new instance per move and update (class function) the board with that move

The problems are:

• It seems to be taking too long (the computer ran out of memory when I tried saving every board, so I stopped and used a generator and a deque), never finding a solution
• When I tried using mini_stacks (a card deck with less than 13 cards, currently just 1s and 2s!) it doesn't seem to be finding any solutions either.
• The recursive approach seems faster (at least comparing how many Boards instances are created) than the two implementations of the while-loop

More details: After the game logic is coded, I mainly tried two approaches to the DFS. The first was with a recursive function:

def rec(board):

if not board.moves:
return
else:
for i in board.moves:
new = copy.deepcopy(board) # instead of a deep copy I also tried
# creating a new instance taking inputs directly from the board
globals()["it"] += 1 # for lack of a better way
new.tt = globals()["it"]
new.update(i)
if new._end == True:
raise Exception("Solved!") # didn't focus on this yet
boards.append(new)
rec(new)

game = Board(mini_stacks) # or full_stacks, to initialize the recursion
rec(game) # start the recursion with the game


The second approach was using a while loop:

game = Board(mini_stacks)
boards = deque()
boards.append(game)
while boards:

current_search = boards.popleft()
if current_search._end:
print("Win")
winning = copy.deepcopy(current_search)
break # win

if current_search.moves:
for no,move in enumerate(current_search.moves):
new = copy.deepcopy(current_search)
it += 1
new.tt = it
new.update(move)
boards.insert(no,new)


With a slight modification, I created a generator function (also new to the concept) and used it for the while loop, adding a stack (=deque?):

def next_generator(boards=boards):

if boards[0].moves:
for no,move in enumerate(boards[0].moves):
new = copy.deepcopy(boards[0])
globals()["it"] += 1
new.tt = globals()["it"]
new.update(move)
boards.append(new)
yield boards.popleft()

while True:

current_search = next(next_generator())
if current_search._end:
print("Win")
winning = copy.deepcopy(current_search)
break # win

game = Board(mini_stacks)
boards = deque()
boards.append(game)
next_generator()


After a bit over 8 years (!) someone pointed out that the link is dead. I happened to find what is likely the code I used. It takes multiple minutes to run (and I'm not even sure if it'll ever finish) and gobbles up RAM without ever freeing it, but if you still care about someone's code who barely knew how to code at the time (even though any modern small language model can generate a better, shorter, faster solution in seconds), here you go:

from itertools import chain, islice
from queue import Queue
from collections import deque, defaultdict
import copy
import time
import sys
sys.setrecursionlimit(1500) # http://stackoverflow.com/a/3323008

mini_stacks = [
[(1, 'H'), (2, 'S'),],
[(1, 'D'), (2,'C'),(1, 'S')],
[(2, 'H'),(1, 'C'), (2, 'D')]]

my_stacks = [
[(1, 'H'), (2, 'S'), (6, 'C'), (11, 'S'), (11, 'C'), (4, 'H'),(2,'C')],
[(4, 'C'), (11, 'D'), (4, 'S'), (9, 'C'), (12, 'C'), (13, 'H'), (4, 'D')],
[(10, 'H'), (6, 'S'), (1, 'D'), (12, 'H'), (3, 'S'), (12, 'S'), (12, 'D')],
[(5, 'D'), (1, 'S'), (8, 'D'), (10, 'C'), (7, 'S'), (9, 'S'), (6, 'H')],
[(2, 'H'), (5, 'C'), (7, 'H'), (10, 'S'), (2, 'D'), (11, 'H')],
[(7, 'C'), (5, 'H'), (9, 'D'), (8, 'C'), (13, 'D'), (13, 'C')],
[(9, 'H'), (6, 'D'), (1, 'C'), (5, 'S'), (7, 'D'), (13, 'S')],
[(3, 'D'), (3, 'H'), (3, 'C'), (8, 'H'), (10, 'D'), (8, 'C')]]


it = 0

class Board:

def __init__(self, stacks):

self._end = False

self.stacks = stacks
self.freecell = {'one':0,'two':0,'three':0}
self.foundation = self.__foundation()
self.memory = deque()
self.memory.append("move 0")

self.moves = self.search_for_moves()
self.tt = globals()["it"]

def __repr__(self):
return "BoardInstance({!r})".format(self.tt)

def __foundation(self):
d = defaultdict(list)
for k in ["H","S","C","D"]:
d[k] = []
return d

def search_for_moves(self):

self._moves = []

if self.memory[0] in list(islice(self.memory, 1, 3)):
return []

# possible mistake here, did a small fix
for no, card in enumerate(x[-1] if len(x) > 0
else 0 for x in self.stacks):
if card != 0: self.add_moves(("stack", no, card))

for key in self.freecell:
if self.freecell[key] != 0:
self.add_moves(("freecell", key, self.freecell[key]))

return self._moves

def add_moves(self,card):

# irrelevant to where the card comes from,
# check if it can be added to a foundation
for k, found in self.foundation.items():

# card[2] is the actual tuple of the card, e.g. (2,"C")
if card[2][1] == k:
if len(found) == 0:
if card[2][0] == 1:
tup = ("foundation",k)
self._moves.append((card,tup))
break
else:
if (card[2][0] == int(found[-1][0]) + 1):
tup = ("foundation",k)
self._moves.append((card,tup))
break


# if the card is NOT already in a freecell, we can move it to one
if card[0] != "freecell":
for k,v in self.freecell.items():
if v==0:
tup = ("freecell", k)
self._moves.append((card,tup))
break

# if the card IS in a freecell, it can go back to stacks
else:
for no, stack in enumerate(self.stacks):
if stack:
# different shape (not color) +
if ((stack[-1][1] != card[2][1]) and
(stack[-1][0] == card[2][0] + 1)):
tup = ("stack", no)
self._moves.append((card,tup))
else:
tup = ("stack", no)
self._moves.append((card,tup))


return None


def update(self, move):

self.memory.append(move)

move_from, move_to = move
card_to_move = move_from[2]

# FROM (remove card)
if move_from[0] == "freecell":
self.freecell[move_from[1]] = 0

elif move_from[0] == "stack":
try: self.stacks[move_from[1]].pop()
except: self.stacks[move_from[1]] = self.stacks[move_from[1]]

# TO
if move_to[0] == "freecell":
if self.freecell[move_to[1]] == 0:
self.freecell[move_to[1]] = card_to_move
elif move_to[0] == "foundation":
self.foundation[move_to[1]].append(card_to_move)
elif move_to[0] == "stack":
self.stacks[move_to[1]].append(card_to_move)

self.distance = 0
win = 0
for k,v in self.foundation.items():
if isinstance(v,list) and len(v) == 5:
win += 1
self.distance += len(v)
if win == 4:
self._end = True


self.moves = self.search_for_moves()

return


start_time = time.time()
game = Board(mini_stacks)
boards = deque()
boards.append(game)
winning = None


def next_generator(boards=boards):

if boards[0].moves:
for no,move in enumerate(boards[0].moves):
new = copy.deepcopy(boards[0])
globals()["it"] += 1
if it % 10000 == 0:
elapsed = time.time()-start_time
mins, secs = int(elapsed // 60), elapsed % 60
print("{:,} done in {:.0f} minutes {:.2f} seconds.".format(it,mins, secs))
if it > 100000: break
new.tt = globals()["it"]
new.update(move)
boards.append(new)
yield boards.popleft()


while True:

current_search = next(next_generator())
if current_search._end:
print("Win")
winning = copy.deepcopy(current_search)
break # win

Continue reading...