Solving Puzzles using Ruby
Date : 2023-05-18 Entry ID : 14418 Game : The Last Case of Benedict Fox (@3663)
I've been skipping annoying video game puzzles for 17 years by writing brute force scripts. Usually, writing the script is more fun than trying to solve a frustrating sliding block puzzle.
Onimusha 2: Samurai's Destiny
In Onimusha 2, I found a chest with a unlocking puzzle that was pretty hard. It required 6 moves, each with 4 possibilities (3, if you discard the move that undoes the previous move), and as I couldn't figure it out, and wasn't really up for manually trying the 729 different combinations, I wrote a Ruby script for brute-forcing the problem. The script isn't very elegant, but it didn't take very long to write, and it was satisfying to see it solve the puzzle.
Here is the source:
class Board
def initialize(tiles) @tiles = tiles end
def solved?
# ?a means the ASCII value of 'a' (97)
@tiles[1][1] == ?a and @tiles[1][2] == ?b and
@tiles[2][1] == ?c and @tiles[2][2] == ?d
end
# moves: 12
# 8 3
# 7 4
# 65
def move(n)
if legal_move(n) then
case n
when 1: @tiles[3][1] = @tiles[2][1];@tiles[2][1] = @tiles[1][1]
@tiles[1][1] = @tiles[0][1];@tiles[0][1] = " "
when 2: @tiles[3][2] = @tiles[2][2];@tiles[2][2] = @tiles[1][2]
@tiles[1][2] = @tiles[0][2];@tiles[0][2] = " "
when 3: @tiles[1] = @tiles[1][1..3] + " "
when 4: @tiles[2] = @tiles[2][1..3] + " "
when 5: @tiles[0][2] = @tiles[1][2];@tiles[1][2] = @tiles[2][2]
@tiles[2][2] = @tiles[3][2];@tiles[3][2] = " "
when 6: @tiles[0][1] = @tiles[1][1];@tiles[1][1] = @tiles[2][1]
@tiles[2][1] = @tiles[3][1];@tiles[3][1] = " "
when 7: @tiles[2] = " " + @tiles[2][0..2]
when 8: @tiles[1] = " " + @tiles[1][0..2]
end
else
puts "illegal move"
end
end
# a move is legal if the tile on the opposite side is empty
def legal_move(n)
empty = ?s # ASCII value of space (32)
case n
when 1: return @tiles[3][1] == empty
when 2: return @tiles[3][2] == empty
when 3: return @tiles[1][0] == empty
when 4: return @tiles[2][0] == empty
when 5: return @tiles[0][2] == empty
when 6: return @tiles[0][1] == empty
when 7: return @tiles[2][3] == empty
when 8: return @tiles[1][3] == empty
else return false
end
end
def get_legal_moves
legal_moves = []
(1..8).each do |x| legal_moves += [x] if legal_move(x) end
return legal_moves
end
# non-shallow copy
def copy() return Marshal.load(Marshal.dump(self)) end
def to_s()
" .- 12 -. " +
" | #{@tiles[0]} | " +
" 8 #{@tiles[1]} 3 " +
" 7 #{@tiles[2]} 4 " +
" | #{@tiles[3]} | " +
" '- 65 -'" end
end
class Brain
attr_reader :moves_attempted
def initialize(board) @original_board = board end
def solve(limit)
@moves_attempted = 0
@solved = false
recursive_descent(@original_board, [], limit)
return @solved
end
# recursive brute force, tries 4^limit times before giving up
def recursive_descent(board, moves_so_far, limit)
return if moves_so_far.length >= limit or @solved
board.get_legal_moves.each do |n|
@moves_attempted+=1
new_board = board.copy
new_board.move(n)
if new_board.solved? then
@solved = true
@solution = moves_so_far + [n]
return
else
solution = recursive_descent(
new_board, moves_so_far + [n], limit)
end
end
end
def print_solution
puts "SOLVED in #{@solution.length} moves "+
"(#{@moves_attempted} moves attempted): "
board = @original_board.copy
@solution.each do |m|
board.move(m)
puts "move: #{m}"
puts board
end
print "summary - moves: "
@solution[0..-2].each do |m| print "#{m}, " end
puts @solution[-1]
end
end
board = Board.new( [ " . " ,
"dab " ,
" c.." ,
" . " ] )
puts board
brain = Brain.new(board)
# _extremely_ inefficient way of determining the smallest number of moves
(1..12).each do |moves|
if brain.solve(moves) then
brain.print_solution
exit
else
puts "unsolvable in #{moves} moves "+
"(#{brain.moves_attempted} moves attempted)"
end
end
The solution was 6 moves:
original Onimusha puzzle:
.- 12 -.
| . |
8 dab 3
7 c.. 4
| . |
'- 65 -'
unsolvable in 1 moves (4 moves attempted)
unsolvable in 2 moves (20 moves attempted)
unsolvable in 3 moves (84 moves attempted)
unsolvable in 4 moves (340 moves attempted)
unsolvable in 5 moves (1364 moves attempted)
SOLVED in 6 moves (168 moves attempted):
move: 2
.- 12 -.
| |
8 da. 3
7 cb. 4
| .. |
'- 65 -'
move: 4
.- 12 -.
| |
8 da. 3
7 cb. 4
| .. |
'- 65 -'
move: 6
.- 12 -.
| a |
8 db. 3
7 c.. 4
| . |
'- 65 -'
move: 8
.- 12 -.
| a |
8 db. 3
7 c.. 4
| . |
'- 65 -'
move: 1
.- 12 -.
| |
8 ab. 3
7 cd. 4
| .. |
'- 65 -'
move: 7
.- 12 -.
| |
8 ab. 3
7 cd. 4
| .. |
'- 65 -'
summary - moves: 2, 4, 6, 8, 1, 7
By the way, an example of a more difficult puzzle using the same rules is this:
.- 12 -.
| d |
8 c.. 3
7 ..b 4
| a |
'- 65 -'
which is unsolvable in anything less than 12 moves (2, 4, 6, 7, 8, 1, 5, 3, 2, 4, 5, 7).
Castlevania: Lords of Shadow
In 2012 I was playing Castlevania: Lords of Shadow, and encountered another annoying puzzle. Similarly to how I solved the Onimusha 2 puzzle boxes, I did a quick brute force on the Castlevania rotation puzzle, using the hint that only one-way rotation should be needed:
# Castlevania: Lords of Shadow: Pan's Temple puzzle solver by syltefar 2012-05-24
moves = [ [-1,+1,-1,"middle RT"], [+1,-1,0,"inner RT"], [0,-1,+1,"outer RT"] ]
def apply(move, puzzle)
(0..2).each do |n| puzzle[n] = (puzzle[n] + move[n]) % 4 end
end
random = Random.new
100000.times do
puzzle = [1,1,1] # start position (0 is north, 1 is east, etc.)
move_list = []
(1..5).each do |m| # shortest solution is 5 moves
move = moves[ random.rand(0...moves.length) ]
apply(move, puzzle) ; move_list += [ move ]
if puzzle == [2,2,2] then # solution is all south
puts "solution:" ; move_list.each { |move| puts move[3] }
exit
end
end
end
Solution: outer RT x 2, middle RT, inner RT x 2
The Last Case of Benedict Fox
Another decade, another annoying sliding block puzzle, this time in The Last Case of Benedict Fox. The final campfire rotating disc puzzle was quite annoying, so I employed the usual brute force Ruby scripting:
# Final camp puzzle
# Positions are triples [inner, middle, outer]
# - adjusting left is negative, right is positive
start_pos = [0,0,0]
target_pos = [2,3,4] # relative to start_pos
moves = [
[" in ->", 1, 0,-3], ["mid ->", 0, 1,-4], ["out ->",-1, 1, 1],
[" in <-",-1, 0, 3], ["mid <- ", 0,-1, 4], ["out <-", 1,-1,-1] ]
puts "Moveset:"
moves.each do |m| puts m.inspect end
def do_move(pos, move) # rotate 'pos' as specified by 'move'
[(pos[0]+move[1])%10, (pos[1]+move[2])%10, (pos[2]+move[3])%10]
end
(1..5).each do |move_count|
print "."
(0..10000).each do |t| # retries
pos = start_pos
movelist = []
(0..move_count).each do |m| # try 'move_count' random moves
move = moves[rand(6)]
movelist.push(move)
pos = do_move(pos, move)
if (pos == target_pos) then # solution found!
# Moves correspond to vector *addition*, order of moves doesn't matter
movelist.sort!{|a,b| a[0] <=> b[0]}
puts "solved in #{move_count} moves after #{t} retries. " +
"pos:#{pos} target_pos:#{target_pos}"
puts "start #{start_pos.inspect}"
pos = start_pos
movelist.each do |solution_move|
pos = do_move(pos, solution_move)
puts "#{solution_move[0]} #{pos.inspect}"
end
exit
end
end
end
end
# solved in 5 moves after 1110 retries. pos:[2, 3, 4] target_pos:[2, 3, 4]
# start [0, 0, 0]
# in -> [1, 0, 7]
# in -> [2, 0, 4]
# in -> [3, 0, 1]
# mid -> [3, 1, 7]
# mid -> [3, 2, 3]
# out -> [2, 3, 4]
Artificial Intelligence?
Benedict Fox was the first game where I used AI to help me solve a puzzle. The game had a puzzle that included solving the (very simple) equation:
x-100+10+1=1810
I asked ChatGPT to solve it:
x-100+10+1=1810, solve for x
and it gave me the correct answer, 1899.
Is this the future of solving annoying video game puzzles?
Version History
- 2025-05-08: Joined 3 script entries into article
- 2023-05-18: Benedict Fox puzzle solver
- 2012-06-24: Castlevania puzzle solver
- 2008-06-18: Put Onimusha 2 puzzle solver in wiki