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.