csps
v2.0.2
Published
🛠️ Tools to solve constraint satisfaction problems
Downloads
15
Maintainers
Readme
csps
Tools to solve constraint satisfaction problems: Constraint Satisfaction Problem Solvers.
Inspired by Russell and Norvig's "Artificial Intelligence - A Modern Approach" Python code and modified under the MIT license.
Background
A CSP is a specific type of problem that is represented by states and a goal state. The factored representation of each problem state consists of a set of variables and a value (set of attributes) for each. The problem is considered solve, when all values for each variable satisfy all constraints (Russell, Norvig 2010).
Some example of CSPs would be Sudoku, crosswords, scheduling, map-coloring, n-queens, zebra puzzle, and many others. The tools in this csps
package help setup and solve CSPs.
Installation and Example Usage
install:
npm i csps
index.ts:
import { CSP, min_conflicts } from "csps";
// define the attributes on your variable
interface VariableAttributes {
// {[key: string]: string}
}
// Setup your problem
const variables = [
/* array of strings */
];
const domains = {
/* var: possible_attributes (type: VariableAttributes[]) */
};
const neighbors = {
/* var: neighbors (type: <string>[]) */
};
const constraints = (
var1: string,
var1Attributes: VariableAttributes[],
var2: string,
var2Attributes: VariableAttributes[],
): boolean => {
// Return true if same variable.
if (var1 === var2) {
return true;
}
// more constraints that return false...
// else, return true
return true;
};
const aCSP = new CSP<VariableAttributes>(variables, domains, neighbors, constraints);
// run min_conflicts on problem
const res = min_conflicts(aCSP);
console.log(res);
// {
// var1: { attr1: 'value1', attr2: 'value1', attr3: 'value1' },
// var2: { attr1: 'value2', attr2: 'value2', attr3: 'value2' },
// var3: { attr1: 'value3', attr2: 'value3', attr3: 'value3' },
// } // or something similar.
Demo
View the example for more in-depth example code.
API
Search Functions
Currently, Min-conflicts Hill Climbing is the only search function supported.
- [x] Min-conflicts Hill Climbing
- [ ] AC3
- [ ] AC3b
- [ ] AC4
- [ ] Backtracking
Please view the docs to see the full API.
Contributing
Please feel free to create issues or make PRs.
Acknowledgements
- Thank you to Russell and Norvig for their AIMA textbook and code.
- Thank you to TSDX, TypeDoc, and other open source packages that made this package possible.