ActiveState Code

Recipe 576692: Sliding Block Puzzle Solver

Recently, I was playing a game called "An Untitled Story" and was frustrated at some of the puzzles it contained. One such puzzle type was a sliding block puzzle game that presented the player with walls, movable blocks, and targets that you had to place the blocks on. The blocks could be moved an infinite amount of times, but once put into motion, they would continue until they hit either a wall or another block. To help solve these puzzle, I wrote the following program to figure out the solutions for me. It can find valid answers far faster than the human mind. The program is somewhat messy but looks much better than its first version.

Python 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
import queue

grids = []

################################################################################

grids.append('''\
OOOOOOOOOOOO
OOO        O
OO         O
OO X       O
O   #  #   O
O          O
O          O
O   #  #   O
OO      X OO
OOX       OO
OO     X OOO
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
OOOOOOOOOOOO
OOOOOOOOOOOO
OOO      OOO
OO   ##   OO
OO  O  #  OO
OO        OO
OO   XX   OO
OOO      OOO
OOOOOOOOOOOO
OOOOOOOOOOOO
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
O          O
O          O
O  #    #  O
O          O
O          O
O          O
O          O
O X     #  O
O          O
O          O
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
O    O    OO
O       # OO
O         OO
O         OO
OOX      OOO
O         OO
O        #OO
O         OO
O    O   OOO
OOOOOOOOOOOO
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
O O      O O
O  #       O
O        # O
O       X  O
O          O
O          O
O  #       O
O       #  O
O          O
O          O
OOOOOOOOOOOO''')

grids.append('''\
OOOOOOOOOOOO
O          O
O   O   #  O
O         OO
O          O
O          O
O        X O
O          O
O        # O
O #        O
O          O
OOOOOOOOOOOO''')

################################################################################

def reader(grid):
    walls = set()
    blocks = set()
    targets = set()
    for y, line in enumerate(grid.split('\n')):
        for x, char in enumerate(line):
            if char == 'O':
                walls.add((y, x))
            elif char == '#':
                blocks.add((y, x))
            elif char == 'X':
                targets.add((y, x))
    return walls, blocks, targets

def worker(walls, blocks, targets):
    states = {frozenset(blocks)}
    jobs = queue.Queue()
    jobs.put((blocks, None))
    while not jobs.empty():
        job = jobs.get()
        # Pick a block to move.
        for block in job[0]:
            # Move up.
            offset = 1
            temp = (block[0] - offset, block[1])
            while temp not in walls and temp not in job[0]:
                offset += 1
                temp = (block[0] - offset, block[1])
            offset -= 1
            # Check for movement.
            if offset:
                copy = set(job[0])
                copy.remove(block)
                copy.add((block[0] - offset, block[1]))
                if copy not in states:
                    if targets.issubset(copy):
                        return (copy, job)
                    states.add(frozenset(copy))
                    jobs.put((copy, job))
            # Move down.
            offset = 1
            temp = (block[0] + offset, block[1])
            while temp not in walls and temp not in job[0]:
                offset += 1
                temp = (block[0] + offset, block[1])
            offset -= 1
            # Check for movement.
            if offset:
                copy = set(job[0])
                copy.remove(block)
                copy.add((block[0] + offset, block[1]))
                if copy not in states:
                    if targets.issubset(copy):
                        return (copy, job)
                    states.add(frozenset(copy))
                    jobs.put((copy, job))
            # Move left.
            offset = 1
            temp = (block[0], block[1] - offset)
            while temp not in walls and temp not in job[0]:
                offset += 1
                temp = (block[0], block[1] - offset)
            offset -= 1
            # Check for movement.
            if offset:
                copy = set(job[0])
                copy.remove(block)
                copy.add((block[0], block[1] - offset))
                if copy not in states:
                    if targets.issubset(copy):
                        return (copy, job)
                    states.add(frozenset(copy))
                    jobs.put((copy, job))
            # Move right.
            offset = 1
            temp = (block[0], block[1] + offset)
            while temp not in walls and temp not in job[0]:
                offset += 1
                temp = (block[0], block[1] + offset)
            offset -= 1
            # Check for movement.
            if offset:
                copy = set(job[0])
                copy.remove(block)
                copy.add((block[0], block[1] + offset))
                if copy not in states:
                    if targets.issubset(copy):
                        return (copy, job)
                    states.add(frozenset(copy))
                    jobs.put((copy, job))
    print(len(states), 'Unique States')
    print('No Solution Found!')
    return (blocks, None)

def opener(walls, answer, targets):
    if answer[1] is not None:
        opener(walls, answer[1], targets)
    print(render(walls, answer[0], targets))

def render(walls, blocks, targets):
    box = {}
    for y, x in walls:
        if y not in box:
            box[y] = {}
        box[y][x] = 'O'
    for y, x in targets:
        box[y][x] = 'X'
    for y, x in blocks:
        box[y][x] = '#'
    max_y = max(box)
    max_x = 0
    for y in box:
        max_x = max(max_x, max(box[y]))
    lines = []
    for y in range(max_y + 1):
        line = ''
        for x in range(max_x + 1):
            line += box[y].get(x, ' ')
        lines.append(line)
    return '\n'.join(lines)

################################################################################

if __name__ == '__main__':
    walls, blocks, targets = reader(grids[-1])
    answer = worker(walls, blocks, targets)
    opener(walls, answer, targets); input()

Comments

  1. 1. At 11:49 a.m. on 17 mar 2009, Stephen Chappell (the author) said:

    Am I the only one that has noticed that almost all recipes here get a -1 vote shortly after they are posted? It is rather annoying as you almost have to add 1 to the score to have a better idea of what other users actually think of the recipe.

  2. 2. At 3:34 a.m. on 20 mar 2009, david.gaarenstroom said:

    I noticed this as well. There seem to be two users that always give people a -1 vote, although sometimes either of them forgets to. I guess they just like to bug every Python developer here...

    IMHO, every negative vote should be accompanied by an explanation.

    But here's a +1 from me!

  3. 3. At 3:48 a.m. on 23 mar 2009, Anand Balachandran Pillai said:

    Yes. This bugged me too. My two last recipes were automatically ranked at -1 immediately after posting without any comments. I wonder if someone has written a bot for this based on the feeds.

Sign in to comment