In [1]:
from numpy import asarray
import numpy
npsum = numpy.sum

The following LayerGame class will let us encapsulate game state via a numpy array (board) and associated methods for finding/checking valid moves, making moves, and checking for end-game conditions.

In [2]:
class LayerGame:
    
    def __init__(self, board, star):
        self.board = board
        self.n_rows, self.n_cols = self.board.shape
        self.star = star
    
    def surrounding_coordinates(self, r, c, color='green'):
        target = 1 if color is 'green' else 0
        coordinates = []
        if r > 0 and self.board[r - 1, c] % 2 == target:
            coordinates.append((r - 1, c))
        if r < self.n_rows - 1 and self.board[r + 1, c] % 2 == target:
            coordinates.append((r + 1, c))
        if c > 0 and self.board[r, c - 1] % 2 == target:
            coordinates.append((r, c - 1))
        if c < self.n_cols - 1 and self.board[r, c + 1] % 2 == target:
            coordinates.append((r, c + 1))
        return coordinates
    
    def valid_move(self, r, c):
        if self.board[r, c] == 0:
            coordinates = self.surrounding_coordinates(r, c)
            if len(coordinates) > 1:
                return True
        return False
    
    def valid_moves(self):
        for r in range(self.n_rows):
            for c in range(self.n_cols):
                if self.valid_move(r, c):
                    yield r, c
    
    def make_move(self, r, c):
        '''caller should check `valid_move` before calling `make_move`'''
        coordinates = self.surrounding_coordinates(r, c)
        self.board[r, c] = 1
        for r, c in coordinates:
            self.board[r, c] = 0
        for r in range(self.n_rows):
            for c in range(self.n_cols):
                if self.board[r, c] == 3:
                    self.board[r, c] = 4
                elif self.board[r, c] == 4:
                    self.board[r, c] = 3
    
    def success(self):
        if npsum(self.board.flatten()) == 1 and self.board[self.star[0], self.star[1]] == 1:
            return True
        return False
    
    def copy(self):
        return LayerGame(self.board.copy(), self.star)

The following level layout corresponds to Threat level 21.

In [3]:
level = asarray([[0, 0, 0, 0, 0, 0],
                 [3, 0, 3, 1, 0, 0],
                 [0, 1, 1, 0, 0, 0],
                 [0, 0, 3, 0, 0, 0],
                 [0, 0, 1, 1, 0, 0],
                 [0, 0, 1, 0, 0, 0]])
star = (3, 2)

To test out LayerGame object, we instantiate it, and check that its valid_move method works as expected.

In [4]:
game = LayerGame(level, star)
In [5]:
# test all occupied spaces
for r, c in [(1, 0), (1, 2), (1, 3), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (5, 2)]:
    assert(game.valid_move(r, c) == False)
# test all far away spaces
for r, c in [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 4), (1, 5), (2, 4), (2, 5), (3, 0), (3, 4), (3, 5), (4, 0), (4, 1), (4, 4), (4, 5), (5, 0), (5, 1), (5, 4), (5, 5)]:
    assert(game.valid_move(r, c) == False)
# test valid spaces
for r, c in [(1, 1), (2, 0), (2, 3), (3, 1), (3, 3), (5, 3)]:
    assert(game.valid_move(r, c) == True)
In [6]:
print(game.board)
[[0 0 0 0 0 0]
 [3 0 3 1 0 0]
 [0 1 1 0 0 0]
 [0 0 3 0 0 0]
 [0 0 1 1 0 0]
 [0 0 1 0 0 0]]

Finally, to determine what moves to make to solve the puzzle, we do a recursive brute forces check of all possible moves. We store the successful moves in a list.

In [7]:
def test(game, moves):
    if game.success():
        return True
    for r, c in game.valid_moves():
        copy = game.copy()
        copy.make_move(r, c)
        if test(copy, moves):
            moves.insert(0, (r, c))
            return True
    return False
In [8]:
moves = []
test(game, moves)
Out[8]:
True
In [9]:
moves
Out[9]:
[(3, 1), (3, 2), (1, 1), (1, 2), (2, 2), (4, 2), (3, 2)]