Implementing CSP with Forward Checking constraint propagation on the example of solving Binary and Futoshiki puzzle
- Problem is defined by set of Variables with their possible values
- Each Variable contains their own number and can be set to a value of int type
- Model class is a problem representation (like Binary puzzle, Futoshiki etc.) that is defined as a set of Variables, Domain and Constraints based on the solving problem
- There is the implementation of both search algoritms: Backtracking and Forward chechikg. See below the comparison of using this methods
Below are two problems taken for an example to demonstrate the use of CSP algorithm
The objective is to fill the grid with 1s and 0s, where there is an equal number of 1s and 0s in each row and column and no more than two of either number adjacent to each other. Additionally, there can be no identical rows or columns.
2. Futoshiki puzzle**
The puzzle is played on a square grid. The goal is to arrange the numbers so that each row and column contains only one of each digit. Some digits may be given at the start. Inequality constraints are initially specified between some of the squares, such that one must be higher or lower than its neighbor. These constraints must be honored in order to complete the puzzle.
- Variable-Selection Heuristics The CSP was implemented with the MRV (Minimum remaining values) heuristic, that means choosing the variable with the fewest “legal” remaining values in its domain. Selecting this value helps detect inconsistencies earlier and, consequently, reduce the number of searches.
- Value-Selection Heuristic After selecting the variable, the order in which the values should be assigned to it must be selected. And to this problem has been implemented a heuristic, which is order values based on how many times each value is shared in a constraint. It means that the least "limiting" value will be selected. Btw after studying the impact of this heuristic was found that using Value-Selection Heuristic is senseles because eventually each value will be selected anyway
Forward checking detects the inconsistency earlier than simple backtracking and thus it allows branches of the search tree that will lead to failure to be pruned earlier than with simple backtracking. This reduces the search tree and (hopefully) the overall amount of work done. Below you can see two graphs that compare both algorithms.
This first graph shows dependence of the used algorithms on the time of finding the first / all solutions (on the example of Binary puzzle). The second graph represents the visited states dependence
