Skip to main content

A library of Knuth's Algorithm X

Works with
It is unknown whether this package works with Bun
It is unknown whether this package works with Cloudflare Workers
This package works with Node.js
This package works with Deno
It is unknown whether this package works with Browsers
JSR Score
100%
Published
2 weeks ago (0.3.2)

algorithm-x

This TypeScript library implements Knuth's Algorithm X and Dancing Links[^1].

Note: It uses ECMAScript 2023 features.

Basic usage

The following problem is taken from the Wikipedia page[^2].

  • the universe U = {1, 2, 3, 4, 5, 6, 7}
  • the collection of set S = {A, B, C, D, E, F}:
    • A = {1, 4, 7}
    • B = {1, 4}
    • C = {4, 5, 7}
    • D = {3, 5, 6}
    • E = {2, 3, 6, 7}
    • F = {2, 7}
import { AlgorithmX } from "@kwj/algorithm-x";

const dlx = new AlgorithmX(7); // [1, 2, 3, 4, 5, 6, 7].length
dlx.addData("A", [1, 4, 7]);
dlx.addData("B", [1, 4]);
dlx.addData("C", [4, 5, 7]);
dlx.addData("D", [3, 5, 6]);
dlx.addData("E", [2, 3, 6, 7]);
dlx.addData("F", [2, 7]);
console.log(dlx.solve().map((x) => x.toSorted())); // [["B", "D", "F"]]

Advanced usage

If you need not only covering exactly once but at most once, such as diagonal lines in the eight queens puzzle, you have to divide constraints into two groups.

Place constraint columns to be covered exactly once on the left side of the matrix, and then create an AlgorithmX object which second parameter is the number of these columns. For more information, see files in the ./example folder.

License

MIT License

[^1]: Dancing links

[^2]: Knuth's Algorithm X

Built and signed on
GitHub Actions
View transparency log

Add Package

deno add @kwj/algorithm-x

Import symbol

import * as mod from "@kwj/algorithm-x";

Add Package

npx jsr add @kwj/algorithm-x

Import symbol

import * as mod from "@kwj/algorithm-x";

Add Package

yarn dlx jsr add @kwj/algorithm-x

Import symbol

import * as mod from "@kwj/algorithm-x";

Add Package

pnpm dlx jsr add @kwj/algorithm-x

Import symbol

import * as mod from "@kwj/algorithm-x";

Add Package

bunx jsr add @kwj/algorithm-x

Import symbol

import * as mod from "@kwj/algorithm-x";