Solving "Infinite Loop" - Part 1
In this episode of "Ankit tries to set an ambitious goal and attempts to solve it incrementally over a decade", we will be trying to make a bot that plays the android game "Infinite Loop"
- Nerd Sniped
- Introduction
- Getting Tiles from an Image
- Developing an Algorithm
- Can we use Maximum Network Flow?
- What else can we use?
- Pitfalls and Future Work
Nerd Sniped
Many years ago, I was the unsuspecting victim of a nerd sniping incident. I first came across Infinite Loop in 2015. An iOS and Android game Designed by Jonas Lekevicius. Jonas was inspired by the flash game "Loops of Zen" by Dr. Arend Hintze. In Jonas' words,
Infinite Loop is a very simple, relaxing and never ending game for iPhone, iPad and Android. Your goal is to turn all forms on the grid so that there would be no open connections. Most levels are algorithmically generated and randomly colored, and after successfully completing each level you will be rewarded with a beautiful design of your own making.
Jonas is not wrong. The game is relaxing but also addictive.
My girlfriend at the time was obsessed with the game. Before I knew it she was more than a thousand levels into the game. As a young undergraduate, I was competitive. To a fault. I had to find a way to play the game without playing the game. If I was going to hit level 1000, I needed to game the game. I spent about a month of actual work trying to figure out a backtracking algorithm to solve the board position and then figuring out how to connect the python script to my phone. Unfortunately an algorithm bug and life in general made me forget about the game and hitting level 1000.
It's 2022 now and I think it is high time I had a blog with an interesting post or two. This spring I took CS5800, Introduction to Algorithms by Dr. Abhi Shelat. Towards the end of the course we were introduced to the applications of Maximum Flow algorithms. I had an intense sense of deja vu when I read what was on Homework 10. Matching things adjacent to each other. Tiling dominoes on a grid.
This Summer, I decided to give Solving Infinite Loop another shot. In Part 1 of this series, we will use basic image processing to get game tiles from a screenshot and explore algorithms to solve the game. In Part 2 , We will use some basic computer vision to make a more robust image to game tile converter. Let's begin!
Introduction
An arbitray level of Infinite Loop is composed of a rectangular grid (Rows and Columns, 2D Array/List) of tiles. We have 5 types of tiles with different number of outgoing edges (the degree of a tile). For tiles with degree 2, there are 2 types of tiles possible. Each tile can of course be rotated along its center. Different tiles have different number of possible rotations.
Let us try to define a couple of helper functions to make our lives easier. We will first define a function that will list out all the possible rotations of a tile. We represent each tile with a 4 bit binary number going clockwise. A tile of degree 1 with its edge pointing up is represented as 1000. The different rotations of this tile are obtained by left or right shifting the number till we get the original number. For 1000, we get 1000, 0001, 0010 and 0100.
def cycleOrientations(orientation):
"""
Takes a list as input and returns a list of all
possible rotations of the input list.
"[a,b,c]" -> "[a,b,c],[b,c,a],[c,a,b]"
"""
out = []
out.append(orientation)
# let t be the first orientation
t = orientation.copy()
# add the first element of the list to the end
t.append(t.pop(0))
# while t is not the same as the first orientation
# repeat the above operation and add it to the
# list of possible orientations
while t != orientation:
out.append(t.copy())
t.append(t.pop(0))
return out
print("\"1010\" : ", cycleOrientations(list("1010")))
print("\"0001\" : ", cycleOrientations(list("0001")))
print("\"1111\" : ", cycleOrientations(list("1111")))
Getting Tiles from an Image
Onto extracting tiles from an image. For an image of a game level, we want a 2D array of tiles. Let us look at a screenshot.
This level is a 11x6 grid. Each tile is square of the same side length. There are three colors in the image. A background color, a tile color and a faint line color used for the UI icon. We can say for cetrain that the most frequent color in the image is the backround color and most non trivial game levels have more pixels of the tile color than the UI icon color. We will define a function that takes as input an image path and returns a black and white image with only the tile color colored white and the background color black.
# for basic image processing
from PIL import Image,ImageDraw
# for fast math
import numpy as np
import math
# to display images and graphs
import matplotlib.pyplot as plt
# for nodes and edges
import networkx as nx
# for io stuff
import io
print('Importing PIL, numpy, matplotlib, networkx')
im_path = "./imgs/1/20220604-003503.png"
def screenshotToBw(path):
"""
Take an input image and return a black and white image
"""
# open the image
im = Image.open(path)
# convert it to grayscale
im = im.convert('L')
# count the unique values
unique, counts = np.unique(
im.__array__(),
return_counts=True
)
# sort values and counts
Z = [x for _,x in sorted(zip(counts,unique))]
# select the 2 most common values
b,w = Z[-2:]
# set the first value
# as the thresholding tile color
thresh = b
# for each pixel if the pixel within
# 2 values of the threshold set it to
# white else set it to black
im = im.point(
lambda x : 255 if abs(x - b) < 2 else 0,
mode='1'
)
return im
screenshotToBw(im_path).resize((288,512),Image.NEAREST)
Thanks to the black background we can find the bounding box of the game. PIL has a handy function getbbox that returns the bounding box of a black and white image. This bounding box is not exactly the size of the grid. However, if we assume that a tile is of a constant side length and the game is always aligned to the center of the screenshot, we can infer the number of columns and rows of the grid. If the tile side length is assumed to be C, then the width of the grid should be columns x C and the height rows x C. Thus inversely, the number of columns is ceil(width of the bbox / C) and the number of rows is ceil(height of the bbox / C). Armed with this insight we can define a function that takes as input a black and white image and returns the a 2D array of bounding boxes for each tile.
def bwToBboxes(im,C=134):
"""
Converts a black and white image and a size length to a list of bounding boxes
Caveat : Here we assume that the image has a game board aligned with the midpoint
of the image and has a known tile side-length.
"""
# get image bounding box
bbox = im.getbbox()
# get the image width and height
w, h = im.size
# get the bbox width and height
W = bbox[2] - bbox[0]
H = bbox[3] - bbox[1]
# get the number of rows and columns
Col,Row = math.ceil(W/C),math.ceil(H/C)
# calculate the center of the image
mid_x = w/2
mid_y = h/2
# create an empty list of bounding boxes
boxes = []
for row in range(Row):
t = []
for col in range(Col):
# calculate the top left coordinates for each bounding box
# If the coordinates of the center are (mid_x,mid_y)
# and the game is center aligned the top left corner of the game
# has to be 1/2 the width and height of the
# game board from the center of the image
p_x = (mid_x - (Col * C / 2)) + col * C
p_y = (mid_y - (Row * C / 2)) + row * C
t.append([int(p_x),int(p_y),int(p_x+C),int(p_y+C)])
boxes.append(t)
return boxes
Let's take a look at the boxes returned by the function.
def drawBoxes(im,boxes):
"""
Draws bounding boxes on an image
"""
# create a new image
im_out = Image.new(im.mode,im.size)
# create a draw object
draw = ImageDraw.Draw(im_out)
# copy the image
im_out.paste(im)
# draw the bounding boxes
for row in boxes:
for box in row:
draw.rectangle(box,outline='red',width=2)
return im_out
im = screenshotToBw(im_path)
boxes = bwToBboxes(im)
drawBoxes(im,boxes).resize((576,1024),Image.NEAREST)
Now that we have individual bounding boxes we can take a look at the individual tiles for the pixels on the midpoints of the north, east, south and west edges.
A cropped image of a tile at position 1,1 looks like this.
im_cropped = im.crop(boxes[1][0])
display(im_cropped)
print("Size of the tile : " , im_cropped.size)
print("Pixel at North corner : " , im_cropped.getpixel((im_cropped.width/2,0)))
print("Pixel at East corner : " , im_cropped.getpixel((im_cropped.width-1,im_cropped.height/2)))
print("Pixel at South corner : " , im_cropped.getpixel((im_cropped.width/2,im_cropped.height-1)))
print("Pixel at West corner : " , im_cropped.getpixel((0,im_cropped.height/2)))
Based on the values at each pixel position we can begin to construct binary representations of the tiles.
def getTiles(im,C=134):
"""
Takes an image and a tile size and returns a 2D list of tiles
"""
tiles = []
# use the bwToBboxes function to get the bounding boxes
bboxes = bwToBboxes(im,C)
for i,row in enumerate(bboxes):
# create a temporary row
v = []
for j,box in enumerate(row):
# for each bounding box crop the image
# and get the NESW pixel values
t = []
cropjorts = im.crop(box)
pxN = cropjorts.getpixel((int(C/2),0))
pxS = cropjorts.getpixel((int(C/2),C-1))
pxE = cropjorts.getpixel((C-1,int(C/2)))
pxW = cropjorts.getpixel((0,int(C/2)))
# append 1 if the pixel is white else 0
t.append(1 if pxN == 255 else 0)
t.append(1 if pxE == 255 else 0)
t.append(1 if pxS == 255 else 0)
t.append(1 if pxW == 255 else 0)
v.append(t)
tiles.append(v)
return tiles
Thus for the game image we have the following tiles:
smol_image = im.crop(im.getbbox())
w,h = smol_image.size
r = w/h
t_H = 500
t_W = int(t_H * r)
display(smol_image.resize((t_W,t_H),Image.NEAREST))
tiles = getTiles(im)
for row in tiles:
for tile in row:
print("".join(map(str,tile)),end=' ')
print()
Developing an Algorithm
Now that we have game tiles from the screenshot, we can begin developing an algorithm. An approach is to select a possible tile orientation and check if it is part of a valid solution and incrementally add tiles to the solution. If we find an invalid tile we try another option, if there are no available options we backtrack to the previously added tile and try another option from the list of possible rotations and move on to the next tile.
I know that sounds complicated but what we are trying to do can be imagined as a large tape of tapes with pointers. Each time we try an option we move the pointer forward and if we would like to undo we move the pointer back. We can also set the pointer back to the beginning of the tape. This sounds a lot like a data structure begging to be implemented. So let's get to implementing it.
The BigTape class
The BigTape class implementation can be described as follows.
- Properties
-
data, a list of items of any data type -
current, an integer that points to the current position of the pointer -
length, the length of the data list
-
- Methods
-
add(item), add an item to the tape -
addItems(items), add a list of items to the tape -
select(), return the item at the current position of the pointer and increment the pointer -
undo(), move the pointer back one position -
top(), return the item at the current position of the pointer without incrementing the pointer -
reset(), set the pointer to the beginning of the tape
-
class BigTape:
# create a tape object with an empty list
# and a tape length and current position of 0
def __init__(self):
self.data = []
self.current = 0
self.length = 0
# add a value to the list
# and increment the tape length
def add(self,item):
self.data.append(item)
self.length += 1
# add lots of values to the list
def addItems(self,items):
for i in items:
self.add(i)
# get the value at the current position
# and increment the current position
# if the current position is greater than the length
# of the tape return None
def select(self):
if self.length > 0 and self.current < self.length:
out = self.data[self.current]
self.current += 1
return out
else :
return None
# get the value at the current position
# if the current position is greater than the length
# of the tape return None
def top(self):
if self.length > 0 and self.current < self.length:
out = self.data[self.current]
return out
else :
return None
# decrement the current position
def undo(self):
if self.length > 0 :
self.current -= 1
# set the current position to 0
def reset(self):
self.current = 0
Pseudocode
Let's now write the algorithm in pseudocode.
- tileTape, a BigTape object that holds the different valid tile orientations as BigTape objects
- While we still have tiles available to select in the tileTape
- Select a tile
- If the tile has available orientations
- Select an orientation
- Check if the orientation is valid
- If it is valid
- Add the tile orientation to the solution
- If it is not valid
- Undo the tileTape
- If there are no more orientations available for the tile
- Reset the orientation tape of the selected tile
- Undo the tileTape
- Undo the tileTape
- Remove the last tile from the solution
Valid Orientations
Valid orientations are orientations that can be placed on the board. For example, a tile on the west edge of the game board cannot face west because there is no tile to connect to in the west.
We can visualize the entire set of tiles as a graph with nodes and edges. Let us begin with a grid graph with the same shape as the tiles array.
rows, cols = len(tiles),len(tiles[0])
G = nx.grid_2d_graph(rows,cols)
pos = {(x,y):(y,-x) for x,y in G.nodes()}
plt.figure(3,figsize=(len(tiles[0]),len(tiles)))
nx.draw(G, pos, with_labels=True, node_size=1300,node_color='0.7',edge_color='black')
Let us now remove nodes with empty tiles. An empty tile has the bit pattern 0000.
for i,row in enumerate(tiles):
for j,tile in enumerate(row):
if sum(tile) == 0:
G.remove_node((i,j))
pos = {(x,y):(y,-x) for x,y in G.nodes()}
plt.figure(3,figsize=(len(tiles[0]),len(tiles)))
nx.draw(G, pos, with_labels=True, node_size=1300,node_color='0.7',edge_color='black')
For tile (3,0), the tile is a 1000 tile and from the graph it is obvious that the only valid sets of orientations are 1000 , 0100 and 0010. We can represent these as edge lists. In this case we have two edge lists for the two valid orientations. The first edge list is (3,0) to (2,0). The second edge list is (3,0) to (3,1). Finally we have (3,0) to (4,0). Let's write a couple of functions to list out the valid neighbour lists for each tile.
def getNeighbours(r,c):
"""
Returns a list of neighbours of a tile
(1,0) -> (0,1),(1,1),(2,0),(1,-1)
"""
return [(r-1,c),(r,c+1),(r+1,c),(r,c-1)]
def selectNeighbors(G,V,orientation):
"""
Select the neighbours of a tile in a given orientation
if the orientation is not valid return an empty list
V is a tuple (row,col)
G is a grid graph
orientation is a string 'N','E','S','W'
(1,0) , "0001" -> []
(1,0) , "0010" -> [((1,0)(2,0))]
"""
r,c = V
neighbours = getNeighbours(r,c)
out = []
for i,bit in enumerate(orientation):
if bit:
if neighbours[i] in G.adj[V]:
out.append((V,neighbours[i]))
else:
return []
return out
def getOptions(G,tiles,V):
"""
Get the edge list options for each tile
V is a tuple (row,col)
G is a grid graph
tiles is a 2D list of tiles
"""
r,c = V
# get all possible orientations of a tile
orientations = cycleOrientations(tiles[r][c])
out = []
# for each orientation get the neighbours in that orientation
# and add them to the list of options for that tile
for o in orientations:
n = selectNeighbors(G,V,o)
if n:
out.append(n)
return out
Let's populate some dictionaries to keep track of the degree of each tile and the valid neighbour lists for each tile.
degreeDict = {}
for v in G.nodes():
r,c = v
s = sum(tiles[r][c])
degreeDict[v] = s
optionDict = {}
for v in G.nodes():
optionDict[v] = getOptions(G,tiles,v)
The valid options we have for tile 2,0 are,
print("Edge options : ", optionDict[(2,0)])
print("Number of valid options : ", len(optionDict[(2,0)]))
print("Degree : ", degreeDict[(2,0)])
Let's now write a function to check if a set of options is valid or not.
def check(opList, opT, G, degreeDict):
"""
Check if adding opT to opList results in a valid game configuration
opT is an edge list
opList is a list of edge lists
"""
tempG = nx.Graph()
tempG.add_nodes_from(G.nodes())
# add the edges from opList to a temp graph
for op in opList:
for edge in op:
tempG.add_edge(edge[0],edge[1])
# add the edges from opT to the temp graph
for edge in opT:
tempG.add_edge(edge[0],edge[1])
flag = True
# check if the degree limits on each node are within bounds
for v in tempG.nodes():
if degreeDict[v] < tempG.degree[v]:
flag = False
return flag
break
return flag
tileTape = BigTape()
# add our options to the tile tape
for i in optionDict:
ops = optionDict[i]
tile = BigTape()
for j in ops:
tile.add(j)
tileTape.add(tile)
iton = list(G.nodes())
ntoi = {v:i for i,v in enumerate(iton)}
solution = []
sol_l = []
while tileTape.top():
n = tileTape.current
t = tileTape.select()
if t.top():
op = t.select()
f = check(solution,op,G,degreeDict=degreeDict)
sol_l.append({
"op":op.copy(),
"valid":f,
"sol":solution.copy(),
"n" : n
})
if f:
solution.append(op)
continue
else:
tileTape.undo()
else:
t.reset()
tileTape.undo()
tileTape.undo()
solution.pop()
tempG = nx.Graph()
tempG.add_nodes_from(G.nodes())
for op in solution:
for edge in op:
tempG.add_edge(edge[0],edge[1])
pos = {(x,y):(y,-x) for x,y in tempG.nodes()}
fig = plt.figure(3,figsize=(len(tiles[0]),len(tiles)))
nx.draw(tempG,
pos,
with_labels=True,
node_size=1300,
node_color='0.7',
edge_color='blue',
width=2)
Et Voila! It does. We have a backtracking algorithm that can solve arbitrary game levels. I know I blitzed through a lot of code so a nice little animation showing the algorithm as it works would be super refreshing 
So here's an animation of the algorithm running on the level above. The number on the bottom left corner of the animation is the number of the option being tried. The numbers near the vertices are the required out degree of the vertex. Edges are colored green if they are a valid option and red if they are not. If green the edges are added to the partial solution. The red circle around the vertex is the current tile being tried.
def drawSol(sol,oP,f,i,iton,tiles,G,ax=None):
tempG = nx.Graph()
tempG.add_nodes_from(G.nodes())
for op in sol:
for edge in op:
tempG.add_edge(edge[0],edge[1])
pos = {(x,y):(y,-x) for x,y in tempG.nodes()}
fig, ax = plt.subplots(figsize=(len(tiles[0]),len(tiles)))
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.spines['left'].set_visible(False)
nx.draw_networkx_edges(G,pos,ax=ax,edge_color='white',width=2)
nx.draw_networkx_edges(tempG,pos,ax=ax,edge_color='blue',width=2)
# draw edges in op as red
col = 'green' if f else 'red'
for edge in oP:
ax.plot([pos[edge[0]][0],pos[edge[1]][0]],[pos[edge[0]][1],pos[edge[1]][1]],color=col)
currentNode = iton[i]
# draw red transparent circle around current node
ax.plot(pos[currentNode][0],pos[currentNode][1],color='red',marker='o',markersize=10,alpha=0.5)
nx.draw_networkx_nodes(tempG,pos=pos,node_size=50,node_color='0.7',ax=ax)
# write degree dict values for each node
for v in tempG.nodes():
ax.text(pos[v][0] + 0.15 ,pos[v][1] + 0.15 ,str(degreeDict[v]) ,color='black',fontsize=10)
buf = io.BytesIO()
fig.savefig(buf)
buf.seek(0)
plt.close(fig)
return Image.open(buf)
imgs = []
for n,i in enumerate(sol_l):
i = drawSol(i["sol"],i["op"],i["valid"],i["n"],iton,tiles,G)
# add frame number in bottom left
draw = ImageDraw.Draw(i)
draw.text((0,i.size[1]-10),str(n),fill=(0,0,0))
imgs.append(i)
imgs[0].save("./imgs/1/out.gif", save_all=True, append_images=imgs[1:],duration=1000, loop=0)
def graphToTiles(G,r,c):
# for each node in the graph check its 2d neighbours and add them to the tile
out = {}
for v in G.nodes():
x,y = v
neigh = getNeighbours(x,y)
b = []
for n in neigh:
if n in G.adj[v]:
b.append(1)
else:
b.append(0)
out[v] = b
return out
# calculate right rotate ditance of two binary strings
def compare(fromList,toList):
i = 0
fl = fromList.copy()
tl = toList.copy()
while fl != tl:
fl.append(fl.pop(0))
i += 1
if i>4:
return 0
break
return i
def shiftsFromTiles(fromTiles,toTiles):
r = len(fromTiles)
c = len(fromTiles[0])
out = []
for i in range(r):
t = []
for j in range(c):
value = compare(fromTiles[i][j],toTiles[i][j])
t.append(value)
out.append(t)
return out
def mergeTiles(tileImages,tiles):
r,c = len(tiles),len(tiles[0])
t_w, t_h = tileImages[0][0].size
out = Image.new('RGB', (t_w*c, t_h*r))
for i,row in enumerate(tileImages):
for j,tile in enumerate(row):
out.paste(tile, (j*t_w, i*t_h))
return out
tiles = getTiles(im)
solutionTiles = graphToTiles(tempG,r,c)
toTiles = []
for r,row in enumerate(tiles):
row_ = []
for c,tile in enumerate(row):
if (r,c) in solutionTiles:
row_.append(solutionTiles[(r,c)])
else:
row_.append([0]*len(tile))
toTiles.append(row_)
shifts = shiftsFromTiles(tiles,toTiles)
tileImages = [[im.crop(box) for box in row] for row in boxes]
solutionImages = [[im.crop(box) for box in row] for row in boxes]
for i,row in enumerate(solutionImages):
for j,tile in enumerate(row):
if (i,j) in solutionTiles:
solutionImages[i][j] = tile.rotate(shifts[i][j]*90)
problem = mergeTiles(tileImages,tiles)
solved = mergeTiles(solutionImages,tiles)
plt.figure(figsize=(10,10))
plt.subplot(1,2,1)
plt.imshow(problem)
plt.axis('off')
plt.subplot(1,2,2)
plt.imshow(solved)
plt.axis('off')
plt.show()
The python library that connects with the game is called AndroidViewClient which connects to a running adb server and is able to simulate events such as taking a screenshot, touching the screen, etc. All the things we need to interact with the game.
Here's a smol timelapse of the game being played by the bot. Look Ma No Hands!
Can we use Maximum Network Flow?
Back to CS5800. The first problem on Homework 10 - "Given a grid of square tiles where some are colored black and some are blank, find if it is possible to cover the tiles with a set of domino tiles, where each domino tile is made of two adjacent square tiles i.e. is a rectangle". Prof. Shelat is usually kind enough to include hints on how to solve a problem. For this problem he advised us to look at it as a maximum bipartite matching problem. A problem that can be transformed into an instance of the max network flow problem.
What is a Maximum Bipartite Matching?
A Bipartite matching is a set of edges from one source set of vertices to another target set of vertices such that no two edges share the same source vertex and no two edges share the same target vertex. This means each item in the source set is matched to exactly one item in the target set. A maximum bipartite matching is a bipartite matching with the maximum number of edges. Meaning if we add a new edge to the matching it will cease to be a bipartite matching.
Let us now try to convert a game level into a bipartite matching problem. We color vertices in a checkerboard pattern. Tiles with odd sums are colored magenta and the rest are cyan. Our tile graph looks like this,
tG = nx.Graph()
tG.add_nodes_from(G.nodes())
pos = {(x,y):(y,-x) for x,y in tempG.nodes()}
fig, ax = plt.subplots(figsize=(len(tiles[0]),len(tiles)))
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.spines['left'].set_visible(False)
nx.draw_networkx_edges(G,pos,ax=ax,edge_color='0.7',width=2)
# color vertex cyan if sum of vertex coordinates is even
colors = ['c' if sum(x)%2 == 0 else 'm' for x in G.nodes()]
nx.draw_networkx_nodes(tG,pos=pos,node_size=50,node_color=colors,ax=ax)
buf = io.BytesIO()
fig.savefig(buf)
buf.seek(0)
plt.close(fig)
Image.open(buf)
We can move the sets over to the left and right to see them in the usual bipartite matching format.
setC = [ n for n in G.nodes() if sum(n)%2 == 0 ]
setM = [ n for n in G.nodes() if sum(n)%2 == 1 ]
colors = {n: 'c' if n in setC else 'm' for n in G.nodes()}
tDG = nx.DiGraph()
tDG.add_nodes_from(tG.nodes())
# draw edges from setC to setM
for n in setC:
for m in setM:
if m in G.adj[n]:
tDG.add_edge(n,m)
#position of setC nodes on the left of screen and setM nodes on the right
for i,n in enumerate(setC):
pos[n] = (0,i)
for i,n in enumerate(setM):
pos[n] = (1,i)
#pos = {(x,y):(y,-x) for x,y in tDG.nodes()}
fig, ax = plt.subplots(figsize=(len(tiles[0]),len(tiles)))
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.spines['left'].set_visible(False)
nx.draw_networkx_edges(tDG,pos,ax=ax,edge_color='0.7',width=2)
# color vertex cyan if sum of vertex coordinates is even
colors = ['c' if sum(x)%2 == 0 else 'm' for x in G.nodes()]
nx.draw_networkx_nodes(tDG,pos=pos,node_size=50,node_color=colors,ax=ax)
buf = io.BytesIO()
fig.savefig(buf)
buf.seek(0)
plt.close(fig)
Image.open(buf)
Wow what a mess, the grid layout with directed edges should be much easier to visualize.
setC = [ n for n in G.nodes() if sum(n)%2 == 0 ]
setM = [ n for n in G.nodes() if sum(n)%2 == 1 ]
colors = {n: 'c' if n in setC else 'm' for n in G.nodes()}
tDG = nx.DiGraph()
tDG.add_nodes_from(tG.nodes())
# draw edges from setC to setM
for n in setC:
for m in setM:
if m in G.adj[n]:
tDG.add_edge(n,m)
pos = {(x,y):(y,-x) for x,y in tDG.nodes()}
fig, ax = plt.subplots(figsize=(len(tiles[0]),len(tiles)))
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.spines['left'].set_visible(False)
nx.draw_networkx_edges(tDG,pos,ax=ax,edge_color='0.7',width=2)
# color vertex cyan if sum of vertex coordinates is even
colors = ['c' if sum(x)%2 == 0 else 'm' for x in G.nodes()]
nx.draw_networkx_nodes(tDG,pos=pos,node_size=50,node_color=colors,ax=ax)
buf = io.BytesIO()
fig.savefig(buf)
buf.seek(0)
plt.close(fig)
Image.open(buf)
What is Maximum Network Flow?
For any graph G the max network flow is the maximum amount of flow that can be sent from one vertex to another on the graph. Usually a flow network with source s and target t follows the following rules:
- The sum of flows going into a vertex must equal the sum of flows going out of that vertex for all vertices except
sandt. - The sum of flows going out of
smust equal the sum of flows going intot. - The flow going through an edge must be less than or equal to the capacity of that edge.
Bipartite Matching to max Network Flow
To convert a bipartite matching problem to a max network flow problem we add a new vertex s and a new vertex t to the graph. We then add an edge from s to each of the vertices in the source set and an edge from each of the vertices in the target set to t. We then add edges between vertices in the source set and adjacent vertices in the target set. Once we solve for the max network flow, we can recover the bipartite matching that results in the max network flow.
So all we need to do is add a source and sink to our directed graph.
setC = [ n for n in G.nodes() if sum(n)%2 == 0 ]
setM = [ n for n in G.nodes() if sum(n)%2 == 1 ]
tDG = nx.DiGraph()
tDG.add_nodes_from(tG.nodes())
# draw edges from setC to setM
for n in setC:
for m in setM:
if m in G.adj[n]:
tDG.add_edge(n,m)
pos = {(x,y):(y,-x) for x,y in tDG.nodes()}
tDG.add_node('s')
tDG.add_node('t')
pos['s'] = (-2,-len(tiles)//2+1)
pos['t'] = (len(tiles[0])+1,-len(tiles)//2+1)
for n in setC:
tDG.add_edge('s',n)
for n in setM:
tDG.add_edge(n,'t')
fig, ax = plt.subplots(figsize=(len(tiles[0])+4,len(tiles)))
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.spines['left'].set_visible(False)
colors = []
for n in tDG.nodes():
if n == 's':
colors.append('g')
elif n == 't':
colors.append('b')
elif sum(n)%2 == 0:
colors.append('c')
else:
colors.append('m')
nx.draw_networkx_nodes(tDG,pos=pos,node_size=50,node_color=colors,ax=ax)
edge_colors = []
edge_weights = []
edge_styles = []
for e in tDG.edges():
if e[0] == 's':
edge_colors.append('c')
edge_weights.append(0.5)
edge_styles.append('dashed')
elif e[1] == 't':
edge_colors.append('m')
edge_weights.append(0.5)
edge_styles.append('dashed')
else:
edge_colors.append('gray')
edge_weights.append(1)
edge_styles.append('solid')
nx.draw_networkx_edges(tDG,pos=pos,ax=ax,edge_color=edge_colors,width=edge_weights,style=edge_styles)
buf = io.BytesIO()
fig.savefig(buf)
buf.seek(0)
plt.close(fig)
Image.open(buf)
Once we perform the flow transformation and recover the matching, The Max Flow solution looks like this,
attrs = {}
for e in tDG.edges():
if e[0] == 's':
r,c = e[1]
attrs[e] = {'capacity':sum(tiles[r][c])}
elif e[1] == 't':
r,c = e[0]
attrs[e] = {'capacity':sum(tiles[r][c])}
else:
attrs[e] = {'capacity':1}
nx.set_edge_attributes(tDG,attrs)
flow_out = nx.maximum_flow(tDG,'s','t')
out_graph = nx.Graph()
out_graph.add_nodes_from(G.nodes())
for e in flow_out[1]:
if e != 's' and e != 't':
for e2 in flow_out[1][e]:
if e2 != 's' and e2 != 't' and flow_out[1][e][e2] > 0:
out_graph.add_edge(e,e2)
pos = {(x,y):(y,-x) for x,y in out_graph.nodes()}
fig, ax = plt.subplots(figsize=(len(tiles[0]),len(tiles)))
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.spines['left'].set_visible(False)
nx.draw_networkx_edges(out_graph,pos,ax=ax,edge_color='0.7',width=2)
# color vertex cyan if sum of vertex coordinates is even
colors = ['c' if sum(x)%2 == 0 else 'm' for x in G.nodes()]
nx.draw_networkx_nodes(out_graph,pos=pos,node_size=50,node_color=colors,ax=ax)
buf = io.BytesIO()
fig.savefig(buf)
buf.seek(0)
plt.close(fig)
maxFlowIm = Image.open(buf)
pos = {(x,y):(y,-x) for x,y in tempG.nodes()}
fig, ax = plt.subplots(figsize=(len(tiles[0]),len(tiles)))
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['bottom'].set_visible(False)
ax.spines['left'].set_visible(False)
nx.draw_networkx_edges(tempG,pos,ax=ax,edge_color='0.7',width=2)
# color vertex cyan if sum of vertex coordinates is even
colors = ['c' if sum(x)%2 == 0 else 'm' for x in G.nodes()]
nx.draw_networkx_nodes(tempG,pos=pos,node_size=50,node_color=colors,ax=ax)
buf = io.BytesIO()
fig.savefig(buf)
buf.seek(0)
plt.close(fig)
backTrackIm = Image.open(buf)
fig = plt.figure(figsize=(10,10))
ax1 = plt.subplot(1,2,1)
plt.imshow(backTrackIm)
ax1.set_title('Backtrack')
plt.axis('off')
ax2 = plt.subplot(1,2,2)
plt.imshow(maxFlowIm)
ax2.set_title('Max Flow')
plt.axis('off')
plt.show()
Converting to images and comparing the backtracking and max flow solutions, we see that the backtracking solution is obviously a valid solution and unfortunately the max flow solution is not.
solMaxFlowTiles = graphToTiles(out_graph,r=len(tiles),c=len(tiles[0]))
toMaxFlowTiles = []
for r,row in enumerate(tiles):
row_ = []
for c,tile in enumerate(row):
if (r,c) in solMaxFlowTiles:
row_.append(solMaxFlowTiles[(r,c)])
else:
row_.append([0]*len(tile))
toMaxFlowTiles.append(row_)
shiftsMaxFlow = shiftsFromTiles(tiles,toMaxFlowTiles)
solutionMaxFlowImages = [[im.crop(box) for box in row] for row in boxes]
for i,row in enumerate(solutionMaxFlowImages):
for j,tile in enumerate(row):
if (i,j) in solutionTiles:
solutionMaxFlowImages[i][j] = tile.rotate((shiftsMaxFlow[i][j])*90)
solved = mergeTiles(solutionImages,tiles)
solvedMaxFlow = mergeTiles(solutionMaxFlowImages,tiles)
plt.figure(figsize=(10,10))
ax1 = plt.subplot(1,2,1)
plt.imshow(solved)
ax1.set_title('Backtrack')
plt.axis('off')
ax2 = plt.subplot(1,2,2)
plt.imshow(solvedMaxFlow)
ax2.set_title('Max Flow')
plt.axis('off')
plt.show()
Why is this happening? Parts of the solution look alright but the rest seems like a garbled mess.
Why? The maximum flow algorithm is a greedy algorithm and it selects paths on the graph that are the best at any one iteration of the algorithm. What we need is a smarter path finding algorithm which takes into account the orientation of the tiles in addition to the capacity of the edges.
I will be contacting Prof. Shelat to see if he has any suggestions for a better path finding algorithm for this problem.
What else can we use?
Due to the nature of the Puzzle it is similar to Sudoku and the 8-Queens puzzle. We can use the same techniques to solve these puzzles. Sudoku and 8-Queens are well known examples of the exact cover problem. So let's us try transforming Infinite Loop into an exact cover problem.
Exact Cover
The Exact Cover Problem can be stated simply as follows:
"Given a set of subsets of a set of elements X, find a subset of the set such that each element in X is in exactly one subset selected."
For example1, Consider a set X = {A,B,C,D} and a set of subsets S = [{A,C}, {B,C}, {B,D}] then [{A,C} , {B,D}] is an exact cover of X. We can also visualize this as a bit matrix where each row represents a subset and each column represents an element in X. Finding an exact cover would be equivalent to finding a set of rows such that each column has only one bit.
AlgorithmX
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the dancing links technique. 1
Here's a really nice lecture by Donald Knuth about Dancing Links.
A nice write up by Ali Assaf from Ecole Polytechnique on a simpler, pythonic version of the algorithm without the dancing links technique can be found here.
Using the python implementation of Algorithm X and converting our tile set to an exact cover bit matrix is left as an exercise for the reader 
Pitfalls and Future Work
We have a decent set of algorithms that solve infinite loop puzzles. However, the image processing heuristics that we settled on are not the best. Some common faliure cases are,
- When tile sizes change in the screenshot of the game, the
bwToTilesfunction does not identify the correct tiles. - A similar problem occurs when the game is not centered to the screen.
Future work would be to extract game tiles from a screenshot with different tile sizes and non centered games.
Thank you for reading 
Feel free to contact me at aliceoxenbury at gmail if you have any questions or comments.