Knuth's Algorithm X: Difference between revisions

Revision as of 03:53, 6 September 2011

Revision as of 03:42, 7 September 2011

Line 1:

[[Donald Knuth]]'s '''Algorithm X''' is a [[recursion (computer science)|recursive]], [[Nondeterministic_algorithmNondeterministic algorithm|nondeterministic]], [[depth-first]], [[backtracking]] [[algorithm]] that finds all solutions to the [[exact cover]] problem represented by a matrix ''A'' consisting of 0s and 1s. The goal is to select a subset of the rows so that the digit 1 appears in each column exactly once.

Algorithm X functions as follows:

Line 144:

|}

: Row ''D'' remains and columns 2, 3, 5, and 6 remain:

::{| border="1" cellpadding="5" cellspacing="0"

Line 219:

|}

: Rows ''D'', ''E'', and ''F'' remain and columns 2, 3, 5, 6, and 7 remain:

::{| border="1" cellpadding="5" cellspacing="0"

Line 289:

|}

:: Row ''F'' remains and columns 2 and 7 remain:

:::{| border="1" cellpadding="5" cellspacing="0"

Line 379:

==External links==

*[http://cheeso.members.winisp.net/srcview.aspx?dir=Sudoku&file=ExactCover.cs Implementation of an Exact Cover solver in C#] - uses Algorithm X and the Dancing Links optimization.

* [http://github.com/mlepage/polycube-solver Polycube solver] Program (with Lua source code) to fill boxes with polycubes using [[Algorithm X]].

Line 385 ⟶ 384:

{{Donald Knuth navbox}}

[[Category:Search algorithms]]

[[Category:Donald Knuth]]