Skip to content

JavaScript library to solve exact cover problems by implementing Donald E. Knuth's Algorithm X using the Dancing Links technique

Notifications You must be signed in to change notification settings

taylorjg/dlxlibjs

Repository files navigation

CircleCI

Description

This is a JavaScript library to solve exact cover problems by implementing Donald E. Knuth's Algorithm X using the Dancing Links technique.

Demos

(These projects are hosted on the Heroku free tier so may take 10s or so to spin up)

Documentation

NOTE: This documentation pertains to the dlxlib@next release of dlxlib.

Example

NOTE: This example pertains to the dlxlib@next release of dlxlib.

const { Dlx } = require('dlxlib')

const matrix = [
  [1, 0, 0, 0],
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 1],
  [0, 1, 0, 0],
  [0, 0, 1, 0]
]

const onStep = e =>
  console.log(`step[${e.stepIndex}]: ${e.partialSolution}`)

const onSolution = e =>
  console.log(`solution[${e.solutionIndex}]: ${e.solution}`)

const dlx = new Dlx()
dlx.on('step', onStep)
dlx.on('solution', onSolution)
dlx.solve(matrix)

// step[0]: 0
// step[1]: 0,3
// step[2]: 0,3,4
// solution[0]: 0,3,4
// step[3]: 2
// step[4]: 2,1
// solution[1]: 2,1
// step[5]: 2,4
// step[6]: 2,4,5
// solution[2]: 2,4,5

Migrating from 1.0.3 to 2.0.0

See the migration guide.

About

JavaScript library to solve exact cover problems by implementing Donald E. Knuth's Algorithm X using the Dancing Links technique

Topics

Resources

Stars

Watchers

Forks

Packages

No packages published