Module TableSalt

TableSalt, Lua framework for constraint satisfaction problems

It goes well with a wide variety of constraint satisfaction problems -- Even ones you cook up yourself!

Github Page

Usage:

    local CSP = require('TableSalt/TableSalt')
local TableSalt = CSP.TableSalt
local Pepper = CSP.Pepper

Info:

  • Copyright: 2014
  • License: MIT
  • Author: Shakil Thakur

Class TableSalt

TableSalt:new (domain, sizeX, sizeY) Creates a new TableSalt instance.
TableSalt:setAddVarsAfterAnyChange (bool) switch to toggle when additional constraints should be added for solveConstraints.
TableSalt:getAddVarsAfterAnyChange () returns where it's adding constraints.
TableSalt:getIDByName (n) Returns the id given a variable name
TableSalt:getIDByPair (x, y) Returns the id given a pair.
TableSalt:getValueByID (i) Returns the value given the id
TableSalt:getValueByName (n) Returns the value given a name
TableSalt:getValueByPair (x, y) Returns the value given a pair.
TableSalt:getDomainByID (i) Returns the domain given the id.
TableSalt:getDomainByName (n) Returns the domain given a name
TableSalt:getDomainByPair (x, y) Returns the domain given a pair.
TableSalt:addConstraintByIDs (section, pepperConstraint, ...) add a constraint to the board via IDs.
TableSalt:addConstraintByPairs (section, pepperConstraint, ...) add a constraint to the board via x,y position.
TableSalt:addConstraintByNames (section, pepperConstraint, ...) add a constraint based on the name given in the input table.
TableSalt:addConstraintForEachRow (pepperConstraint, ...) adds a constraint for each row.
TableSalt:addConstraintForEachColumn (pepperConstraint, ...) adds a constraint for each column.
TableSalt:addConstraintForAll (pepperConstraint, ...) adds a constraint for all values.
TableSalt:isFilled () determines if each variable has a value
TableSalt:isSolved () determines if the problem is solved based on the constraints that were added
TableSalt:solveConstraints (specificCellID) runs the AC3 algorithm to reduce domains/solve the problem
TableSalt:getSmallestDomainID () returns the id associated with the variable with the smallest domain.
TableSalt:solveForwardCheck () runs the forward check algorithm in the current state.
TableSalt:solve () solve the constraint satisfaction problem.
TableSalt:print () prints out the problem either as a table, a row, or a grid.

Pepper Constraints

Pepper Pepper Constraints are constraints written as functions that reduce the domain on a set of variables.
Pepper.allDiff (section, board) ensures all numbers in a section are of a different value
Pepper.setVal (section, board, val) sets the value of the cell[s].

CSP module

CSP CSP module that is passed back by the script.


Class TableSalt

TableSalt:new (domain, sizeX, sizeY)
Creates a new TableSalt instance. This will initialize a table, where each cell has a unique id which hold a value and a domain that can be accessed through various getters, as described below.

Parameters:

  • domain the domain for each of the cells in the problem
  • sizeX the length of the input or a table representing the variables
  • sizeY (optional) - the height of the domain space if the CSP exists over a grid

Returns:

    a new TableSalt instance

Usage:

     local TableSalt = require('TableSalt/TableSalt')
 local aussie = TableSalt:new({"Red", "Green", "Blue"}, {"WA", "NT", "SA", "Q", "NSW", "V", "T"}) -- for the australia coloring problem.
 local sudoku = TableSalt:new({1,2,3,4,5,6,7,8,9}, 9, 9) -- for sudoku. Creates a 9x9 grid
 local linear = TableSalt:new({1,2,3,4,5,6,7,8,9}, 9) -- basically creates a 9x1 grid, for problems that don't really require a grid, but can be enumerated
TableSalt:setAddVarsAfterAnyChange (bool)
switch to toggle when additional constraints should be added for solveConstraints. When this is true, it will act like the classic AC3 algorithm and add constraints after any domain has changed. When it's false, it will only add contraints after a value has been set (aka, the domain has been reduced to 1). If the problem is easily solved by constraints, setting this to true will incur a huge speedup (as in the case for sudoku).

