Project P054
Sliding puzzle
The 3 x 3 and 4 x 4 sliding puzzles: shuffled boards that are always solvable, typed boards checked by counting the pairs out of order, several tiles slid in one line, and for 3 x 3 the fewest moves found by breadth-first search from both ends.
4 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-10
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Numbered tiles in a 3 x 3 or 4 x 4 frame with one gap. Slide a tile beside the gap into it, again and again, until the tiles read 1, 2, 3 ... in order with the gap last. Shuffled boards are always solvable. A board you type in is checked first, and a 3 x 3 board can be solved in the fewest moves.
main.eml- the menu, shuffling, sliding several tiles in one line, typing in a board, and the hintsboard.eml- boards: the tiles beside the gap, sliding one, counting the pairs out of order, whether a board can be solved, and the drawingsolver.eml- the fewest moves for a 3 x 3 boardrng.eml- random numbers written in EML, the generator of P008
How each part works:
- Only half of all orders of the tiles can be reached. Count the pairs of tiles that are out of order, reading row by row and skipping the gap. A slide along a row changes no pair. A slide along a column moves one tile past the n - 1 tiles between, so it changes n - 1 pairs. - On a 3 x 3 board that is 2 pairs, so the count stays odd or even, and the solved board has 0: only an even count can be solved. - On a 4 x 4 board it is 3 pairs, so the count flips between odd and even, while the gap moves one row. The count plus the gap's row (from the bottom) keeps its parity, which is odd on the solved board.
- A shuffle puts the tiles in a random order with Fisher-Yates. When the order cannot be solved, the first two tiles trade places. That changes the count by one and pairs every unsolvable order with one solvable order, so every solvable board is still equally likely.
- The fewest moves come from breadth-first search, as in the corpus case
graph-bfs-traversal: every board one slide away is a neighbour, and boards are found one distance at a time. It searches from both ends at once - from the board and from the solved board - one level at a time, always on the smaller side, and stops in the first level where the two meet. A 3 x 3 board is at most 31 moves from solved, so each side looks only about half as deep, at a few thousand boards instead of up to 181,440. - A 4 x 4 board has over ten trillion positions, so it gets no search - only the solvability check and the play.
What is checked: menu choices 1 to 7; tiles beside the gap (several in a line slide one after another, stopping at the first that is not); a typed board of 9 or 16 numbers using each of 0 to 8, or 0 to 15, once; size 3 or 4 and a seed from 0 to 999999999 for a new puzzle. An empty answer cancels.
Sessions: sessions/basic.in starts from the default board (seed 2026). A hint says it can be solved in 16 moves. After 4 1 2, slid in one line, 13 are left, and the solution's 13 tiles, typed in one line, solve it in 16 moves - the fewest. Then a 4 x 4 board (seed 5) gets two slides and asks for a hint, which only a 3 x 3 board has.
sessions/bad-input.in gives: - menu choices 0 and x; - an empty slide, 99, a, "4 99" (the 4 slides, then it stops at 99) and "x y"; - typed boards: three numbers; a board with 8 twice; 3 x 3 with 8 and 7 swapped (1 pair out of order, so it cannot be solved); and 4 x 4 with 15 and 14 swapped (1 pair, plus the gap in row 1, adds up to an even 2); - a typed board one slide from solved, solved with 8, then a slide and a hint on the solved board; - a new puzzle that first gets sizes 5 and 2, then is cancelled at each question.
Built on the verified corpus case graph-bfs-traversal (breadth-first traversal with a queue and a dict of the nodes already visited).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Sliding puzzle ==
Slide tiles into the gap until they read in order with the gap last.
A shuffled 3 x 3 board, seed 2026.
+------------+
| 1 2 6 |
| 4 8 3 |
| 7 5 |
+------------+
Moves 0. Slide one of: 4 7.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 0
Pick a number from 1 to 7.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> x
Pick a number from 1 to 7.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order>
Cancelled.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order> 99
99 is not beside the gap.
+------------+
| 1 2 6 |
| 4 8 3 |
| 7 5 |
+------------+
Moves 0. Slide one of: 4 7.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order> a
a is not beside the gap.
+------------+
| 1 2 6 |
| 4 8 3 |
| 7 5 |
+------------+
Moves 0. Slide one of: 4 7.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order> 4 99
Slid 1, then stopped: 99 is not beside the gap.
+------------+
| 1 2 6 |
| 8 3 |
| 4 7 5 |
+------------+
Moves 1. Slide one of: 1 8 4.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order> x y
x is not beside the gap.
+------------+
| 1 2 6 |
| 8 3 |
| 4 7 5 |
+------------+
Moves 1. Slide one of: 1 8 4.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 5
the board, row by row, 0 for the gap> 1 2 3
Type 9 numbers for 3 x 3 or 16 for 4 x 4.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 5
the board, row by row, 0 for the gap> 1 2 3 4 5 6 7 8 8
Use each number from 0 to 8 once.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 5
the board, row by row, 0 for the gap> 1 2 3 4 5 6 8 7 0
That board cannot be solved: it has 1 pair of tiles out of order, an odd number, and every slide keeps that number odd or even.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 5
the board, row by row, 0 for the gap> 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0
That board cannot be solved: its 1 pair out of order and the gap's row from the bottom, 1, add up to an even number, and every slide keeps that sum odd or even.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 5
the board, row by row, 0 for the gap> 1 2 3 4 5 6 7 0 8
That board can be solved.
+------------+
| 1 2 3 |
| 4 5 6 |
| 7 8 |
+------------+
Moves 0. Slide one of: 5 7 8.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order> 8
+------------+
| 1 2 3 |
| 4 5 6 |
| 7 8 |
+------------+
Solved in 1 move.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
The board is solved - start a new one or type one in.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 2
The board is solved.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 4
size (3 to 4)> 5
Type a number from 3 to 4.
size (3 to 4)> 2
Type a number from 3 to 4.
size (3 to 4)>
Cancelled.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 4
size (3 to 4)> 3
seed (0 to 999999999)>
Cancelled.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 7
Bye.
What was typed (34 lines)
0
x
1
1
99
1
a
1
4 99
1
x y
5
1 2 3
5
1 2 3 4 5 6 7 8 8
5
1 2 3 4 5 6 8 7 0
5
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0
5
1 2 3 4 5 6 7 0 8
1
8
1
2
4
5
2
4
3
7
basic
interpreter: byte-equal== Sliding puzzle ==
Slide tiles into the gap until they read in order with the gap last.
A shuffled 3 x 3 board, seed 2026.
+------------+
| 1 2 6 |
| 4 8 3 |
| 7 5 |
+------------+
Moves 0. Slide one of: 4 7.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 2
Slide 4: from here the board can be solved in 16 moves.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order> 4 1 2
+------------+
| 2 6 |
| 1 8 3 |
| 4 7 5 |
+------------+
Moves 3. Slide one of: 2 6 8.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 2
Slide 6: from here the board can be solved in 13 moves.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 3
The fewest moves from here: 13 - slide 6 3 8 6 2 1 4 7 5 8 6 5 8.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order> 6 3 8 6 2 1 4 7 5 8 6 5 8
+------------+
| 1 2 3 |
| 4 5 6 |
| 7 8 |
+------------+
Solved in 16 moves.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 4
size (3 to 4)> 4
seed (0 to 999999999)> 5
A shuffled 4 x 4 board, seed 5.
+----------------+
| 12 1 9 15 |
| 8 4 3 10 |
| 7 11 14 6 |
| 2 5 13 |
+----------------+
Moves 0. Slide one of: 6 13.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 1
tiles to slide, in order> 13 5
+----------------+
| 12 1 9 15 |
| 8 4 3 10 |
| 7 11 14 6 |
| 2 5 13 |
+----------------+
Moves 2. Slide one of: 11 2 5.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 2
Only a 3 x 3 board can be searched - a 4 x 4 one has over ten trillion positions.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 6
+----------------+
| 12 1 9 15 |
| 8 4 3 10 |
| 7 11 14 6 |
| 2 5 13 |
+----------------+
Moves 2. Slide one of: 11 2 5.
1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit
choice> 7
Bye.
What was typed (15 lines)
2
1
4 1 2
2
3
1
6 3 8 6 2 1 4 7 5 8 6 5 8
4
4
5
1
13 5
2
6
7
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P054 sliding puzzle: slide the tiles into the gap until they read in
# order, on a 3 x 3 or 4 x 4 board. Shuffled boards are always solvable;
# a board you type is checked first, and a 3 x 3 board can be solved in the
# fewest moves by breadth-first search.
import board
import solver
import rng
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def words(s):
[] => out
"" => word
for c in s + " ":
if c == " " or c == ",":
if word != "":
out + [word] => out
"" => word
else:
word + c => word
return out
def number(s):
if s == "" or len(s) > 9:
return -1
0 => n
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n * 10 + int(c) => n
return n
def counted(n, one, many):
if n == 1:
return "1 " + one
return str(n) + " " + many
def joined(xs):
"" => s
for x in xs:
if s != "":
s + " " => s
s + str(x) => s
return s
def show(p):
for line in board.drawn(p[0], p[1]):
line ^0
if p[0] == board.solved(p[1]):
("Solved in " + counted(p[2], "move", "moves") + ".") ^0
else:
("Moves " + str(p[2]) + ". Slide one of: " + joined(board.slides(p[0], p[1])) + ".") ^0
def shuffled(n, g):
# A random order of the tiles and the gap (Fisher-Yates on EML's own
# random numbers). Half of all orders cannot be solved; for those, two
# tiles trade places - that changes the inversions by one and makes the
# board solvable, the same as lifting two tiles out and putting them back
# the other way round.
board.solved(n) => b
for k in [0:n * n - 2]:
n * n - 1 - k => i
g.below(i + 1) => j
b[i] => t
b[j] => b[i]
t => b[j]
if not board.solvable(b, n):
-1 => a
-1 => c
for i in [0:n * n - 1]:
if b[i] != 0:
if a == -1:
i => a
elif c == -1:
i => c
b[a] => t
b[c] => b[a]
t => b[c]
return b
def ask_number(prompt, low, high):
while True:
trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => answer
if answer == "":
return -1
number(answer) => n
if n >= low and n <= high:
return n
("Type a number from " + str(low) + " to " + str(high) + ".") ^0
def new_puzzle(p):
ask_number("size", 3, 4) => n
if n == -1:
"Cancelled." ^0
return p
ask_number("seed", 0, 999999999) => seed
if seed == -1:
"Cancelled." ^0
return p
[shuffled(n, rng.Rng(seed)), n, 0] => p
("A shuffled " + str(n) + " x " + str(n) + " board, seed " + str(seed) + ".") ^0
show(p)
return p
def slide(p):
if p[0] == board.solved(p[1]):
"The board is solved - start a new one or type one in." ^0
return
words(trim(input("tiles to slide, in order> "))) => ws
if len(ws) == 0:
"Cancelled." ^0
return
0 => done
for w in ws:
number(w) => tile
False => ok
for t in board.slides(p[0], p[1]):
if t == tile:
True => ok
if not ok:
if done > 0:
("Slid " + str(done) + ", then stopped: " + w + " is not beside the gap.") ^0
else:
(w + " is not beside the gap.") ^0
show(p)
return
board.slid(p[0], tile) => p[0]
p[2] + 1 => p[2]
done + 1 => done
if p[0] == board.solved(p[1]):
show(p)
return
show(p)
def hint(p, all_moves):
if p[1] != 3:
"Only a 3 x 3 board can be searched - a 4 x 4 one has over ten trillion positions." ^0
return
if p[0] == board.solved(3):
"The board is solved." ^0
return
solver.solution(p[0]) => way
if all_moves:
("The fewest moves from here: " + str(len(way)) + " - slide " + joined(way) + ".") ^0
else:
("Slide " + str(way[0]) + ": from here the board can be solved in " + counted(len(way), "move", "moves") + ".") ^0
def typed(p):
trim(input("the board, row by row, 0 for the gap> ")) => answer
if answer == "":
"Cancelled." ^0
return p
words(answer) => ws
if len(ws) != 9 and len(ws) != 16:
"Type 9 numbers for 3 x 3 or 16 for 4 x 4." ^0
return p
3 => n
if len(ws) == 16:
4 => n
[] => b
[False] * (n * n) => seen
for w in ws:
number(w) => x
if x < 0 or x >= n * n or seen[x]:
("Use each number from 0 to " + str(n * n - 1) + " once.") ^0
return p
True => seen[x]
b + [x] => b
board.inversions(b) => inv
if not board.solvable(b, n):
if n == 3:
("That board cannot be solved: it has " + counted(inv, "pair", "pairs") + " of tiles out of order, an odd number, and every slide keeps that number odd or even.") ^0
else:
("That board cannot be solved: its " + counted(inv, "pair", "pairs") + " out of order and the gap's row from the bottom, " + str(n - int(board.gap(b) / n)) + ", add up to an even number, and every slide keeps that sum odd or even.") ^0
return p
[b, n, 0] => p
"That board can be solved." ^0
show(p)
return p
"== Sliding puzzle ==" ^0
"Slide tiles into the gap until they read in order with the gap last." ^0
[shuffled(3, rng.Rng(2026)), 3, 0] => p
"A shuffled 3 x 3 board, seed 2026." ^0
show(p)
True => running
while running:
"" ^0
"1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
slide(p)
elif choice == "2":
hint(p, False)
elif choice == "3":
hint(p, True)
elif choice == "4":
new_puzzle(p) => p
elif choice == "5":
typed(p) => p
elif choice == "6":
show(p)
elif choice == "7":
False => running
else:
"Pick a number from 1 to 7." ^0
"Bye." ^0
Python projection (main.py)
import board
import solver
import rng
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def words(s):
out = []
word = ""
for c in s + " ":
if c == " " or c == ",":
if word != "":
out = out + [word]
word = ""
else:
word = word + c
return out
def number(s):
if s == "" or len(s) > 9:
return -1
n = 0
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n = n * 10 + int(c)
return n
def counted(n, one, many):
if n == 1:
return "1 " + one
return str(n) + " " + many
def joined(xs):
s = ""
for x in xs:
if s != "":
s = s + " "
s = s + str(x)
return s
def show(p):
for line in board.drawn(p[0], p[1]):
print(line)
if p[0] == board.solved(p[1]):
print("Solved in " + counted(p[2], "move", "moves") + ".")
else:
print("Moves " + str(p[2]) + ". Slide one of: " + joined(board.slides(p[0], p[1])) + ".")
def shuffled(n, g):
b = board.solved(n)
for k in range(0, n * n - 2+1):
i = n * n - 1 - k
j = g.below(i + 1)
t = b[i]
b[i] = b[j]
b[j] = t
if not board.solvable(b, n):
a = -1
c = -1
for i in range(0, n * n):
if b[i] != 0:
if a == -1:
a = i
elif c == -1:
c = i
t = b[a]
b[a] = b[c]
b[c] = t
return b
def ask_number(prompt, low, high):
while True:
answer = trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
if answer == "":
return -1
n = number(answer)
if n >= low and n <= high:
return n
print("Type a number from " + str(low) + " to " + str(high) + ".")
def new_puzzle(p):
n = ask_number("size", 3, 4)
if n == -1:
print("Cancelled.")
return p
seed = ask_number("seed", 0, 999999999)
if seed == -1:
print("Cancelled.")
return p
p = [shuffled(n, rng.Rng(seed)), n, 0]
print("A shuffled " + str(n) + " x " + str(n) + " board, seed " + str(seed) + ".")
show(p)
return p
def slide(p):
if p[0] == board.solved(p[1]):
print("The board is solved - start a new one or type one in.")
return
ws = words(trim(input("tiles to slide, in order> ")))
if len(ws) == 0:
print("Cancelled.")
return
done = 0
for w in ws:
tile = number(w)
ok = False
for t in board.slides(p[0], p[1]):
if t == tile:
ok = True
if not ok:
if done > 0:
print("Slid " + str(done) + ", then stopped: " + w + " is not beside the gap.")
else:
print(w + " is not beside the gap.")
show(p)
return
p[0] = board.slid(p[0], tile)
p[2] = p[2] + 1
done = done + 1
if p[0] == board.solved(p[1]):
show(p)
return
show(p)
def hint(p, all_moves):
if p[1] != 3:
print("Only a 3 x 3 board can be searched - a 4 x 4 one has over ten trillion positions.")
return
if p[0] == board.solved(3):
print("The board is solved.")
return
way = solver.solution(p[0])
if all_moves:
print("The fewest moves from here: " + str(len(way)) + " - slide " + joined(way) + ".")
else:
print("Slide " + str(way[0]) + ": from here the board can be solved in " + counted(len(way), "move", "moves") + ".")
def typed(p):
answer = trim(input("the board, row by row, 0 for the gap> "))
if answer == "":
print("Cancelled.")
return p
ws = words(answer)
if len(ws) != 9 and len(ws) != 16:
print("Type 9 numbers for 3 x 3 or 16 for 4 x 4.")
return p
n = 3
if len(ws) == 16:
n = 4
b = []
seen = [False] * (n * n)
for w in ws:
x = number(w)
if x < 0 or x >= n * n or seen[x]:
print("Use each number from 0 to " + str(n * n - 1) + " once.")
return p
seen[x] = True
b = b + [x]
inv = board.inversions(b)
if not board.solvable(b, n):
if n == 3:
print("That board cannot be solved: it has " + counted(inv, "pair", "pairs") + " of tiles out of order, an odd number, and every slide keeps that number odd or even.")
else:
print("That board cannot be solved: its " + counted(inv, "pair", "pairs") + " out of order and the gap's row from the bottom, " + str(n - int(board.gap(b) / n)) + ", add up to an even number, and every slide keeps that sum odd or even.")
return p
p = [b, n, 0]
print("That board can be solved.")
show(p)
return p
print("== Sliding puzzle ==")
print("Slide tiles into the gap until they read in order with the gap last.")
p = [shuffled(3, rng.Rng(2026)), 3, 0]
print("A shuffled 3 x 3 board, seed 2026.")
show(p)
running = True
while running:
print("")
print("1) slide 2) hint 3) solve 4) new puzzle 5) type a board 6) show 7) quit")
choice = trim(input("choice> "))
if choice == "1":
slide(p)
elif choice == "2":
hint(p, False)
elif choice == "3":
hint(p, True)
elif choice == "4":
p = new_puzzle(p)
elif choice == "5":
p = typed(p)
elif choice == "6":
show(p)
elif choice == "7":
running = False
else:
print("Pick a number from 1 to 7.")
print("Bye.")
board.eml
eml# P054 sliding puzzle - boards. A board of size n is a list of n * n
# numbers, row by row, 0 for the gap; it is solved when it reads 1, 2, ...,
# n * n - 1 with the gap last.
def solved(n):
[] => b
for k in [1:n * n - 1]:
b + [k] => b
return b + [0]
def gap(b):
for i in [0:len(b) - 1]:
if b[i] == 0:
return i
return -1
def slides(b, n):
# The tiles that can slide into the gap: the ones beside it, above it or
# below it - in the order up, left, right, down from the gap.
gap(b) => g
int(g / n) => r
g - r * n => c
[] => out
if r > 0:
out + [b[g - n]] => out
if c > 0:
out + [b[g - 1]] => out
if c < n - 1:
out + [b[g + 1]] => out
if r < n - 1:
out + [b[g + n]] => out
return out
def slid(b, tile):
# A new board with tile moved into the gap (tile must be beside it).
b[0:len(b)] => nb
gap(b) => g
for i in [0:len(b) - 1]:
if b[i] == tile:
0 => nb[i]
tile => nb[g]
return nb
def inversions(b):
# Pairs of tiles in the wrong order, reading row by row and skipping
# the gap.
0 => count
for i in [0:len(b) - 1]:
if b[i] != 0:
for j in [i + 1:len(b) - 1]:
if b[j] != 0 and b[j] < b[i]:
count + 1 => count
return count
def solvable(b, n):
# A slide along a row changes no pair's order. A slide along a column
# jumps one tile over n - 1 others, changing the order of n - 1 pairs:
# for odd n that keeps the parity of the inversions, so only boards with
# an even count can reach the solved board (0 inversions). For even n
# every vertical slide flips the parity and moves the gap one row, so
# inversions + the gap's row counted from the bottom (1 for the bottom
# row) keeps its parity, which is odd on the solved board.
inversions(b) => inv
if n % 2 == 1:
return inv % 2 == 0
int(gap(b) / n) => r
return (inv + n - r) % 2 == 1
def key(b):
# A board as text, one character a tile (3 x 3 only: tiles 0 to 8).
"" => s
for x in b:
s + str(x) => s
return s
def board_of(s):
[] => b
for ch in s:
b + [int(ch)] => b
return b
def drawn(b, n):
[] => lines
"+" + "----" * n + "+" => rule
lines + [rule] => lines
for r in [0:n - 1]:
"|" => line
for c in [0:n - 1]:
b[r * n + c] => x
" " => cell
if x != 0:
str(x) => cell
if len(cell) == 1:
" " + cell => cell
line + " " + cell + " " => line
lines + [line + "|"] => lines
lines + [rule] => lines
return lines
Python projection (board.py)
def solved(n):
b = []
for k in range(1, n * n):
b = b + [k]
return b + [0]
def gap(b):
for i in range(0, len(b)):
if b[i] == 0:
return i
return -1
def slides(b, n):
g = gap(b)
r = int(g / n)
c = g - r * n
out = []
if r > 0:
out = out + [b[g - n]]
if c > 0:
out = out + [b[g - 1]]
if c < n - 1:
out = out + [b[g + 1]]
if r < n - 1:
out = out + [b[g + n]]
return out
def slid(b, tile):
nb = b[0:len(b)]
g = gap(b)
for i in range(0, len(b)):
if b[i] == tile:
nb[i] = 0
nb[g] = tile
return nb
def inversions(b):
count = 0
for i in range(0, len(b)):
if b[i] != 0:
for j in range(i + 1, len(b)):
if b[j] != 0 and b[j] < b[i]:
count = count + 1
return count
def solvable(b, n):
inv = inversions(b)
if n % 2 == 1:
return inv % 2 == 0
r = int(gap(b) / n)
return (inv + n - r) % 2 == 1
def key(b):
s = ""
for x in b:
s = s + str(x)
return s
def board_of(s):
b = []
for ch in s:
b = b + [int(ch)]
return b
def drawn(b, n):
lines = []
rule = "+" + "----" * n + "+"
lines = lines + [rule]
for r in range(0, n):
line = "|"
for c in range(0, n):
x = b[r * n + c]
cell = " "
if x != 0:
cell = str(x)
if len(cell) == 1:
cell = " " + cell
line = line + " " + cell + " "
lines = lines + [line + "|"]
lines = lines + [rule]
return lines
solver.eml
eml# P054 sliding puzzle - the fewest moves for a 3 x 3 board, by breadth-first
# search as in the corpus case graph-bfs-traversal: every board one slide
# away is a neighbour, and the search finds every board at distance 1, then
# 2, and so on, so the first time it reaches the goal it has a shortest way.
#
# It searches from both ends at once - from the puzzle and from the solved
# board - a whole level at a time, always widening the smaller side, and
# stops when the two meet. A 3 x 3 board is at most 31 moves from solved,
# so each side only goes about half as deep, and sees a few thousand boards
# instead of up to 181,440.
import board
def moves(s):
# [tile, the board after sliding it] for every tile beside the gap, a
# board as its text key.
0 => g
while s[g] != "0":
g + 1 => g
int(g / 3) => r
g - r * 3 => c
[] => targets
if r > 0:
targets + [g - 3] => targets
if c > 0:
targets + [g - 1] => targets
if c < 2:
targets + [g + 1] => targets
if r < 2:
targets + [g + 3] => targets
[] => out
for t in targets:
"" => ns
for i in [0:8]:
if i == g:
ns + s[t] => ns
elif i == t:
ns + "0" => ns
else:
ns + s[i] => ns
out + [[int(s[t]), ns]] => out
return out
def widened(frontier, mine, other):
# One level outward from frontier. mine maps each board this side has
# seen to [the board it came from, the tile slid, its distance]. Returns
# [the next level, the boards in it the other side has seen too].
[] => next_level
[] => met
for s in frontier:
mine[s][2] + 1 => d
for m in moves(s):
m[1] => t
if not (t in mine):
[s, m[0], d] => mine[t]
next_level + [t] => next_level
if t in other:
met + [t] => met
return [next_level, met]
def solution(b):
# The tiles to slide, in order, for the fewest moves - [] when b is
# solved. b must be solvable.
board.key(b) => start
"123456780" => goal
if start == goal:
return []
{} => fwd
["", 0, 0] => fwd[start]
{} => bwd
["", 0, 0] => bwd[goal]
[start] => fa
[goal] => fb
[] => met
while len(met) == 0:
if len(fa) <= len(fb):
widened(fa, fwd, bwd) => res
res[0] => fa
else:
widened(fb, bwd, fwd) => res
res[0] => fb
res[1] => met
# Every board met in this level is the same distance from the side just
# widened; the shortest way goes through the one nearest the other end.
met[0] => best
for t in met:
if fwd[t][2] + bwd[t][2] < fwd[best][2] + bwd[best][2]:
t => best
[] => first_half
best => s
while s != start:
[fwd[s][1]] + first_half => first_half
fwd[s][0] => s
[] => second_half
best => s
while s != goal:
second_half + [bwd[s][1]] => second_half
bwd[s][0] => s
return first_half + second_half
Python projection (solver.py)
import board
def moves(s):
g = 0
while s[g] != "0":
g = g + 1
r = int(g / 3)
c = g - r * 3
targets = []
if r > 0:
targets = targets + [g - 3]
if c > 0:
targets = targets + [g - 1]
if c < 2:
targets = targets + [g + 1]
if r < 2:
targets = targets + [g + 3]
out = []
for t in targets:
ns = ""
for i in range(0, 9):
if i == g:
ns = ns + s[t]
elif i == t:
ns = ns + "0"
else:
ns = ns + s[i]
out = out + [[int(s[t]), ns]]
return out
def widened(frontier, mine, other):
next_level = []
met = []
for s in frontier:
d = mine[s][2] + 1
for m in moves(s):
t = m[1]
if not t in mine:
mine[t] = [s, m[0], d]
next_level = next_level + [t]
if t in other:
met = met + [t]
return [next_level, met]
def solution(b):
start = board.key(b)
goal = "123456780"
if start == goal:
return []
fwd = {}
fwd[start] = ["", 0, 0]
bwd = {}
bwd[goal] = ["", 0, 0]
fa = [start]
fb = [goal]
met = []
while len(met) == 0:
if len(fa) <= len(fb):
res = widened(fa, fwd, bwd)
fa = res[0]
else:
res = widened(fb, bwd, fwd)
fb = res[0]
met = res[1]
best = met[0]
for t in met:
if fwd[t][2] + bwd[t][2] < fwd[best][2] + bwd[best][2]:
best = t
first_half = []
s = best
while s != start:
first_half = [fwd[s][1]] + first_half
s = fwd[s][0]
second_half = []
s = best
while s != goal:
second_half = second_half + [bwd[s][1]]
s = bwd[s][0]
return first_half + second_half
rng.eml
eml# P054 sliding puzzle - random numbers written in EML: the linear congruential
# generator of P008 (number guessing), with the constants of the C
# standard's example rand(). Python's random module is not used, so a seed
# gives the same board on every machine, and the interpreter can check a
# whole session byte for byte.
class Rng:
def __init__(self, seed):
seed % 2147483648 => self.state
def step(self):
(1103515245 * self.state + 12345) % 2147483648 => self.state
return self.state
def below(self, n):
# A number from 0 to n - 1, taken from the high bits of the state: the
# low bits of this generator repeat with short periods. Dividing by
# 65536 is exact in a float for a state below 2^31.
return int(self.step() / 65536) % n
Python projection (rng.py)
class Rng:
def __init__(self, seed):
self.state = seed % 2147483648
def step(self):
self.state = (1103515245 * self.state + 12345) % 2147483648
return self.state
def below(self, n):
return int(self.step() / 65536) % n