How to resolve the algorithm Solve a Hidato puzzle step by step in the Ruby programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Solve a Hidato puzzle step by step in the Ruby programming language
Table of Contents
Problem Statement
The task is to write a program which solves Hidato (aka Hidoku) puzzles. The rules are: For example the following problem has the following solution, with path marked on it:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Solve a Hidato puzzle step by step in the Ruby programming language
This Ruby code solves Hidato puzzles, which are number puzzles where the goal is to fill in all the empty cells with numbers from 1 to $n$, where $n$ is the number of cells. The numbers must follow certain rules:
- Each row must contain the numbers from 1 to $n$ in order, without repetition.
- Each column must contain the numbers from 1 to $n$ in order, without repetition.
- Each $3 × 3$ subgrid must contain the numbers from 1 to $n$ in order, without repetition.
The code uses a backtracking algorithm to solve the puzzle. It starts by placing the number 1 in the first cell and then tries to place the number 2 in the next cell. If the number 2 cannot be placed in that cell, the algorithm backtracks to the previous cell and tries a different number. The code uses a recursive function called try to place the numbers in the cells. The try function takes two arguments: the cell to be filled in and the number to be placed in that cell. The function returns true if the number can be placed in the cell and false otherwise.
The code also uses a data structure called a "Cell" to store information about each cell in the puzzle. The Cell structure has three fields:
value: The value of the cell.used: A boolean value that indicates whether the cell has been used.adj: A list of the cells that are adjacent to the cell.
The code uses the to_s method to print the puzzle to the console. The to_s method takes an optional argument, which is the message to be printed before the puzzle. If no argument is given, the default message is "Problem:".
The following is an example of how to use the code to solve a Hidato puzzle:
board = <<EOS
. 4
0 7 0
1 0 0
EOS
Hidato.new(board).solve
This code will solve the following Hidato puzzle:
. 4
0 7 0
1 0 0
The solution to the puzzle is:
1 4
2 7 3
1 5 6
Source code in the ruby programming language
# Solve a Hidato Puzzle
#
class Hidato
Cell = Struct.new(:value, :used, :adj)
ADJUST = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
def initialize(board, pout=true)
@board = []
board.each_line do |line|
@board << line.split.map{|n| Cell[Integer(n), false] rescue nil} + [nil]
end
@board << [] # frame (Sentinel value : nil)
@board.each_with_index do |row, x|
row.each_with_index do |cell, y|
if cell
@sx, @sy = x, y if cell.value==1 # start position
cell.adj = ADJUST.map{|dx,dy| [x+dx,y+dy]}.select{|xx,yy| @board[xx][yy]}
end
end
end
@xmax = @board.size - 1
@ymax = @board.map(&:size).max - 1
@end = @board.flatten.compact.size
puts to_s('Problem:') if pout
end
def solve
@zbl = Array.new(@end+1, false)
@board.flatten.compact.each{|cell| @zbl[cell.value] = true}
puts (try(@board[@sx][@sy], 1) ? to_s('Solution:') : "No solution")
end
def try(cell, seq_num)
return true if seq_num > @end
return false if cell.used
value = cell.value
return false if value > 0 and value != seq_num
return false if value == 0 and @zbl[seq_num]
cell.used = true
cell.adj.each do |x, y|
if try(@board[x][y], seq_num+1)
cell.value = seq_num
return true
end
end
cell.used = false
end
def to_s(msg=nil)
str = (0...@xmax).map do |x|
(0...@ymax).map{|y| "%3s" % ((c=@board[x][y]) ? c.value : c)}.join
end
(msg ? [msg] : []) + str + [""]
end
end
# Which may be used as follows to solve Evil Case 1:
board1 = <<EOS
. 4
0 7 0
1 0 0
EOS
Hidato.new(board1).solve
# Which may be used as follows to solve this tasks example:
board2 = <<EOS
0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
. . 0 0 18 0 0
. . . . 0 7 0 0
. . . . . . 5 0
EOS
Hidato.new(board2).solve
# Which may be used as follows to solve The Snake in the Grass:
board3 = <<EOS
1 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 74
. . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 .
. . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 .
EOS
t0 = Time.now
Hidato.new(board3).solve
puts " #{Time.now - t0} sec"
# Solve a Hidato Like Puzzle with Warnsdorff like logic applied
#
class HLPsolver
attr_reader :board
Cell = Struct.new(:value, :used, :adj)
def initialize(board, pout=true)
@board = []
frame = ADJACENT.flatten.map(&:abs).max
board.each_line do |line|
@board << line.split.map{|n| Cell[Integer(n), false] rescue nil} + [nil]*frame
end
frame.times {@board << []} # frame (Sentinel value : nil)
@board.each_with_index do |row, x|
row.each_with_index do |cell, y|
if cell
@sx, @sy = x, y if cell.value==1 # start position
cell.adj = ADJACENT.map{|dx,dy| [x+dx,y+dy]}.select{|xx,yy| @board[xx][yy]}
end
end
end
@xmax = @board.size - frame
@ymax = @board.map(&:size).max - frame
@end = @board.flatten.compact.size
@format = " %#{@end.to_s.size}s"
puts to_s('Problem:') if pout
end
def solve
@zbl = Array.new(@end+1, false)
@board.flatten.compact.each{|cell| @zbl[cell.value] = true}
puts (try(@board[@sx][@sy], 1) ? to_s('Solution:') : "No solution")
end
def try(cell, seq_num)
value = cell.value
return false if value > 0 and value != seq_num
return false if value == 0 and @zbl[seq_num]
cell.used = true
if seq_num == @end
cell.value = seq_num
return true
end
a = []
cell.adj.each_with_index do |(x, y), n|
cl = @board[x][y]
a << [wdof(cl.adj)*10+n, x, y] unless cl.used
end
a.sort.each do |key, x, y|
if try(@board[x][y], seq_num+1)
cell.value = seq_num
return true
end
end
cell.used = false
end
def wdof(adj)
adj.count {|x,y| not @board[x][y].used}
end
def to_s(msg=nil)
str = (0...@xmax).map do |x|
(0...@ymax).map{|y| @format % ((c=@board[x][y]) ? c.value : c)}.join
end
(msg ? [msg] : []) + str + [""]
end
end
require 'HLPsolver'
ADJACENT = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
# solve Evil Case 1:
board1 = <<EOS
. 4
0 7 0
1 0 0
EOS
HLPsolver.new(board1).solve
boardx = <<EOS
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
EOS
HLPsolver.new(boardx).solve
# solve this tasks example:
board2 = <<EOS
0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
. . 0 0 18 0 0
. . . . 0 7 0 0
. . . . . . 5 0
EOS
HLPsolver.new(board2).solve
#solve The Snake in the Grass:
board3 = <<EOS
1 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 74
. . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 .
. . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 .
EOS
t0 = Time.now
HLPsolver.new(board3).solve
puts " #{Time.now - t0} sec"
You may also check:How to resolve the algorithm Display a linear combination step by step in the Ruby programming language
You may also check:How to resolve the algorithm Range expansion step by step in the Ruby programming language
You may also check:How to resolve the algorithm Chinese zodiac step by step in the Ruby programming language
You may also check:How to resolve the algorithm Topological sort step by step in the Ruby programming language
You may also check:How to resolve the algorithm Josephus problem step by step in the Ruby programming language