Parameters:

  • bool default is true

Usage:

     local sudoku = TableSalt:new({1,2,3,4,5,6,7,8,9}, 9, 9)
 sudoku:setAddVarsAfterAnyChange(false)
TableSalt:getAddVarsAfterAnyChange ()
returns where it's adding constraints.

Returns:

    true if after any domain change. false if only when a variable is assigned
TableSalt:getIDByName (n)
Returns the id given a variable name

Parameters:

  • n the name of a variable used in the problem

Returns:

    the id associated with the given name

Usage:

     local aussie = TableSalt:new({"Red", "Green", "Blue"}, {"WA", "NT", "SA", "Q", "NSW", "V", "T"})
 aussie:getIDByName("NSW") -- will return the ID for NSW
TableSalt:getIDByPair (x, y)
Returns the id given a pair. (0,0) represents the top left

Parameters:

  • x the x position from the left
  • y the y position from the top

Returns:

    the id associated with the pair

Usage:

     local sudoku = TableSalt:new({1,2,3,4,5,6,7,8,9}, 9, 9)
 sudoku:getIDByPair(5,5) -- will return the id of the centermost cell
TableSalt:getValueByID (i)
Returns the value given the id

Parameters:

  • i the id of the cell

Returns:

    the value associated with the given id or nil if it hasn't been set.

Usage:

     local linear = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 8)
 -- various problem constraints would go here
 linear:solve()
 linear:getValueByID(7) -- will return the value for the 7th item
TableSalt:getValueByName (n)
Returns the value given a name

Parameters:

  • n the name of the variable

Returns:

    the value associated with the given name or nil if it hasn't been set.

Usage:

     local aussie = TableSalt:new({"Red", "Green", "Blue"}, {"WA", "NT", "SA", "Q", "NSW", "V", "T"})
 -- the various australia color problem constraints would go here
 aussie:solveForwardCheck()
 aussie:getValueByName("WA") -- will return the value that was set for "WA" (western australia)
TableSalt:getValueByPair (x, y)
Returns the value given a pair. (0,0) represents the top left

Parameters:

  • x the x position from the left
  • y the y position from the top

Returns:

    the value associated with the pair or nil if it hasn't been set.

Usage:

     local sudoku = TableSalt:new({1,2,3,4,5,6,7,8,9}, 9, 9)
 -- the various sudoku constraints would go here
 sudoku:solve()
 sudoku:getValueByPair(5,5) -- will return the value of the centermost cell.
TableSalt:getDomainByID (i)
Returns the domain given the id.

Parameters:

  • i the id

Returns:

    the domain (as a table) associated with the id. {nil} if empty

Usage:

     local linear = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 8)
 -- various problem constraints would go here
 linear:solveConstraints()
 linear:getDomainyID(7) -- will return the domain for the 7th item. Ex: {4, 6, 8}
TableSalt:getDomainByName (n)
Returns the domain given a name

Parameters:

  • n the name of the variable

Returns:

    the domain (as a table) associated with the given name. {nil} if empty

Usage:

     local aussie = TableSalt:new({"Red", "Green", "Blue"}, {"WA", "NT", "SA", "Q", "NSW", "V", "T"})
 -- the various australia color problem constraints would go here
 aussie:solveForwardCheck()
 aussie:getDomainByName("WA") -- will return the domain for "WA" Ex: {"Green"}
TableSalt:getDomainByPair (x, y)
Returns the domain given a pair. (0,0) represents the top left

Parameters:

  • x the x position from the left
  • y the y position from the top

Returns:

    the domain (as a table) associated with the given pair. {nil} if empty

