Class: Sudoku::SolutionSet::Process

Inherits:
Object
  • Object
show all
Defined in:
lib/sudoku/solution_set/process.rb,
lib/sudoku/solution_set/process/step.rb,
lib/sudoku/solution_set/process/out_of_history.rb,
lib/sudoku/solution_set/process/steps/delete_redundant_choices.rb,
lib/sudoku/solution_set/process/steps/pick_unsatisfied_constraint.rb,
lib/sudoku/solution_set/process/steps/move_choice_into_included_set.rb,
lib/sudoku/solution_set/process/steps/pick_choice_satisfying_constraint.rb

Defined Under Namespace

Modules: Steps Classes: OutOfHistory, Step

Constant Summary collapse

STEPS = 
Hash[[
  :pick_unsatisfied_constraint,
  :pick_choice_satisfying_constraint,
  :move_choice_into_included_set,
  :delete_redundant_choices
]
FALLBACKS = 
{
  :pick_choice_satisfying_constraint => :pick_choice_satisfying_constraint
}

Instance Method Summary collapse

Constructor Details

#initialize(solution_set) ⇒ Process

Returns a new instance of Process.



25
26
27
28
 
# File 'lib/sudoku/solution_set/process.rb', line 25

def initialize(solution_set)
  @solution_set = solution_set
  @queue, @history = [], []
end

Instance Method Details

#fallback(step) ⇒ Object 



107
108
109
 
# File 'lib/sudoku/solution_set/process.rb', line 107

def fallback(step)
  FALLBACKS[STEPS.invert[step.class]]
end

#prepare_next_run ⇒ Object 



92
93
94
 
# File 'lib/sudoku/solution_set/process.rb', line 92

def prepare_next_run
  queue_backtrack(:pick_choice_satisfying_constraint)
end

#proceed ⇒ Object 



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/sudoku/solution_set/process.rb', line 70

def proceed
  item = @queue.shift

  case item[:action]
  when :take
    if output = item[:step].take(item[:input])
      @history << item

      if output == :solved
        return :solved
      end

      queue(successor(item[:step]), :input => output)
    else
      queue_backtrack(fallback(item[:step]))
    end
  when :revert
    item[:step].revert
    @history.pop
  end
end

#queue(step, options = {}) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/sudoku/solution_set/process.rb', line 43

def queue(step, options={})
  options = { :action => :take }.merge(options)

  if step.is_a?(Symbol)
    step = STEPS[step].new(@solution_set)
  end

  @queue << {
    :action => options[:action],
    :step   => step,
    :input  => options[:input]
  }
end

#queue_backtrack(step) ⇒ Object

Raises:



57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/sudoku/solution_set/process.rb', line 57

def queue_backtrack(step)
  @history.reverse_each do |item|
    queue(item[:step], :action => :revert)

    if item[:step].class == STEPS[step]
      queue(item[:step])
      return
    end
  end

  raise OutOfHistory, "unable to backtrack to #{step}"
end

#run! ⇒ Object 



30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/sudoku/solution_set/process.rb', line 30

def run!
  loop do
    if @queue.empty?
      queue(STEPS.keys.first)
    else
      if proceed == :solved
        prepare_next_run
        return true
      end
    end
  end
end

#successor(step) ⇒ Object 



96
97
98
99
100
101
102
103
104
105
 
# File 'lib/sudoku/solution_set/process.rb', line 96

def successor(step)
  names = STEPS.keys
  classes = STEPS.values

  if step.class == classes.last
    names.first
  else
    names[classes.index(step.class) + 1]
  end
end