Content deleted Content added
Adding short description: "Algorithm for exact cover problem" (Shortdesc helper) |
m →Example: {{mathcal}} class="wikitable" |
||
Line 28:
==Example==
For example, consider the exact cover problem specified by the universe ''U'' = {1, 2, 3, 4, 5, 6, 7} and the collection of sets
:* ''A'' = {1, 4, 7};
:* ''B'' = {1, 4};
Line 38:
This problem is represented by the matrix:
:{| class="wikitable"
! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
Line 68:
Step 2—The lowest number of 1s in any column is two. Column 1 is the first column with two 1s and thus is selected (deterministically):
:{| class="wikitable"
! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
Line 100:
: Step 5—Row ''A'' has a 1 in columns 1, 4, and 7:
::{| class="wikitable"
! !! <span style="color:blue">1</span> !! 2 !! 3 !! <span style="color:blue">4</span> !! 5 !! 6 !! <span style="color:blue">7</span>
|-
Line 124:
: Column 1 has a 1 in rows ''A'' and ''B''; column 4 has a 1 in rows ''A'', ''B'', and ''C''; and column 7 has a 1 in rows ''A'', ''C'', ''E'', and ''F''. Thus, rows ''A'', ''B'', ''C'', ''E'', and ''F'' are to be removed and columns 1, 4 and 7 are to be removed:
::{| class="wikitable"
! !! <span style="color:red">1</span> !! 2 !! 3 !! <span style="color:red">4</span> !! 5 !! 6 !! <span style="color:red">7</span>
|-
Line 148:
: Row ''D'' remains and columns 2, 3, 5, and 6 remain:
::{| class="wikitable"
! !! 2 !! 3 !! 5 !! 6
|-
Line 159:
: Step 2—The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s:
::{| class="wikitable"
! !! <span style="color:red">2</span> !! 3 !! 5 !! 6
|-
Line 175:
: Row ''B'' has a 1 in columns 1 and 4:
::{| class="wikitable"
! !! <span style="color:blue">1</span> !! 2 !! 3 !! <span style="color:blue">4</span> !! 5 !! 6 !! 7
|-
Line 199:
: Column 1 has a 1 in rows ''A'' and ''B''; and column 4 has a 1 in rows ''A'', ''B'', and ''C''. Thus, rows ''A'', ''B'', and ''C'' are to be removed and columns 1 and 4 are to be removed:
::{| class="wikitable"
! !! <span style="color:red">1</span> !! 2 !! 3 !! <span style="color:red">4</span> !! 5 !! 6 !! 7
|-
Line 223:
: Rows ''D'', ''E'', and ''F'' remain and columns 2, 3, 5, 6, and 7 remain:
::{| class="wikitable"
! !! 2 !! 3 !! 5 !! 6 !! 7
|-
Line 240:
: Step 2—The lowest number of 1s in any column is one. Column 5 is the first column with one 1 and thus is selected (deterministically):
::{| class="wikitable"
! !! 2 !! 3 !! <span style="color:red">5</span> !! 6 !! 7
|-
Line 263:
:: Step 5—Row ''D'' has a 1 in columns 3, 5, and 6:
:::{| class="wikitable"
! !! 2 !! <span style="color:blue">3</span> !! <span style="color:blue">5</span> !! <span style="color:blue">6</span> !! 7
|-
Line 278:
:: Column 3 has a 1 in rows ''D'' and ''E''; column 5 has a 1 in row ''D''; and column 6 has a 1 in rows ''D'' and ''E''. Thus, rows ''D'' and ''E'' are to be removed and columns 3, 5, and 6 are to be removed:
:::{| class="wikitable"
! !! 2 !! <span style="color:red">3</span> !! <span style="color:red">5</span> !! <span style="color:red">6</span> !! 7
|-
Line 293:
:: Row ''F'' remains and columns 2 and 7 remain:
:::{| class="wikitable"
! !! 2 !! 7
|-
Line 314:
::: Row ''F'' has a 1 in columns 2 and 7:
::::{|
! !! <span style="color:blue">2</span> !! <span style="color:blue">7</span>
|-
Line 323:
::: Column 2 has a 1 in row ''F''; and column 7 has a 1 in row ''F''. Thus, row ''F'' is to be removed and columns 2 and 7 are to be removed:
::::{|
! !! <span style="color:red">2</span> !! <span style="color:red">7</span>
|-
Line 334:
::: As rows ''B'', ''D'', and ''F'' are selected, the final solution is:
::::{|
! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
Line 357:
There are no branches at level 0, thus the algorithm terminates.
In summary, the algorithm determines there is only one exact cover:
==Implementations==
| |||