Better algorithm for determining sequence of moves needed to reach a success state in game
Solution 1:
I actually thought this was a fun game, so I wrote a quick solution that:
- defines the game so you can play it
- solves the game by building a tree of all possible moves (without duplicates)
- tells you what the minimum number of needed moves for a game is and shows you the resulting steps (for one of the possible solutions)
Edit: the first version I posted actually didn't remove empty columns and allowed 1 block moves - so I updated the answer here, same main idea though.
import random
# plays and solves http://g.fromgame.com/game/13/
class Game:
def __init__(self, width, height, colours=2):
self.width = width
self.height = height
self.colours = colours
self.board = [[0 for __ in range(width)] for __ in range(height)]
def generate(self, seed=0):
# very naive way to generate a board,
# heavily biased towards horizontal runs, not really important
random.seed(seed)
self.board = []
while len(self.board) < self.width * self.height:
self.board.extend([random.randint(0, self.colours)] * random.randint(1, self.width // 2))
self.board = [self.board[i*self.width:(i+1)*self.width] for i in range(self.height)]
self.drop()
def drop(self):
# simply gravity, keeps dropping blocks until they are all at the 'bottom'
dropped = True
while dropped:
dropped = False
for lower, above in zip(reversed(self.board), list(reversed(self.board))[1:]):
for i in range(len(lower)):
if lower[i] == 0 and above[i] != 0:
lower[i] = above[i]
above[i] = 0
dropped = True
# move columns to the left, leaving no empties
rc = [i for i, c in enumerate(self.board[-1]) if c == 0]
self.board = [[c for i, c in enumerate(line) if i not in rc] + [0 for __ in range(len(rc))] for line in self.board]
def copy(self):
# returns a completely new copy of this game
game = self.__class__(self.width, self.height, self.colours)
game.board = [line.copy() for line in self.board]
return game
def print(self):
for line in self.board:
print(''.join(map(str,line)))
def get_move(self, start_x, start_y):
# returns all the pairs x, y that would be removed if the block at x, y is removed
if self.board[start_y][start_x] == 0:
return []
colour = self.board[start_y][start_x]
queue = [(start_x, start_y)]
result = {(start_x, start_y)}
def add(a, b):
if (a, b) not in result and self.board[b][a] == colour:
result.add((a, b))
queue.append((a, b))
while queue:
x, y = queue.pop(0)
if x+1 < self.width:
add(x+1, y)
if y+1 < self.height:
add(x, y+1)
if x-1 >= 0:
add(x-1, y)
if y-1 >= 0:
add(x, y-1)
return result
def get_all_moves(self):
# finds a set of all possible moves (as tuples of moves that are all the same move)
moves = set()
for y in range(self.height):
for x in range(self.width):
if self.board[y][x] > 0 and not any((x, y) in m for m in moves):
m = self.get_move(x, y)
# only moves of more than one block are valid
if len(m) > 1:
moves.add(tuple(m))
return moves
def make_move(self, move):
for x, y in move:
self.board[y][x] = 0
self.drop()
def check_won(self):
# returns whether the game has been completed assumes all positive colours
return sum(sum(line) for line in self.board) == 0
def play(self):
# trivial if there's nothing on the board, win in 0 moves, 1 path, empty moves
if self.check_won():
return 0, 1, {}
# otherwise play all possible moves until conclusion
moves = {}
size = self.width * self.height
min_d = size # worst case as many moves as squares
total = 0
for move in self.get_all_moves():
next_state = self.copy()
next_state.make_move(move)
d, n, rest = next_state.play()
# only save the move if there's a way to win the game after this move
if d < size:
moves[(move[0], d)] = rest
total += n
min_d = min(min_d, d+1)
return min_d, total, moves
def main():
g = Game(4, 5)
g.generate(seed=1)
print('Start of the game:')
g.print()
min_moves, paths, moves = g.play()
if min_moves == g.width * g.height:
print('Game cannot be won!')
else:
g_copy = g.copy()
print(f'The first winning play in {min_moves} moves, out of {paths} possible different games:')
options = moves
n = min_moves
x, y = 0, 0
next_options = {}
while n > 0:
for ((x, y), c), next_options in options.items():
if c == n:
break
print(f'Make move {(x, y)}:')
g_copy.make_move(g_copy.get_move(x, y))
g_copy.print()
n -= 1
options = next_options
if __name__ == '__main__':
main()
This plays the game with a tiny board of 4x5, and the output:
Start of the game:
0101
0111
1122
1121
2211
The first winning play in 3 moves, out of 11 possible different games:
Make move (2, 3):
0100
0101
1101
1111
2211
Make move (2, 4):
0000
0000
0000
0000
2200
Make move (0, 4):
0000
0000
0000
0000
0000
Note that it numbers the board from top-left to lower-right, so 0,0 is top-left and 4,5 is lower-right in this example. The random seed is set, so you get the same result every time you run, though not necessarily the same game on every computer, this depends on the implementation of random - you could add a .save() and .load() function if you need more repeatability.
Note that the answer to your question is really just the play method together with the get_move and get_all_moves methods - which show how to build a tree of possible moves, depth-first with backtracking (using recursion - so limiting the board size through recursion depth, it would doable but a little less readable without recursion).
Also note that after this line: min_moves, paths, moves = g.play(), moves contains the full tree of all possible moves, given the game g, played to conclusion. It's worth having a look in a debugger to see what's actually generated - it's too big to print here.
To see how many solutions of each length there are:
from collections import defaultdict
counts = defaultdict(int)
def count(ms, n):
for m, k in ms:
if k == 0:
counts[n] += 1
else:
count(ms[(m, k)], n+1)
count(moves, 0)
print(counts)
For this example:
defaultdict(<class 'int'>, {2: 7, 3: 4})