Usage:

     local sudoku = TableSalt:new({1,2,3,4,5,6,7,8,9}, 9, 9)
 -- the various sudoku constraints would go here
 sudoku:solveConstraints()
 sudoku:getDomainByPair(5,5) -- will return the domain of the centermost cell. Ex: {1, 3, 5}
 sudoku:solveForwardCheck()
 sudoku:getDomainByPair(5,5) -- should be solved, so only one thing in the domain. Ex: {5}
TableSalt:addConstraintByIDs (section, pepperConstraint, ...)
add a constraint to the board via IDs. For more information, check out PepperConstraints.md

Parameters:

  • section a table of id's
  • pepperConstraint a function which reduces domains based on a constraint
  • ... any additional arguments pepperConstraint requires

Usage:

     local linear = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9)
 --id's 1, 3, and 5 have to be different
 linear:addConstraintByIDs({1, 3, 5}, Pepper.allDiff)
TableSalt:addConstraintByPairs (section, pepperConstraint, ...)
add a constraint to the board via x,y position. For more information, check out PepperConstraints.md

Parameters:

  • section a table of x,y pairs
  • pepperConstraint a function which reduces domains based on a constraint
  • ... any additional arguments pepperConstraint requires

Usage:

     local sudoku = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 9)
 -- (1, 1), (5, 2), and (7, 2) all have a value of 4
 sudoku:addConstraintByPairs({ {1, 1}, {5, 2}, {7, 2} }, Pepper.setVal, 4)
TableSalt:addConstraintByNames (section, pepperConstraint, ...)
add a constraint based on the name given in the input table. For more information, check out PepperConstraints.md

Parameters:

  • section a table of names
  • pepperConstraint a function which reduces domains based on a constraint
  • ... any additional arguments pepperConstraint requires

Usage:

     local aussie = TableSalt:new({"Red", "Green", "Blue"}, {"WA", "NT", "SA", "Q", "NSW", "V", "T"})
 aussie:addConstraintByNames({ "WA", "NT", "SA" }, Pepper.allDiff)
TableSalt:addConstraintForEachRow (pepperConstraint, ...)
adds a constraint for each row. This is handy for grid based problems. For more information, check out PepperConstraints.md

Parameters:

  • pepperConstraint a function which reduces domains based on a constraint
  • ... any additional arguments pepperConstraint requires

Usage:

     local sudoku = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 9)
 sudoku:addConstraintForEachRow(Pepper.allDiff)
TableSalt:addConstraintForEachColumn (pepperConstraint, ...)
adds a constraint for each column. This is handy for grid based problems. For more information, check out PepperConstraints.md

Parameters:

  • pepperConstraint a function which reduces domains based on a constraint
  • ... any additional arguments pepperConstraint requires

Usage:

     local sudoku = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 9)
 sudoku:addConstraintForEachColumn(Pepper.allDiff)
TableSalt:addConstraintForAll (pepperConstraint, ...)
adds a constraint for all values. For more information, check out PepperConstraints.md

Parameters:

  • pepperConstraint a function which reduces domains based on a constraint
  • ... any additional arguments pepperConstraint requires

Usage:

     local linear = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9)
 linear:addConstraintForAll(Pepper.allDiff)
TableSalt:isFilled ()
determines if each variable has a value

Returns:

    true if each cell has a value, false otherwise

Usage:

     local aussie = TableSalt:new({"Red", "Green", "Blue"}, {"WA", "NT", "SA", "Q", "NSW", "V", "T"})
 aussie:isFilled() -- should return false
TableSalt:isSolved ()
determines if the problem is solved based on the constraints that were added

Returns:

    true if all constraints are satisfied (domain has been reduced to 1 value). false otherwise

Usage:

     local aussie = TableSalt:new({"Red", "Green", "Blue"}, {"WA", "NT", "SA", "Q", "NSW", "V", "T"})
 --all the australia color constraints go here
 aussie:isSolved() --should return false
 aussie:solveForwardCheck()
 -- isSolved should now return true as the values have been set.
 aussie:isSolved()
TableSalt:solveConstraints (specificCellID)
runs the AC3 algorithm to reduce domains/solve the problem

