{"_id":"@billdaddy/cspkit","name":"@billdaddy/cspkit","dist-tags":{"latest":"0.1.0"},"versions":{"0.1.0":{"name":"@billdaddy/cspkit","version":"0.1.0","description":"Zero-dependency TypeScript Constraint Satisfaction Problem (CSP) solver: backtracking with AC3 arc consistency, MRV heuristic, forward checking, min-conflicts. Like Python python-constraint.","type":"module","main":"./dist/index.cjs","module":"./dist/index.js","types":"./dist/index.d.ts","exports":{".":{"types":"./dist/index.d.ts","import":"./dist/index.js","require":"./dist/index.cjs"}},"scripts":{"build":"tsup","typecheck":"tsc --noEmit","test":"node --experimental-vm-modules node_modules/.bin/jest --forceExit","prepublishOnly":"npm run typecheck && npm test && npm run build"},"keywords":["csp","constraint","satisfaction","backtracking","ac3","arc-consistency","mrv","min-conflicts","n-queens","graph-coloring","sudoku","typescript","zero-dependencies"],"author":{"name":"trananhtung"},"license":"MIT","repository":{"type":"git","url":"git+https://github.com/trananhtung/cspkit.git"},"devDependencies":{"@types/jest":"^30.0.0","jest":"^30.4.2","ts-jest":"^29.4.11","tsup":"^8.5.1","typescript":"^6.0.3"},"_id":"@billdaddy/cspkit@0.1.0","gitHead":"18f20f3356ea89d43a4fdf5f7380f206627c3b16","bugs":{"url":"https://github.com/trananhtung/cspkit/issues"},"homepage":"https://github.com/trananhtung/cspkit#readme","_nodeVersion":"20.18.2","_npmVersion":"11.5.2","dist":{"integrity":"sha512-VX3hQh0yUaV9trnAOmIUw+E+ppbbbnJlNxvmI1GECk6GpTywwIPVIqWNDOX2OfAtRS2F1NrOVmqllMIprip3Ow==","shasum":"c698ce6a095a79f864ff72a108550d80664ce096","tarball":"https://registry.npmjs.org/@billdaddy/cspkit/-/cspkit-0.1.0.tgz","fileCount":9,"unpackedSize":91389,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEYCIQCARd0bu8Oab4/62UuEZ5bqwimtHe0zCOLZdtm0AioI6QIhAMCH+4+G4nDKT31XVuibXiS5aHv0YnQxbVKSnwnvT3KK"}]},"_npmUser":{"name":"billdaddy","email":"tunganhtran94@gmail.com"},"directories":{},"maintainers":[{"name":"billdaddy","email":"tunganhtran94@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/cspkit_0.1.0_1782290108232_0.776458764040828"},"_hasShrinkwrap":false}},"time":{"created":"2026-06-24T08:35:08.017Z","0.1.0":"2026-06-24T08:35:08.367Z","modified":"2026-06-24T08:35:08.516Z"},"maintainers":[{"name":"billdaddy","email":"tunganhtran94@gmail.com"}],"description":"Zero-dependency TypeScript Constraint Satisfaction Problem (CSP) solver: backtracking with AC3 arc consistency, MRV heuristic, forward checking, min-conflicts. Like Python python-constraint.","homepage":"https://github.com/trananhtung/cspkit#readme","keywords":["csp","constraint","satisfaction","backtracking","ac3","arc-consistency","mrv","min-conflicts","n-queens","graph-coloring","sudoku","typescript","zero-dependencies"],"repository":{"type":"git","url":"git+https://github.com/trananhtung/cspkit.git"},"author":{"name":"trananhtung"},"bugs":{"url":"https://github.com/trananhtung/cspkit/issues"},"license":"MIT","readme":"# cspkit\n\n[![All Contributors](https://img.shields.io/badge/all_contributors-1-orange.svg?style=flat-square)](#contributors-)\n\n> Zero-dependency TypeScript Constraint Satisfaction Problem (CSP) solver. Backtracking + AC3 arc consistency + MRV heuristic + forward checking + min-conflicts. Like Python `python-constraint`. Solves N-Queens, Sudoku, graph coloring, scheduling, cryptarithmetic.\n\n[![npm](https://img.shields.io/npm/v/@billdaddy/cspkit)](https://www.npmjs.com/package/@billdaddy/cspkit)\n[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](LICENSE)\n\n## Install\n\n```bash\nnpm install @billdaddy/cspkit\n```\n\n## Quick start\n\n```typescript\nimport { CSP, allDifferent, notEqual } from \"@billdaddy/cspkit\";\n\n// Australia map coloring — no adjacent regions share a color\nconst csp = new CSP();\nconst colors = [\"red\", \"green\", \"blue\"];\nfor (const state of [\"WA\", \"NT\", \"SA\", \"Q\", \"NSW\", \"V\", \"T\"]) {\n  csp.variable(state, colors);\n}\ncsp.constraint([\"WA\", \"NT\"],  notEqual());\ncsp.constraint([\"WA\", \"SA\"],  notEqual());\ncsp.constraint([\"NT\", \"SA\"],  notEqual());\ncsp.constraint([\"NT\", \"Q\"],   notEqual());\ncsp.constraint([\"SA\", \"Q\"],   notEqual());\ncsp.constraint([\"SA\", \"NSW\"], notEqual());\ncsp.constraint([\"SA\", \"V\"],   notEqual());\ncsp.constraint([\"Q\",  \"NSW\"], notEqual());\ncsp.constraint([\"NSW\", \"V\"],  notEqual());\n\nconst solution = csp.solve();\n// { WA: 'red', NT: 'green', SA: 'blue', Q: 'red', NSW: 'green', V: 'red', T: 'red' }\n```\n\n## Why cspkit?\n\nThe npm CSP ecosystem is effectively empty:\n- **csps** — abandoned 2021, only Min-conflicts, 402 annual downloads\n- **edge-coloring** — single algorithm, 1 download/week\n- **python-constraint** port — none\n\nPython's `python-constraint` (PyCSP), Go's constraint solvers, and Ruby's Ruco have been solving CSPs for years. `cspkit` brings the full algorithm stack to npm.\n\n## Core concepts\n\nA CSP has:\n- **Variables** — named slots with a domain of possible values\n- **Constraints** — predicates that must hold over a subset of variables\n- **Solution** — an assignment of values to variables satisfying all constraints\n\n## Examples\n\n### N-Queens\n\n```typescript\nimport { nQueens } from \"@billdaddy/cspkit\";\n\nconst solutions = nQueens(8).solveAll();\n// → 92 solutions, each like { Q0: 0, Q1: 4, Q2: 7, Q3: 5, Q4: 2, Q5: 6, Q6: 1, Q7: 3 }\n```\n\n### Graph coloring\n\n```typescript\nimport { graphColoring } from \"@billdaddy/cspkit\";\n\nconst csp = graphColoring(\n  [[\"A\", \"B\"], [\"B\", \"C\"], [\"A\", \"C\"]],  // triangle\n  [\"red\", \"green\", \"blue\"]\n);\ncsp.solveAll().length; // → 6\n```\n\n### Cryptarithmetic — SEND+MORE=MONEY\n\n```typescript\nconst csp = new CSP();\nconst digits = [0,1,2,3,4,5,6,7,8,9];\nfor (const v of [\"S\",\"E\",\"N\",\"D\",\"M\",\"O\",\"R\",\"Y\"]) csp.variable(v, digits);\ncsp.constraint([\"S\"], notEqualTo(0));\ncsp.constraint([\"M\"], notEqualTo(0));\ncsp.constraint([\"S\",\"E\",\"N\",\"D\",\"M\",\"O\",\"R\",\"Y\"], allDifferent());\ncsp.constraint([\"S\",\"E\",\"N\",\"D\",\"M\",\"O\",\"R\",\"Y\"], (S,E,N,D,M,O,R,Y) => {\n  const [s,e,n,d,m,o,r,y] = [S,E,N,D,M,O,R,Y] as number[];\n  return s*1000+e*100+n*10+d + m*1000+o*100+r*10+e\n    === m*10000+o*1000+n*100+e*10+y;\n});\nconst sol = csp.solve({ ac3: false });\n// → { S:9, E:5, N:6, D:7, M:1, O:0, R:8, Y:2 }\n```\n\n## API\n\n```typescript\nclass CSP {\n  variable(name: string, domain: unknown[]): this\n  constraint(variables: string[], check: (...values: unknown[]) => boolean): this\n\n  solve(options?: SolveOptions): Record<string, unknown> | null\n  solveAll(options?: SolveOptions): Record<string, unknown>[]\n  ac3(): boolean  // run arc consistency (returns false if unsatisfiable)\n  minConflicts(maxSteps?: number): Record<string, unknown> | null\n\n  get variables(): string[]\n  domain(name: string): unknown[]\n}\n\ninterface SolveOptions {\n  ac3?: boolean   // default: true\n  mrv?: boolean   // default: true (Minimum Remaining Values heuristic)\n  limit?: number  // default: Infinity (for solveAll)\n}\n```\n\n### Built-in constraint helpers\n\n```typescript\nallDifferent()           // all variables have distinct values\nnotEqual()               // two variables differ\nequalTo(value)           // variable equals value\nnotEqualTo(value)        // variable not equal to value\nlessThan()               // a < b\nlessThanOrEqual()        // a <= b\ngreaterThan()            // a > b\ngreaterThanOrEqual()     // a >= b\nsumEquals(target)        // sum of all variables equals target\nsumInRange(min, max)     // sum is in [min, max]\ninSet(allowed: Set)      // value is in the allowed set\nnotInSet(excluded: Set)  // value is not in the excluded set\n```\n\n### Problem factories\n\n```typescript\nnQueens(n: number): CSP\ngraphColoring(edges: [string, string][], colors?: unknown[]): CSP\n```\n\n## Algorithms\n\n| Algorithm | When | Effect |\n|---|---|---|\n| **AC3** | pre-solve | Reduces domains using arc consistency — eliminates values that can't participate in any solution |\n| **Backtracking** | main search | Depth-first search with pruning |\n| **MRV** | variable order | Pick variable with fewest remaining values (fails fast) |\n| **Forward checking** | propagation | After assignment, prune inconsistent values from neighbors |\n| **Min-conflicts** | local search | Iterative repair — good for large/overconstrained problems |\n\n## Comparison\n\n| Language | Library | Status | Algorithms |\n|---|---|---|---|\n| Python | `python-constraint` | Active | AC3, backtracking, min-conflicts |\n| Go | `constraint-solver` | Active | Backtracking + propagation |\n| Ruby | `ruco` | Active | Backtracking |\n| npm (old) | `csps` | **Abandoned 2021** | Min-conflicts only |\n| **npm** | **cspkit** | **Active** | AC3 + backtracking + MRV + forward checking + min-conflicts |\n\n## Contributors ✨\n\nThis project follows the [all-contributors](https://github.com/all-contributors/all-contributors) specification. Contributions of any kind are welcome — code, docs, bug reports, ideas, reviews! See the [emoji key](https://allcontributors.org/docs/en/emoji-key) for how each contribution is recognized, and open a PR or issue to get involved.\n\nThanks goes to these wonderful people:\n\n<!-- ALL-CONTRIBUTORS-LIST:START - Do not remove or modify this section -->\n<!-- prettier-ignore-start -->\n<!-- markdownlint-disable -->\n<table>\n  <tbody>\n    <tr>\n      <td align=\"center\" valign=\"top\" width=\"14.28%\"><a href=\"https://github.com/trananhtung\"><img src=\"https://avatars.githubusercontent.com/u/30992229?v=4?s=100\" width=\"100px;\" alt=\"Tung Tran\"/><br /><sub><b>Tung Tran</b></sub></a><br /><a href=\"https://github.com/trananhtung/cspkit/commits?author=trananhtung\" title=\"Code\">💻</a> <a href=\"#maintenance-trananhtung\" title=\"Maintenance\">🚧</a></td>\n    </tr>\n  </tbody>\n</table>\n\n<!-- markdownlint-restore -->\n<!-- prettier-ignore-end -->\n\n<!-- ALL-CONTRIBUTORS-LIST:END -->\n\n## License\n\nMIT © [trananhtung](https://github.com/trananhtung)\n","readmeFilename":"README.md","_rev":"1-63882f33ad4323e381b08069d6187541"}