<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P054-sliding-puzzle/ | updated: 2026-10-10 -->

# 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.

EML-P project `projects/sliding-puzzle` in the EML language repo: 4 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/sliding-puzzle` runs it and `eml project verify projects/sliding-puzzle` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: graph-bfs-traversal (https://efficientnewlanguage.org/cases/085-graph-bfs-traversal/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
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
```

Screen:

```text
== 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.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
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
```

Screen:

```text
== 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.
```

## Modules

### main.eml

```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 of main.eml:

```python
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 of board.eml:

```python
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 of solver.eml:

```python
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 of rng.eml:

```python
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
```

## README

# P054 - Sliding puzzle

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 hints
- `board.eml` - boards: the tiles beside the gap, sliding one, counting the
  pairs out of order, whether a board can be solved, and the drawing
- `solver.eml` - the fewest moves for a 3 x 3 board
- `rng.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).