Parameters:

  • specificCellID (optional) useful for running constrains only associated with one cell. If omitted, solveConstraints will use all constraints

Returns:

    true if the problem was solved. false otherwise
TableSalt:getSmallestDomainID ()
returns the id associated with the variable with the smallest domain. If there's a tie, it uses the degree heuristic which picks the variable with the larger number of constraints

Returns:

    the id of the variable with the smallest domain

Usage:

     linear = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9)
 --some of linear's constraints are added here
 linear:solveConstraints()
 --after that, I may want to get ahold of the domain the with smallest id
 linear:getSmallestDomainID()
TableSalt:solveForwardCheck ()
runs the forward check algorithm in the current state. It goes through each variable, tries a value from the domain, runs solveConstraints to prune, backtracks if necessary, and finally determines a solution.

Returns:

    true if the problem is solved. false otherwise

Usage:

     local aussie = TableSalt:new({"Red", "Green", "Blue"}, {"WA", "NT", "SA", "Q", "NSW", "V", "T"})
 -- the various australia color problem constraints would go here
 -- the Australia color problem doesn't benefit from calling solveConstraints as no domains are reduced.
 aussie:solveForwardCheck()
TableSalt:solve ()
solve the constraint satisfaction problem. This will call solveConstraints to reduce the domains and then solveForwardCheck to finish solving the problem

Returns:

    true if the problem was able to be solved. false if not.

Usage:

     local sudoku = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 9)
 sudoku:setAddVarsAfterAnyChange(false)
 sudoku:addConstraintForEachColumn(Pepper.allDiff)
 --all the other sudoku constraints go here
 sudoku:solve()
 sudoku:print() -- print out the problem.
TableSalt:print ()
prints out the problem either as a table, a row, or a grid. How it prints out is dependent on how the inputs were given. If the variables were given as a table, it will print out as a table. Otherwise it will print out as a grid.

Usage:

     local sudoku = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 9)
 --add all the sudoku constraints here

 -- will show a 9x9 grid of ?s
 sudoku:print()
 sudoku:solve()
 --will show the solved sudoku puzzle now that it's solved
 sudoku:print()

Pepper Constraints

Pepper
Pepper Constraints are constraints written as functions that reduce the domain on a set of variables. For more information, check out PepperConstraints.md
Pepper.allDiff (section, board)
ensures all numbers in a section are of a different value

Parameters:

  • section the id's of all variables the constraint is applied to as a table
  • board the self referential TableSalt instance

Returns:

    the new domain of each of the id's in section as a table. They should correlate so section[1]'s new domain should be the first element in the table that is returned.

Usage:

     local sudoku = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 9)
 --this will ensure that each the values in each row are all different
 sudoku:addConstraintForEachRow(Pepper.allDiff)
Pepper.setVal (section, board, val)
sets the value of the cell[s]. Used as a constraint satisfaction function.

Parameters:

  • section the id's of all variables the constraint is applied to as a table
  • board the self referential TableSalt instance
  • val the value that each variable in the section should be set to

Returns:

    the new domain of each of the id's in section as a table. They should correlate so section[1]'s new domain should be the first element in the table that is returned.

Usage:

     local sudoku = TableSalt:new({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 9)
 --this will set the value of (1, 1), (2, 2), and (3, 3) to all be 9.
 --the setVal function is run by various methods to determine values/successes
 sudoku:addConstraintByPairs({{1, 1}, {2, 2}, {3, 3}}, Pepper.setVal, 9)

CSP module

CSP
CSP module that is passed back by the script. Containing both the TableSalt class and the Pepper constraints.

Fields:

  • TableSalt reference to the TableSalt class
  • Pepper reference to the Pepper constraints
  • _VERSION the version of the current module

Usage:

     local CSP = require('TableSalt/TableSalt')
 local TableSalt = CSP.TableSalt
 local Pepper = CSP.Pepper
generated by LDoc 1.4.2