triangle.py

# coding: utf-8

# In[114]:

class Game:
    
    def __init__(self, init_pos, dim):
        self.dim = dim
        self.board = [1] * int(dim * (dim + 1) / 2)
        self.board[init_pos] = 0
        self.directions = [ (-1, 0), (-1, -1), (0, -1), (0, 1), (1, 0), (1, 1)]
        self.loc = [ int(k * (k + 1) /2) for k in range(dim)]
        self.moves_made = 0
        self.max_depth = len(self.board) - 2

    
    def init_positions(self):
        for n in range (self.dim):
            for r in range(n + 1):
                yield (n, r)
                
    def final_positions(self):
        for n in range (self.dim):
            for r in range(n + 1):
                yield (n, r)
    
    def set_init_pos(self, init_pos):
        self.board = [1] * int(self.dim * (self.dim + 1) / 2)
        self.board[self.position(init_pos)] = 0
        self.moves_made = 0
    
    def set_final_pos(self, final_pos):
        self.board = [0] * int(self.dim * (self.dim + 1) / 2)
        self.board[self.position(final_pos)] = 1
        self.moves_made = self.max_depth
            
    
    def generate_moves(self):
        for move in self.candidate_moves():
            if (self.is_valid(move)):
                yield move
                
                
    def generate_moves_reverse(self):
        for move in self.candidate_moves():
            if (self.is_valid_reverse(move)):
                yield move


    def bounds(self, pos):
        (n, r) = pos
        return 0 <= n and 0<= r and n < self.dim and r <= n
    
    def position(self, pos):
        (n, r) = pos
        return self.loc[n] + r
    
    def value(self, pos):
        return self.board[self.position(pos)]
    
    def clear(self, pos):
        self.board[self.position(pos)] = 0
        
    def place(self, pos):
        self.board[self.position(pos)] = 1

    def explain(self, move):
        (n1, r1, (nc, rc)) = move
        (n2, r2) = (n1 + nc, r1 + rc)
        (n3, r3) = (n2 + nc, r2 + rc)
        return ((n1, r1), (n2, r2), (n3, r3))
        
    def is_valid(self, move):
        (p1, p2, p3) = self.explain(move)
        if self.bounds(p1) and self.bounds(p2) and self.bounds(p3):
            if (self.value(p1) == 1 and self.value(p2) == 1 and self.value(p3) == 0):
                return True
        
        return False
    
    def is_valid_reverse(self, move):
        (p1, p2, p3) = self.explain(move)
        if self.bounds(p1) and self.bounds(p2) and self.bounds(p3):
            if (self.value(p1) == 0 and self.value(p2) == 0 and self.value(p3) == 1):
                return True
        
        return False
            
    
    def make_move(self, move):
        (p1, p2, p3) = self.explain(move)
        self.clear(p1)
        self.clear(p2)
        self.place(p3)
        self.moves_made += 1
        
    def undo_move(self, move):
        (p1, p2, p3) = self.explain(move)
        self.place(p1)
        self.place(p2)
        self.clear(p3)
        self.moves_made -= 1

    
    def candidate_moves(self):
        for n in range(self.dim):
            for r in range(1 + n):
                for d in self.directions:
                    yield (n, r, d)
                    
                    
    def complete(self):
        return self.moves_made == len(self.board) - 2
                    
        


# In[115]:

class Search:
    
    def __init__(self, game):
        self.game = game
        self.solutions = []
        self.reverse_map = {}
        self.reverse_map_count = {}
        self.reverse_len = int(game.max_depth / 2)
        self.forward_len = game.max_depth - self.reverse_len
        self.solution_count = 0
    
    def solve(self):
        
        for final_pos in self.game.final_positions():
            self.game.set_final_pos(final_pos)
            self.fill_reverse(0, [])
            

        for init_pos in self.game.init_positions():
            self.game.set_init_pos(init_pos)
            if self.search(0, []):
                return True
            
        return False
        
    
    def search(self, depth, path):
        if depth == self.forward_len:
            # if tuple(self.game.board) in self.reverse_map:
                # self.solutions.append(path + self.reverse_map[tuple(self.game.board)][::-1])
                # return False
            
            if tuple(self.game.board) in self.reverse_map_count:
                self.solution_count += self.reverse_map_count[tuple(self.game.board)]
                return False
            
            
            return False
        
        for move in self.game.generate_moves():
            self.game.make_move(move)
            ret = self.search(depth + 1, path + [move])
            self.game.undo_move(move)
            if ret:
                return True
            
        return False        
    
    
    def fill_reverse(self, depth, path):
        
        if depth == self.reverse_len:
            if tuple(self.game.board) not in self.reverse_map:
                self.reverse_map[tuple(self.game.board)] = path
            
            if tuple(self.game.board) not in self.reverse_map_count:
                self.reverse_map_count[tuple(self.game.board)] = 1
            else:
                self.reverse_map_count[tuple(self.game.board)] = self.reverse_map_count[tuple(self.game.board)] + 1


            return False
        
        for move in self.game.generate_moves_reverse():
            self.game.undo_move(move)
            ret = self.fill_reverse(depth + 1, path + [move])    
            self.game.make_move(move)
            if ret:
                return True
            
        return False    
    


# In[116]:

g = Game(0, 5)


# In[117]:

s = Search(g)


# In[118]:

s.solve()


# In[120]:

print ("Number of solutions", s.solution_count)