Class ConstraintSolver::ConstraintSolver
In: lib/ConstraintSolver.rb
Parent: Object
Test::Unit::TestCase AllDifferentConstraintTest SolutionTest ConstraintSolverTest ConstraintListTest VariableTest DomainTest BinaryConstraintTest ProblemTest BinaryRelationTest Exception DomainWipeoutException UndoStackEmptyException AbstractConstraint BinaryConstraint AllDifferentConstraint Array ConstraintList BinaryRelation Variable Solution ConstraintSolver Problem Domain test/DomainTest.rb test/SolutionTest.rb lib/BinaryConstraint.rb lib/Variable.rb test/ConstraintListTest.rb lib/ConstraintList.rb test/ProblemTest.rb lib/Solution.rb test/BinaryConstraintTest.rb lib/ConstraintSolver.rb test/VariableTest.rb test/AllDifferentConstraintTest.rb lib/AllDifferentConstraint.rb lib/Problem.rb test/ConstraintSolverTest.rb lib/Domain.rb lib/AbstractConstraint.rb ConstraintSolver dot/m_19_0.png

Methods

assignNextVariable   new   reviseConstraints   solve  

Attributes

log  [R] 

Public Class methods

new()

Initialises a new solver.

[Source]

# File lib/ConstraintSolver.rb, line 14
        def initialize
            @log = Logger.new(self.class.to_s)
        end

Public Instance methods

solve(problem)

Attempts to solve the constraint satisfaction problem and returns a list of all solutions. If there are no solutions, an empty list is returned. Requires the problem to solve as an argument.

[Source]

# File lib/ConstraintSolver.rb, line 21
        def solve(problem)
            @problem = problem
            @constraintChecks = 0
            @nodeChecks = 0
            @solutions = Array.new
            assignNextVariable(@problem.variables.sort { |a,b| b.merit <=> a.merit })
            return @solutions, @nodeChecks, @constraintChecks
        end

Private Instance methods

assignNextVariable(variables)

Attempts to assign a value that is consistent with all constraints to the next variable. Returns true iff a solution to the constraint satisfaction problem was found; i.e. before the call there was only one unassigned variable and a value that is consistent with all constraints was found in its domain. This method calls itself recursively if not all variables have values assigned to them.

[Source]

# File lib/ConstraintSolver.rb, line 38
        def assignNextVariable(variables)
            retval = false
            unassigned = variables.first
            values = unassigned.domain.sort { |a,b|
                (@problem.meritMap.has_key?(b) ? @problem.meritMap[b] : 0) <=>
                (@problem.meritMap.has_key?(a) ? @problem.meritMap[a] : 0)
            }
            values.each { |value|
                unassigned.value = value
                @nodeChecks += 1
                @log.debug("Checking node " + unassigned.to_s)
                revisedDomains, wipeout = reviseConstraints(unassigned)
                if not wipeout # if a domain was wiped out we can skip the rest of the subtree
                    if variables.size == 1
                        solution = Solution.new(@problem.variables, @problem.meritMap)
                        @log.info("Found solution " + solution.to_s)
                        @solutions << solution
                        retval = true
                    else
                        retval = assignNextVariable(variables.rest)
                    end
                end
                revisedDomains.each { |domain| domain.undoPruning }
                #break if retval
            }
            unassigned.reset
            return retval
        end
reviseConstraints(variable)

Revises all constraints that involve variable. Returns the list of domains that have been revised and a boolean indicating whether a domain was wiped out during pruning.

[Source]

# File lib/ConstraintSolver.rb, line 70
        def reviseConstraints(variable)
            revisedDomains = Array.new
            wipeout = false
            queue = @problem.constraints.notAllAssignedWithVariable(variable)
            begin
                while not queue.empty?
                    revisedConstraint = queue.shift
                    @log.debug("Revising constraint " + revisedConstraint.to_s)
                    revisedVariables, checks = revisedConstraint.revise
                    @constraintChecks += checks
                    revisedVariables.each { |variable|
                        revisedDomains << variable.domain
                        @problem.constraints.notAllAssignedWithVariable(variable).each { |constraint|
                            queue << constraint unless queue.include?(constraint) or constraint == revisedConstraint
                        }
                    }
                end
            rescue DomainWipeoutException
                wipeout = true
            end
            return revisedDomains, wipeout
        end

[Validate]