How o3-mini-high Solved a Decades-Old Programming Challenge
Since 2023, I have been experimenting with solving the 227 Puzzle challenge hosted on the online judge platform using OpenAI’s GPT models. After countless trials, chatGPT cracked it when the o3-mini-high model was released in February.
Why was this puzzle so challenging? The 227 Puzzle, a decades-old brain teaser, involves sliding tiles into place — deceptively simple yet complex to solve programmatically.
The online judge platform hosts programming challenges that help users prepare for competitive programming contests. I personally solved some of these challenges back in 2006. The problems come in varying levels of difficulty, but in general, they are not very straightforward to solve.
📊 Curious about the trial history? Check it out:
Problem statement
227 Puzzle
A children’s puzzle that was popular 30 years ago consisted of a 5×5 frame containing 24 small squares of equal size. Each square had a unique letter of the alphabet printed on it. Since there were only 24 squares, the frame also contained an empty position, the same size as a square. A square could be moved into that empty position if it was immediately to the right, left, above, or below it. The objective of the puzzle was to slide squares into the empty position to arrange the letters in alphabetical order.
The illustration below represents a puzzle in its original configuration and after a sequence of 6 moves:
- The square above the empty position moves.
- The square to the right of the empty position moves.
- The square to the right of the empty position moves.
- The square below the empty position moves.
- The square below the empty position moves.
- The square to the left of the empty position moves.
Your task is to write a program that displays the resulting frames given their initial configurations and sequences of moves.
Input
The input consists of multiple puzzles. Each puzzle is described by its initial configuration and a sequence of moves. The first 5 lines of the description represent the starting configuration of the puzzle. The following lines contain the sequence of moves.
Each puzzle frame is structured as follows:
- The first line represents the top row of the puzzle.
- The next four lines follow in sequence.
- The empty position in a frame is represented by a blank space.
- Each line consists of exactly 5 characters.
The sequence of moves is represented using the characters:
- A: Moves the square above the empty position.
- B: Moves the square below the empty position.
- L: Moves the square to the left of the empty position.
- R: Moves the square to the right of the empty position.
If an illegal move is attempted, the puzzle is considered to have no final configuration. The sequence of moves always ends with the digit 0. The end of data is denoted by the character Z.
Output
For each puzzle:
- The output starts with “Puzzle #X:” where X is the puzzle number.
- If the puzzle results in a valid final configuration, it is displayed.
- If an invalid move is encountered, the message “This puzzle has no final configuration.” is displayed.
- Each character in a row is separated by a single space, including the blank position.
- A blank line separates the output of different puzzle records.
Example
Input:
TRGSJ XDOKI M VLN WPABE UQHCF ARRBBL0 ABCDE FGHIJ KLMNO PQRS TUVWX AAA LLLL0 ABCDE FGHIJ KLMNO PQRS TUVWX AAAAABBRRRLL0 Z
Output:
Puzzle #1: T R G S J X O K L I M D V B N W P A E U Q H C F
Puzzle #2: A B C D F G H I E K L M N J P Q R S O T U V W X
Puzzle #3: This puzzle has no final configuration.
Solution
ChatGPT:
Below is one complete Python solution. You can run the script and feed it the input (for example via standard‐input redirection) to see the output. (Comments in the code explain the details.)
#!/usr/bin/env python3
import sys
def main():
# Read all lines from standard input.
# (We only remove the newline, not other whitespace,
# because the spaces in the board are significant.)
lines = sys.stdin.readlines()
puzzle_no = 1 # To number the puzzles in the output.
i = 0 # Index for the current line.
firstPuzzle = True # To control blank line printing between puzzles.
while i < len(lines):
# Read the first line of a new puzzle.
# If this line is "Z", we have reached the end of data.
first_line = lines[i].rstrip('\n')
i += 1
if first_line == "Z":
break
# The puzzle board consists of 5 lines.
# (Each line should be exactly 5 characters; if not, we pad with spaces.)
board = []
# Process the first board line.
if len(first_line) < 5:
first_line += " " * (5 - len(first_line))
board.append(list(first_line))
# Process the next 4 board lines.
for _ in range(4):
if i >= len(lines):
break
row = lines[i].rstrip('\n')
i += 1
if len(row) < 5:
row += " " * (5 - len(row))
board.append(list(row))
# Read the moves.
# Moves may span more than one input line.
# They are terminated by the digit '0'.
moves = ""
while i < len(lines):
move_line = lines[i].rstrip('\n')
i += 1
moves += move_line
if '0' in move_line:
break
# Remove the terminating '0' (and anything following it).
if '0' in moves:
moves = moves[:moves.index('0')]
# Find the position of the blank (' ') in the board.
blank_r = blank_c = None
for r in range(5):
for c in range(5):
if board[r][c] == ' ':
blank_r, blank_c = r, c
break
if blank_r is not None:
break
# Process the moves one by one.
valid = True # Flag to indicate if all moves are legal.
for move in moves:
if move not in "ABLR":
valid = False
break
if move == 'A':
# Move the tile above the blank into the blank.
if blank_r == 0:
valid = False
break
board[blank_r][blank_c], board[blank_r-1][blank_c] = (
board[blank_r-1][blank_c],
board[blank_r][blank_c]
)
blank_r -= 1
elif move == 'B':
# Move the tile below the blank.
if blank_r == 4:
valid = False
break
board[blank_r][blank_c], board[blank_r+1][blank_c] = (
board[blank_r+1][blank_c],
board[blank_r][blank_c]
)
blank_r += 1
elif move == 'L':
# Move the tile to the left of the blank.
if blank_c == 0:
valid = False
break
board[blank_r][blank_c], board[blank_r][blank_c-1] = (
board[blank_r][blank_c-1],
board[blank_r][blank_c]
)
blank_c -= 1
elif move == 'R':
# Move the tile to the right of the blank.
if blank_c == 4:
valid = False
break
board[blank_r][blank_c], board[blank_r][blank_c+1] = (
board[blank_r][blank_c+1],
board[blank_r][blank_c]
)
blank_c += 1
# Print a blank line between puzzles (but not before the first puzzle).
if not firstPuzzle:
print()
firstPuzzle = False
# Print the puzzle header.
print("Puzzle #%d:" % puzzle_no)
puzzle_no += 1
# Print the result.
if not valid:
print("This puzzle has no final configuration.")
else:
# Each row is printed with one space between characters.
for row in board:
print(' '.join(row))
if __name__ == '__main__':
main()
How the script works
-
Input reading and board setup:
The program reads five consecutive lines (padding with spaces if necessary) to form the 5×5 board. (A board line might include a blank position; note that we only remove the newline so that any spaces remain intact.) -
Moves reading:
It then reads one or more lines that together form the moves sequence. The moves are concatenated until a'0'is encountered. The'0'is removed from the move string. -
Simulating moves:
For each move:- A: Move the square above the blank (if possible).
- B: Move the square below the blank.
- L: Move the square to the left.
- R: Move the square to the right.
If a move is illegal (for example, trying to move a tile from outside the board) or an unexpected character is encountered, the puzzle is marked invalid.
-
Output:
The final board (if valid) is printed with one space between every character. If an illegal move was attempted the script prints “This puzzle has no final configuration.” A blank line is printed between successive puzzles.
You can test the script using the sample input given in the problem description.