csp v0.1.0 Csp.Problems
Test constraint satisfaction problems.
Link to this section Summary
Functions
Returns an instance of a constraint satisfaction problem for map coloring of Australian states.
Returns an example of a correct solution of the map coloring Csp.
Returns an example of a wrong solution of the map coloring Csp.
Returns an instance of N-queens problem
for the specified n.
Returns an instance of N-queens problem
for the specified n. Note, that this returns a more complicated representation of N Queens problem:
this is useful for demonstrating representation-dependence of the problem solving performance only.
Pretty-prints an N Queens problem solution represented as row to column associations
(generated by nqueens/1).
Pretty-prints an N Queens problem solution represented as cell assignments
(generated by nqueens_slow/2).
Pretty prints a prefilled or solved Sudoku
from sudoku_cells_map, mapping cell coordinates to values.
Returns an example Csp struct for the following problem
Defines a Sudoku puzzle, with prefilled map of unary constraints
for prefilled variables.
Returns a CSP corresponding to the example Sudoku from Wikipedia.
A cells map of prefilled values from an example Sudoku from Wikipedia.
Link to this section Types
sudoku_cells_map()
Specs
sudoku_cells_map() :: %{required({row :: 0..8, column :: 0..8}) => 1..9}
Link to this section Functions
map_coloring()
Specs
map_coloring() :: Csp.t()
Returns an instance of a constraint satisfaction problem for map coloring of Australian states.
map_coloring_example_solution()
Specs
map_coloring_example_solution() :: Csp.assignment()
Returns an example of a correct solution of the map coloring Csp.
map_coloring_wrong_solution()
Specs
map_coloring_wrong_solution() :: Csp.assignment()
Returns an example of a wrong solution of the map coloring Csp.
nqueens(n \\ 8)
Specs
nqueens(non_neg_integer()) :: Csp.t()
Returns an instance of N-queens problem
for the specified n.
The variables in the returned CSP are queen rows (1-indexed); domains are corresponding columns (also 1-indexed).
E.g., 2 => 4 assignment means that the queen is positioned on the row 2 and column 4.
To solve this, we suggest running the following:
alias Csp.{Problems, Searcher}
queens8 = nqueens()
Searcher.backtrack(queens8)nqueens_slow(n \\ 8, use_row_placement_constraints \\ true)
Returns an instance of N-queens problem
for the specified n. Note, that this returns a more complicated representation of N Queens problem:
this is useful for demonstrating representation-dependence of the problem solving performance only.
The second argument determines the way we constraint the number of queens that we require to be placed on the board:
true(default) will use 8 row constraints, saying that each row should have exactly one queenfalsewill use a global constraint on all cells, saying that we should have exactlynqueens.
They are semantically equivalent, but may lead to different performance for solvers. Perhaps counterintuitevely, at least for backtracking it's easier to solve the problem with row-based placement constraints (even though we have more constraints in total), since we find inconsistencies earlier.
The variables in the returned CSP are cell coordinates (0-indexed, {row, column});
domains are boolean (true if a queen is placed in the corresponding cell).
To solve this, we suggest running the following:
alias Csp.{Problems, Searcher}
queens8 = nqueens_slow()
Searcher.backtrack(queens8)pretty_print_nqueens(assignment, n \\ 8)
Specs
pretty_print_nqueens(Csp.assignment(), non_neg_integer()) :: :ok
Pretty-prints an N Queens problem solution represented as row to column associations
(generated by nqueens/1).
pretty_print_nqueens_slow(assignment, n \\ 8)
Specs
pretty_print_nqueens_slow(Csp.assignment(), non_neg_integer()) :: :ok
Pretty-prints an N Queens problem solution represented as cell assignments
(generated by nqueens_slow/2).
pretty_print_sudoku(sudoku_cells_map)
Specs
pretty_print_sudoku(sudoku_cells_map()) :: :ok
Pretty prints a prefilled or solved Sudoku
from sudoku_cells_map, mapping cell coordinates to values.
squares(max_value \\ 9)
Specs
squares(non_neg_integer()) :: Csp.t()
Returns an example Csp struct for the following problem:
Y = X ^ 2
where X, Y are >= 0 and <= `max_value`max_value defaults to 9.
sudoku(prefilled)
Specs
sudoku(sudoku_cells_map()) :: Csp.t()
Defines a Sudoku puzzle, with prefilled map of unary constraints
for prefilled variables.
prefilled should be a map matching cell coordinates (expressed as
tuples {row, column}, with 0-indexed rows and column) to theire prefilled values.
wiki_sudoku()
Specs
wiki_sudoku() :: Csp.t()
Returns a CSP corresponding to the example Sudoku from Wikipedia.
wiki_sudoku_cells_map()
Specs
wiki_sudoku_cells_map() :: sudoku_cells_map()
A cells map of prefilled values from an example Sudoku from Wikipedia.