The easiest, but perhaps not the fastest, way to go about this would be
recursion. Write a function that performs one step at a time, and calls
itself again and again until the goal is reached. For each step, you can
check whether the step is allowed or prohibited by some custom
restrictions.
Here’s some exemplary code to get you started. Use it from the command
line like this:
$ ruby grid.rb 1 1
=> {:POS_X=>1, :POS_Y=>1, :GOAL_X=>1, :GOAL_Y=>1, :STEPS=>0, :PATH=>[]}
=> found 1 solution(s)
(we’re at the goal already)
$ ruby grid.rb 3 3
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:right, :right, :down, :down]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:right, :down, :right, :down]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:right, :down, :down, :right]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:down, :right, :right, :down]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:down, :right, :down, :right]}
=> {:POS_X=>3, :POS_Y=>3, :GOAL_X=>3, :GOAL_Y=>3, :STEPS=>4,
:PATH=>[:down, :down, :right, :right]}
=> found 6 solution(s)
Here’s the actual code, the entire state (current position, goal, number
of steps, step taken etc.) are stored in the hash array “state”. I think
you should find it easy to add custom restrictions. Just change the
functions can_step_down? and can_step_right?; and add more entries to
the state hash if necessary.
Get the dimensions of the grid from the command line.
DIM_X = ARGV.shift.to_i
DIM_Y = ARGV.shift.to_i
###Main function###
Check whether we’re at the goal, otherwise take one step to
the right and left.
Calls itself recursively until the goal is reached.
def take_one_step(state=initialize_state,solutions=[],&block)
if solution?(state)
yield state
else
if can_step_right?(state)
step_right(state)
take_one_step(state,solutions,&block)
undo_step_right(state)
end
if can_step_down?(state)
step_down(state)
take_one_step(state,solutions,&block)
undo_step_down(state)
end
end
solutions
end
###Helper functions###
We start out at the top-left corner.
def initialize_state
{
:POS_X => 1,
:POS_Y => 1,
:GOAL_X => DIM_X,
:GOAL_Y => DIM_Y,
:STEPS => 0,
:PATH => []
}
end
Take a step to the right, updating the state accordingly.
def step_right(state)
state[:POS_X] += 1
state[:STEPS] += 1
state[:PATH] << :right
end
Undo the step to the right, ie. reset the state hash.
def undo_step_right(state)
state[:POS_X] -= 1
state[:STEPS] -= 1
state[:PATH].pop
end
Take a step down, updating the state accordingly.
def step_down(state)
state[:POS_Y] += 1
state[:STEPS] += 1
state[:PATH] << :down
end
Undo the step down, ie. reset the state hash.
def undo_step_down(state)
state[:POS_Y] -= 1
state[:STEPS] -= 1
state[:PATH].pop
end
# Are we allowed to step right? You can add custom restrictions here.
def can_step_right?(state)
state[:POS_X] < state[:GOAL_X]
end
Are we allowed to step down? You can add custom restrictions here.
def can_step_down?(state)
state[:POS_Y] < state[:GOAL_Y]
end
Is this state a solution, ie. are we at the goal?
def solution?(state)
state[:POS_X] == state[:GOAL_X] && state[:POS_Y] == state[:GOAL_Y]
end
###MAIN###
Call the recursive function and print the result.
i = 0
take_one_step do |sol|
p sol
i += 1
end
puts “found #{i} solution(s)”
For a grid of size 14x14 I’m getting (after removing the print statement
for every solution) 10_400_600 solutions in 30 seconds on my machine.
