pythonpython-3.xrecursiondepth-first-search

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:

The problems are:

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
Solution

  • So after taking a break I found it. As it seems, it was not the recurion nor the while loops. I did the following:

    Major changes in the core code (pastebin link):

    Minor changes in the core code:

    Using the second approach (while loop without function definitions) I tested for stacks of various sizes. When taking too much time, I stop the program, shuffle the deck and re-run. It found solutions relatively fast for sizes 2-6, and then for 7+ the time (as well as Board objects created) skyrockets. I tried with 9,11 and 13 cards but it didn't find a solution quickly and I got bored eventually.

    Here you can see no of Boards created till solution (or stop) of 5 re-runs (shuffles) per deck size.

    Cards vs boards