module Bruteforcable

Bruteforcable module provides conventional brute-force search mechanism for any classes, objects that can handle message `build_brute_force_corpus`.

By including Bruteforcable, the class is responsible for calling `setup_for_brute_force(corpus, initial_state)` before issuing brute force process by calling `brute_force`.

Brute force basically try to assign available value to every variables and apply to the state to see if it's a stop state.

The process stops as soon as it reach a stop state.

*Duck typing requirements:*

`corpus` is supposed to handle these messages:

1. `no_variables` which usually means number of variables
2. `available_values(index)` which returns a set of available values for
    variable number index
3. `variable_at(index)` returns variable instance number index
4. `sort_variable(&comp_func)` (optional) sort all variables as compare
    function passed as a block
5. `acquire(variable, value)`, strategy to handle value before assigning
    it to the variable
6. `release(variable, value)`, strategy to handle value before assigning
    the variable to another value

`initial_state` is supposed to handle these messages:

1. `final_state?` which returns true if it's a stop state, false otherwise
2. `apply(variable, value)` which apply a variable with specified value
    to itself

Attributes

corpus[RW]

state[RW]

Public Instance Methods

brute_force() click to toggle source

# File lib/sudoku_solver/brute_force/bruteforcable.rb, line 36
def brute_force
  if self.corpus.no_variables > 0
    try(corpus, 0, self.state)
  end
  return (self.state.final_state? ? self.state : nil)
end

setup_for_brute_force(corpus, initial_state) click to toggle source

# File lib/sudoku_solver/brute_force/bruteforcable.rb, line 58
def setup_for_brute_force(corpus, initial_state)
  self.corpus = corpus
  self.state = initial_state
end

sort_variables(&comp_func) click to toggle source

# File lib/sudoku_solver/brute_force/bruteforcable.rb, line 63
def sort_variables(&comp_func)
  if comp_func
    self.corpus.sort_variables do |a, b|
      comp_func.call(a, b)
    end
  else
    self.curpus.sort_variables
  end
end

try(corpus, index, state) click to toggle source

# File lib/sudoku_solver/brute_force/bruteforcable.rb, line 43
def try(corpus, index, state)
  variable = corpus.variable_at(index)
  corpus.available_values(variable).each do |value|
    corpus.acquire(variable, value)
    state.apply(corpus.variable_at(index), value)
    if index == corpus.no_variables - 1
      return true if state.final_state?
    else
      return true if try(corpus, index + 1, state)
    end
    corpus.release(variable, value)
  end
  return false
end