AIOJ

This page introduces the exact cover problem and the repeated cover problem, the algorithm that solves them—Algorithm X—and the Dancing Links data structure used to optimize Algorithm X. It also explains how to use DLX to solve some search problems with the help of modeling.

Exact Cover Problem

Definition

The exact cover problem (English: Exact Cover Problem) asks, given many sets $S_i (1 \le i \le n)$ and a set $X$ , for an unordered tuple $(T_1, T_2, \cdots , T_m)$ satisfying the following conditions:

$\forall i, j \in [1, m],T_i\bigcap T_j = \varnothing (i \neq j)$
$X = \bigcup\limits_{i = 1}^{m}T_i$
$\forall i \in[1, m], T_i \in \{S_1, S_2, \cdots, S_n\}$

Explanation

For example, suppose we are given

\begin{aligned} & S_1 = \{5, 9, 17\} \\ & S_2 = \{1, 8, 119\} \\ & S_3 = \{3, 5, 17\} \\ & S_4 = \{1, 8\} \\ & S_5 = \{3, 119\} \\ & S_6 = \{8, 9, 119\} \\ & X = \{1, 3, 5, 8, 9, 17, 119\} \end{aligned}

Then $(S_1, S_4, S_5)$ is a valid solution.

Problem Transformation

Discretizing all numbers in $\bigcup\limits_{i = 1}^{n}S_i$ gives the following model:

Given a 0–1 matrix, you may select some rows so that, in the end, every column ¹ contains exactly one 1. For example, modeling the example above gives the following matrix:

\begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}

The $i$ -th row represents $S_i$ , and its entries, in order, represent $[1 \in S_i],[3 \in S_i],[5 \in S_i],\cdots,[119 \in S_i]$ .

Implementation

Brute Force 1

One approach is to enumerate which rows to select and then check whether the resulting plan is valid.

Since each row has two states—selected or not selected—the time complexity of enumerating the rows is $O(2^n)$ .

Each check takes $O(nm)$ time, so the total complexity is $O(nm\cdot2^n)$ .

Implementation

int ok = 0;
for (int state = 0; state < 1 << n; ++state) {  // Enumerate whether each row is selected.
  for (int i = 1; i <= n; ++i)
    if ((1 << i - 1) & state)
      for (int j = 1; j <= m; ++j) a[i][j] = 1;
  int flag = 1;
  for (int j = 1; j <= m; ++j)
    for (int i = 1, bo = 0; i <= n; ++i)
      if (a[i][j]) {
        if (bo)
          flag = 0;
        else
          bo = 1;
      }
  if (!flag)
    continue;
  else {
    ok = 1;
    for (int i = 1; i <= n; ++i)
      if ((1 << i - 1) & state) printf("%d ", i);
    puts("");
  }
  memset(a, 0, sizeof(a));
}
if (!ok) puts("No solution.");

Brute Force 2

Considering the special properties of a 0–1 matrix, each row can be viewed as an $m$ -bit binary number.

Therefore, the original problem becomes

Given $n$ $m$ -bit binary numbers, select some of them so that the bitwise AND of every pair is 0 and the bitwise OR of all selected numbers is $2^m - 1$ . tmp denotes the bitwise OR of the binary numbers selected so far.

Since each row has two states—selected or not selected—the time complexity of enumerating the rows is $O(2^n)$ .

Computing tmp each time takes $O(n)$ time, so the total complexity is $O(n\cdot2^n)$ .

Implementation

int ok = 0;
for (int i = 1; i <= n; ++i)
  for (int j = m; j >= 1; --j) num[i] = num[i] << 1 | a[i][j];
for (int state = 0; state < 1 << n; ++state) {
  int tmp = 0;
  bool flag = true;
  for (int i = 1; i <= n; ++i)
    if ((1 << i - 1) & state) {
      if (tmp & num[i]) {
        flag = false;
        break;
      }
      tmp |= num[i];
    }
  if (flag && tmp == (1 << m) - 1) {
    ok = 1;
    for (int i = 1; i <= n; ++i)
      if ((1 << i - 1) & state) printf("%d ", i);
    puts("");
  }
}
if (!ok) puts("No solution.");

Repeated Cover Problem

The repeated cover problem is similar to the exact cover problem, but it imposes no restriction on overlap between elements. The X algorithm introduced below was originally designed for the exact cover problem, but with the modifications and optimizations marked in the text, it can also solve the repeated cover problem efficiently.

X Algorithm

Donald E. Knuth proposed Algorithm X. Its idea is similar to the brute-force method above, but it is easier to optimize.

Procedure

Continuing with the example mentioned above, we obtain the following 0–1 matrix:

\begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}

At this point, the first row contains $3$ $1$ s, the second row contains $3$ $1$ s, the third row contains $3$ $1$ s, the fourth row contains $2$ $1$ s, the fifth row contains $2$ $1$ s, and the sixth row contains $3$ $1$ s. Select the first row, delete it, and mark every column containing $1$ in it;
$\begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Red}0 & 1 & \color{Red}0 & \color{Red}0 & 1 \\ 0 & 1 & \color{Red}1 & 0 & \color{Red}0 & \color{Red}1 & 0 \\ 1 & 0 & \color{Red}0 & 1 & \color{Red}0 & \color{Red}0 & 0 \\ 0 & 1 & \color{Red}0 & 0 & \color{Red}0 & \color{Red}0 & 1 \\ 0 & 0 & \color{Red}0 & 1 & \color{Red}1 & \color{Red}0 & 1 \end{pmatrix}$
Select all marked columns, delete them, and mark every row containing $1$ in one of those columns (marking rows is unnecessary for the repeated cover problem);
$\begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Red}0 & \color{Red}1 & \color{Blue}1 & \color{Red}0 & \color{Blue}0 & \color{Blue}1 & \color{Red}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 0 \\ 0 & 1 & \color{Blue}0 & 0 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Red}0 & \color{Red}0 & \color{Blue}0 & \color{Red}1 & \color{Blue}1 & \color{Blue}0 & \color{Red}1 \end{pmatrix}$
Select all marked rows and delete them;
$\begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 0 \\ 0 & 1 & \color{Blue}0 & 0 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Blue}0 & \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix}$
This means that the row has been selected, and the columns containing all its $1$ s can no longer contain any other $1$ s.

Thus, we obtain a new, smaller 0–1 matrix:
$\begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix}$
At this point, the first row (originally the second row) contains $3$ $1$ s, the second row (originally the fourth row) contains $2$ $1$ s, and the third row (originally the fifth row) contains $2$ $1$ s. Select the first row (originally the second row), delete it, and mark every column containing $1$ in it;
$\begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Red}1 & 0 & \color{Red}1 & \color{Red}0 \\ \color{Red}0 & 1 & \color{Red}0 & \color{Red}1 \end{pmatrix}$
Select all marked columns, delete them, and mark every row containing $1$ in one of those columns;
$\begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Red}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & \color{Red}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix}$
Select all marked rows and delete them;
$\begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix}$
This gives an empty matrix. However, the row deleted last, 1 0 1 1, was not all $1$ s, which means the choice was incorrect;
$\begin{pmatrix} \end{pmatrix}$
Backtrack to step 4. Consider selecting the second row (originally the fourth row), delete it, and mark every column containing $1$ in it;
$\begin{pmatrix} \color{Red}1 & 0 & \color{Red}1 & 1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Red}0 & 1 & \color{Red}0 & 1 \end{pmatrix}$
Select all marked columns, delete them, and mark every row containing $1$ in one of those columns;
$\begin{pmatrix} \color{Blue}1 & \color{Red}0 & \color{Blue}1 & \color{Red}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & 1 & \color{Blue}0 & 1 \end{pmatrix}$
Select all marked rows and delete them;
$\begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & 1 & \color{Blue}0 & 1 \end{pmatrix}$
We then obtain the following matrix:
$\begin{pmatrix} 1 & 1 \end{pmatrix}$
At this point, the first row (originally the fifth row) contains $2$ $1$ s. Delete them all to obtain an empty matrix:
$\begin{pmatrix} \end{pmatrix}$
The row deleted in the previous step consisted entirely of $1$ s, so the attempt succeeds and the algorithm ends.

The answer is the three deleted rows: $1, 4, 5$ .

We strongly recommend simulating the deletion, restoration, and backtracking process yourself before continuing.

The procedure of Algorithm X can be summarized as follows:

For the current matrix $M$ , select and mark a row $r$ , and add $r$ to $S$ ;
If all choices of $r$ have been tried without finding a solution, end the algorithm and report that there is no solution;
Mark the row $r$ , along with the related rows $r_i$ and columns $c_i$ (related rows and columns are defined as in step 2 of X Algorithm, and the same convention applies below);
Delete all marked rows and columns to obtain a new matrix $M'$ ;
If $M'$ is empty and $r$ consists entirely of $1$ s, end the algorithm and output the set $S$ of deleted rows;

If $M'$ is empty and $r$ is not entirely $1$ , restore the rows related to $r$ , namely $r_i$ , and the columns $c_i$ , then return to step 1;

If $M'$ is not empty, return to step 1.

It is not hard to see that Algorithm X requires many operations to delete and restore rows and columns.

A naive idea is to store the matrix in a two-dimensional array and use four arrays to store the indices of the rows adjacent to each row, updating only those four arrays for each deletion or restoration. However, in a typical problem matrix there are far more 0s than 1s, so the resulting space complexity is unacceptable.

Donald E. Knuth thought of using a doubly linked cross list to maintain these operations.

The repeated jumps through a doubly linked cross list are aptly likened to dancing, so the doubly linked cross list used to optimize Algorithm X is also called “Dancing Links”.

Dancing Links Optimization of Algorithm X

Preprocessor Directive

#define IT(i, A, x) for (i = A[x]; i != x; i = A[i])

Definition

A doubly linked cross list has four pointer fields, pointing to the elements above, below, to the left, and to the right. Each element $i$ also corresponds to a cell in the entire list, so we must represent the column and row containing $i$ , as shown below:

A large doubly linked list is more complicated:

Each row has a row-head pointer, and each column has a column pointer.

The row-head pointer is first[], while the column pointers are the $c + 1$ sentinel nodes we create. Note that a row-head pointer is not a sentinel node in the list. It is virtual, like the first[] array in an adjacency list, and points directly to the first element in its row.

Each column also has a siz[] value representing the number of elements in that column.

In particular, node $0$ having no right neighbor means that this Dancing Links structure is empty.

constexpr int MS = 1e5 + 5;
int n, m, idx, first[MS], siz[MS];
int L[MS], R[MS], U[MS], D[MS];
int col[MS], row[MS];

Procedure

The remove Operation

remove(c) deletes column $c$ and the rows and columns related to it from Dancing Links.

First delete $c$ . Then:

The right neighbor of the node to the left of $c$ should become the right neighbor of $c$ .
The left neighbor of the node to the right of $c$ should become the left neighbor of $c$ .

That is, L[R[c]] = L[c], R[L[c]] = R[c];.

Then traverse down this column, deleting every row encountered.

How do we delete a row? Enumerate the pointers $j$ in the current row. Then:

The lower neighbor of the node above $j$ should become the lower neighbor of $j$ .
The upper neighbor of the node below $j$ should become the upper neighbor of $j$ .

Remember to update the number of elements in each column.

That is, U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];.

The implementation of remove is as follows:

Implementation

void remove(const int &c) {
  int i, j;
  L[R[c]] = L[c], R[L[c]] = R[c];
  // Traverse this column from top to bottom
  IT(i, D, c)
  // Traverse this row from left to right
  IT(j, R, i)
  U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
}

The recover Operation

recover(c) restores column $c$ and the rows and columns related to it in Dancing Links.

recover(c) is the inverse operation of remove(c), so we will not elaborate on it here.

It is worth noting that recover(c) the order of all operations is exactly the reverse of the order of operations in remove(c).

The implementation of recover(c) is as follows:

Implementation

void recover(const int &c) {
  int i, j;
  IT(i, U, c) IT(j, L, i) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
  L[R[c]] = R[L[c]] = c;
}

The build Operation

build(r, c) creates a Dancing Links structure of size $r \times c$ , with $r$ rows and $c$ columns.

Create $c + 1$ nodes as the column pointers.

For node $i$ , the left neighbor is $i - 1$ , the right neighbor is $i + 1$ , the upper neighbor is $i$ , and the lower neighbor is $i$ . In particular, the left neighbor of node $0$ is $c$ , and the right neighbor of node $c$ is $0$ .

Thus, we obtain a circular doubly linked list:

This initializes a Dancing Links structure.

The implementation of build(r, c) is as follows:

Implementation

void build(const int &r, const int &c) {
  n = r, m = c;
  for (int i = 0; i <= c; ++i) {
    L[i] = i - 1, R[i] = i + 1;
    U[i] = D[i] = i;
  }
  L[0] = c, R[c] = 0, idx = c;
  memset(first, 0, sizeof(first));
  memset(siz, 0, sizeof(siz));
}

The insert Operation

insert(r, c) inserts a node into row $r$ , column $c$ .

There are two cases for insertion:

If row $r$ has no elements, insert one element directly and make first[r] point to it.

This can be done with first[r] = L[idx] = R[idx] = idx;.
If row $r$ already has elements, connect the new element to $c$ and $first(r)$ in a special way.

Let the new element be $idx$ . Then:
- Insert $idx$ immediately below $c$ . Then:
  - The node below $idx$ is the node that was originally below $c$ ;
  - The upper neighbor of the node below $idx$ (that is, the node originally below $c$ ) is $idx$ ;
  - The upper neighbor of $idx$ is $c$ ;
  - The lower neighbor of $c$ is $idx$ .
  Remember to record the column and row containing $idx$ , and update the number of elements in this column.
```
col[++idx] = c, row[idx] = r, ++siz[c];
U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx;
```
  We strongly recommend fully understanding the order of these steps before continuing.
- Insert $idx$ immediately to the right of $first(r)$ . Then:
  - The node to the right of $idx$ is the node that was originally to the right of $first(r)$ ;
  - The left neighbor of the node originally to the right of $first(r)$ is $idx$ ;
  - The left neighbor of $idx$ is $first(r)$ ;
  - The right neighbor of $first(r)$ is $idx$ .
```
L[idx] = first[r], R[idx] = R[first[r]];
L[R[first[r]]] = idx, R[first[r]] = idx;
```
  We strongly recommend fully understanding the order of these steps before continuing.

The following image may help clarify insert(r, c):

Pay attention to the directions of the curved arrows.

The implementation of insert(r, c) is as follows:

Implementation

void insert(const int &r, const int &c) {
  row[++idx] = r, col[idx] = c, ++siz[c];
  U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx;
  if (!first[r])
    first[r] = L[idx] = R[idx] = idx;
  else {
    L[idx] = first[r], R[idx] = R[first[r]];
    L[R[first[r]]] = idx, R[first[r]] = idx;
  }
}

The dance Operation

dance() recursively deletes and restores rows and columns.

If node $0$ has no right neighbor, the matrix is empty; record the answer and return;
Select the column with the fewest elements and delete it;
Traverse all rows containing $1$ in this column, enumerating whether each is selected;
Recursively call dance(). If it succeeds, return; otherwise, restore the selected row;
If there is no solution, return.

The implementation of dance() is as follows:

Implementation

bool dance(int dep) {
  int i, j, c = R[0];
  if (!R[0]) {
    ans = dep;
    return true;
  }
  IT(i, R, 0) if (siz[i] < siz[c]) c = i;
  remove(c);
  IT(i, D, c) {
    stk[dep] = row[i];
    IT(j, R, i) remove(col[j]);
    if (dance(dep + 1)) return true;
    IT(j, L, i) recover(col[j]);
  }
  recover(c);
  return false;
}

Here, stk[] records the answer.

Notice that we always delete the column with the fewest elements first. This gives the program a degree of heuristic guidance and minimizes the branching of the search tree.

For the repeated cover problem, an evaluation function (similar to the one in A*) can prune the search: if even the current best case uses more selected rows than the best solution found so far, return directly.

Template

Template Code

#include <cctype>
#include <cstring>
#include <iostream>
constexpr int N = 500 + 10;
int n, m, ans;
int stk[N];

struct DLX {
  static constexpr int MAXSIZE = 1e5 + 10;
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];

  void build(const int &r, const int &c) {  // Perform the build operation
    n = r, m = c;
    for (int i = 0; i <= c; ++i) {
      L[i] = i - 1, R[i] = i + 1;
      U[i] = D[i] = i;
    }
    L[0] = c, R[c] = 0, tot = c;
    memset(first, 0, sizeof(first));
    memset(siz, 0, sizeof(siz));
  }

  void insert(const int &r, const int &c) {  // Perform the insert operation
    col[++tot] = c, row[tot] = r, ++siz[c];
    D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot;
    if (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }

  void remove(const int &c) {  // Perform the remove operation
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i])
      for (j = R[i]; j != i; j = R[j])
        U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }

  void recover(const int &c) {  // Perform the recover operation
    int i, j;
    for (i = U[c]; i != c; i = U[i])
      for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }

  bool dance(int dep) {  // dance
    if (!R[0]) {
      ans = dep;
      return true;
    }
    int i, j, c = R[0];
    for (i = R[0]; i != 0; i = R[i])
      if (siz[i] < siz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
      stk[dep] = row[i];
      for (j = R[i]; j != i; j = R[j]) remove(col[j]);
      if (dance(dep + 1)) return true;
      for (j = L[i]; j != i; j = L[j]) recover(col[j]);
    }
    recover(c);
    return false;
  }
} solver;

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  solver.build(n, m);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      int x;
      cin >> x;
      if (x) solver.insert(i, j);
    }
  solver.dance(1);
  if (ans)
    for (int i = 1; i < ans; ++i) cout << stk[i] << ' ';
  else
    cout << "No Solution!\n";
  return 0;
}

Properties

The number of recursive calls and backtracks in DLX is related to the number of $1$ s in the matrix, not to parameters such as $r, c$ . Therefore, its time complexity is exponential; the theoretical complexity is roughly $O(c^n)$ , where $c$ is a constant very close to $1$ and $n$ is the number of $1$ s in the matrix.

In practice, however, DLX performs well and can generally solve most problems.

Modeling

The difficulty of DLX lies not entirely in building the linked list, but in modeling.

Make sure you have fully mastered the DLX template before continuing.

Whenever we encounter a problem, we should consider what the rows and columns represent:

Rows represent decisions, because each row corresponds to a set and therefore to selecting or not selecting it;
Columns represent states, because column $i$ corresponds to some condition $P_i$ .

For a given row, because the values in different columns are not all the same, a decision is defined by different states.

Example 1 P1784 Sudoku

Solution Outline

First consider what the decisions are.

In this problem, each decision can be represented by an ordered triple of the form $(r, c, w)$ .

Notice that the “block” is not a parameter of the decision, because it is determined by each fixed $(r, c)$ .

Therefore, there are $9 \times 9 \times 9 = 729$ rows.

Next consider what the states are.

Let us consider the effects of the decision $(r, c, w)$ . Denote the block containing $(r, c)$ by $b$ .

Row $r$ uses one $w$ (represented by $9 \times 9 = 81$ columns);
Column $c$ uses one $w$ (represented by $9 \times 9 = 81$ columns);
Block $b$ uses one $w$ (represented by $9 \times 9 = 81$ columns);
A number is placed in $(r, c)$ (represented by $9 \times 9 = 81$ columns).

Therefore, there are $81 \times 4 = 324$ columns and a total of $729 \times 4 = 2916$ $1$ s.

We have thus successfully transformed the $9 \times 9$ Sudoku problem into an exact cover problem with $729$ rows, $324$ columns, and $2916$ $1$ s.

Reference Code

#include <cctype>
#include <cstring>
#include <iostream>
constexpr int N = 1e6 + 10;
int ans[10][10], stk[N];

struct DLX {
  static constexpr int MAXSIZE = 1e5 + 10;
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];

  void build(const int &r, const int &c) {  // Perform the build operation
    n = r, m = c;
    for (int i = 0; i <= c; ++i) {
      L[i] = i - 1, R[i] = i + 1;
      U[i] = D[i] = i;
    }
    L[0] = c, R[c] = 0, tot = c;
    memset(first, 0, sizeof(first));
    memset(siz, 0, sizeof(siz));
  }

  void insert(const int &r, const int &c) {  // Perform the insert operation
    col[++tot] = c, row[tot] = r, ++siz[c];
    D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot;
    if (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }

  void remove(const int &c) {  // Perform the remove operation
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i])
      for (j = R[i]; j != i; j = R[j])
        U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }

  void recover(const int &c) {  // Perform the recover operation
    int i, j;
    for (i = U[c]; i != c; i = U[i])
      for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }

  bool dance(int dep) {  // dance
    int i, j, c = R[0];
    if (!R[0]) {
      for (i = 1; i < dep; ++i) {
        int x = (stk[i] - 1) / 9 / 9 + 1;
        int y = (stk[i] - 1) / 9 % 9 + 1;
        int v = (stk[i] - 1) % 9 + 1;
        ans[x][y] = v;
      }
      return true;
    }
    for (i = R[0]; i != 0; i = R[i])
      if (siz[i] < siz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
      stk[dep] = row[i];
      for (j = R[i]; j != i; j = R[j]) remove(col[j]);
      if (dance(dep + 1)) return true;
      for (j = L[i]; j != i; j = L[j]) recover(col[j]);
    }
    recover(c);
    return false;
  }
} solver;

int GetId(int row, int col, int num) {
  return (row - 1) * 9 * 9 + (col - 1) * 9 + num;
}

void Insert(int row, int col, int num) {
  int dx = (row - 1) / 3 + 1;
  int dy = (col - 1) / 3 + 1;
  int room = (dx - 1) * 3 + dy;
  int id = GetId(row, col, num);
  int f1 = (row - 1) * 9 + num;            // task 1
  int f2 = 81 + (col - 1) * 9 + num;       // task 2
  int f3 = 81 * 2 + (room - 1) * 9 + num;  // task 3
  int f4 = 81 * 3 + (row - 1) * 9 + col;   // task 4
  solver.insert(id, f1);
  solver.insert(id, f2);
  solver.insert(id, f3);
  solver.insert(id, f4);
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  solver.build(729, 324);
  for (int i = 1; i <= 9; ++i)
    for (int j = 1; j <= 9; ++j) {
      cin >> ans[i][j];
      for (int v = 1; v <= 9; ++v) {
        if (ans[i][j] && ans[i][j] != v) continue;
        Insert(i, j, v);
      }
    }
  solver.dance(1);
  for (int i = 1; i <= 9; ++i, cout << '\n')
    for (int j = 1; j <= 9; ++j, cout << ' ') cout << ans[i][j];
  return 0;
}

Example 2 Target Sudoku

Solution Outline

The model for this problem is exactly the same as for Sudoku; the main difference lies in how the answer is updated.

For this problem, we can create a weight array. Each time we find a Sudoku solution,

multiply the number at each position by its corresponding weight and add it to the answer.

Reference Code

#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
constexpr int oo = 0x3f3f3f3f;
constexpr int N = 1e5 + 10;
constexpr int e[] = {6, 6, 6, 6, 6, 6, 6,  6, 6, 6, 7, 7, 7, 7, 7, 7, 7,
                     6, 6, 7, 8, 8, 8, 8,  8, 7, 6, 6, 7, 8, 9, 9, 9, 8,
                     7, 6, 6, 7, 8, 9, 10, 9, 8, 7, 6, 6, 7, 8, 9, 9, 9,
                     8, 7, 6, 6, 7, 8, 8,  8, 8, 8, 7, 6, 6, 7, 7, 7, 7,
                     7, 7, 7, 6, 6, 6, 6,  6, 6, 6, 6, 6, 6};
int ans = -oo, a[10][10], stk[N];

int GetWeight(int row, int col, int num) {  // Multiply a number by its corresponding weight
  return num * e[(row - 1) * 9 + (col - 1)];
}

struct DLX {
  static constexpr int MAXSIZE = 1e5 + 10;
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];

  void build(const int &r, const int &c) {  // Perform the build operation
    n = r, m = c;
    for (int i = 0; i <= c; ++i) {
      L[i] = i - 1, R[i] = i + 1;
      U[i] = D[i] = i;
    }
    L[0] = c, R[c] = 0, tot = c;
    memset(first, 0, sizeof(first));
    memset(siz, 0, sizeof(siz));
  }

  void insert(const int &r, const int &c) {  // Perform the insert operation
    col[++tot] = c, row[tot] = r, ++siz[c];
    D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot;
    if (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }

  void remove(const int &c) {  // Perform the remove operation
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i])
      for (j = R[i]; j != i; j = R[j])
        U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }

  void recover(const int &c) {  // Perform the recover operation
    int i, j;
    for (i = U[c]; i != c; i = U[i])
      for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }

  void dance(int dep) {  // dance
    int i, j, c = R[0];
    if (!R[0]) {
      int cur_ans = 0;
      for (i = 1; i < dep; ++i) {
        int cur_row = (stk[i] - 1) / 9 / 9 + 1;
        int cur_col = (stk[i] - 1) / 9 % 9 + 1;
        int cur_num = (stk[i] - 1) % 9 + 1;
        cur_ans += GetWeight(cur_row, cur_col, cur_num);
      }
      ans = std::max(ans, cur_ans);
      return;
    }
    for (i = R[0]; i != 0; i = R[i])
      if (siz[i] < siz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
      stk[dep] = row[i];
      for (j = R[i]; j != i; j = R[j]) remove(col[j]);
      dance(dep + 1);
      for (j = L[i]; j != i; j = L[j]) recover(col[j]);
    }
    recover(c);
  }
} solver;

int GetId(int row, int col, int num) {
  return (row - 1) * 9 * 9 + (col - 1) * 9 + num;
}

void Insert(int row, int col, int num) {
  int dx = (row - 1) / 3 + 1;    // r
  int dy = (col - 1) / 3 + 1;    // c
  int room = (dx - 1) * 3 + dy;  // room
  int id = GetId(row, col, num);
  int f1 = (row - 1) * 9 + num;            // task 1
  int f2 = 81 + (col - 1) * 9 + num;       // task 2
  int f3 = 81 * 2 + (room - 1) * 9 + num;  // task 3
  int f4 = 81 * 3 + (row - 1) * 9 + col;   // task 4
  solver.insert(id, f1);
  solver.insert(id, f2);
  solver.insert(id, f3);
  solver.insert(id, f4);
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  solver.build(729, 324);
  for (int i = 1; i <= 9; ++i)
    for (int j = 1; j <= 9; ++j) {
      cin >> a[i][j];
      for (int v = 1; v <= 9; ++v) {
        if (a[i][j] && v != a[i][j]) continue;
        Insert(i, j, v);
      }
    }
  solver.dance(1);
  cout << (ans == -oo ? -1 : ans);
  return 0;
}

Example 3 "NOI2005" Smart Marble Game

Solution Approach

Definition: The shape of the smart marble given in the problem is called its standard shape.

Obviously, we can change the shape of a smart marble by changing two parameters: $d$ (the number of times it is rotated $90^{\circ}$ clockwise) and $f$ (whether it is flipped horizontally).

Again, let us first consider what the decisions are.

In this problem, each decision can be represented by the ordered quintuple $(v, d, f, i)$ .

It represents the position of the upper-left corner of the standard shape of the $i$ -th smart marble, whose number is $v$ , after $d$ clockwise rotations by $90^{\circ}$ .

Coincidentally, we can let $f = 1$ mean no horizontal flip and $f = -1$ mean a horizontal flip, thereby simplifying the code.

Therefore, there are $55 \times 4 \times 2 \times 12 = 5280$ rows.

It should be noted that, because of some illegal placements, such as $(1, 0, 1, 4)$ ,

in actual operation, the empty smart-marble board only needs $2730$ rows.

Now let us consider what the states are.

The state in this problem is relatively simple.

Let us think about what effect the decision $(v, d, f, i)$ has.

Some cells are occupied (represented by $55$ columns);
The $i$ -th smart marble is used (represented by $12$ columns).

Therefore, there are $55 + 12 = 67$ columns, and $5280 \times (5 + 1) = 31680$ entries containing $1$ in total.

At this point, we have successfully transformed the smart marble game into an exact cover problem with $5280$ rows, $67$ columns, and $31680$ entries equal to $1$ in total.

Reference Code

#include <cstring>
#include <iostream>
#include <string>
int numcol, numrow;
int dfn[3000], tx[2], nxt[2], num[50][50], vis[50];
std::string ans[50];
constexpr int f[2] = {-1, 1};
constexpr int table[12][5][2] = {
    // directions of shapes
    {{0, 0}, {1, 0}, {0, 1}},                   // A
    {{0, 0}, {0, 1}, {0, 2}, {0, 3}},           // B
    {{0, 0}, {1, 0}, {0, 1}, {0, 2}},           // C
    {{0, 0}, {1, 0}, {0, 1}, {1, 1}},           // D
    {{0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}},   // E
    {{0, 0}, {0, 1}, {1, 1}, {0, 2}, {0, 3}},   // F
    {{0, 0}, {1, 0}, {0, 1}, {0, 2}, {1, 2}},   // G
    {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0, 2}},   // H
    {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}},   // I
    {{0, 0}, {-1, 1}, {0, 1}, {1, 1}, {0, 2}},  // J
    {{0, 0}, {1, 0}, {1, 1}, {2, 1}, {2, 2}},   // K
    {{0, 0}, {1, 0}, {0, 1}, {0, 2}, {0, 3}},   // L
};
constexpr int len[12] = {3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5};
constexpr int getx[] = {
    0,  1,  2,  2,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,  5,  5,  6,
    6,  6,  6,  6,  6,  7,  7,  7,  7,  7,  7,  7,  8,  8,  8,  8,  8,
    8,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,  9,  10, 10, 10, 10, 10,
    10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12,
    12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13,
    13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14};
constexpr int gety[] = {
    0, 1, 1,  2,  1,  2,  3,  1,  2, 3, 4, 1, 2, 3,  4,  5,  1, 2, 3, 4, 5,
    6, 1, 2,  3,  4,  5,  6,  7,  1, 2, 3, 4, 5, 6,  7,  8,  1, 2, 3, 4, 5,
    6, 7, 8,  9,  1,  2,  3,  4,  5, 6, 7, 8, 9, 10, 1,  2,  3, 4, 5, 6, 7,
    8, 9, 10, 11, 1,  2,  3,  4,  5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5,
    6, 7, 8,  9,  10, 11, 12, 13, 1, 2, 3, 4, 5, 6,  7,  8,  9};

struct DLX {
  static constexpr int MS = 1e5 + 10;
  int n, m, tot, first[MS], siz[MS];
  int L[MS], R[MS], U[MS], D[MS];
  int col[MS], row[MS];

  void build(const int &r, const int &c) {
    n = r, m = c;
    for (int i = 0; i <= c; ++i) {
      L[i] = i - 1, R[i] = i + 1;
      U[i] = D[i] = i;
    }
    L[0] = c, R[c] = 0, tot = c;
    memset(first, 0, sizeof(first));
    memset(siz, 0, sizeof(siz));
  }

  void insert(const int &r, const int &c) {  // insert
    col[++tot] = c, row[tot] = r, ++siz[c];
    D[tot] = D[c], U[D[c]] = tot, U[tot] = c, D[c] = tot;
    if (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else
      R[tot] = R[first[r]], L[R[first[r]]] = tot, L[tot] = first[r],
      R[first[r]] = tot;  // !
  }

  void remove(const int &c) {  // remove
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i])
      for (j = R[i]; j != i; j = R[j])
        U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }

  void recover(const int &c) {  // recover
    int i, j;
    for (i = U[c]; i != c; i = U[i])
      for (j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }

  bool dance() {  // dance
    if (!R[0]) return true;
    int i, j, c = R[0];
    for (i = R[0]; i != 0; i = R[i])
      if (siz[i] < siz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
      if (col[i] <= 55) ans[getx[col[i]]][gety[col[i]]] = dfn[row[i]] + 'A';
      for (j = R[i]; j != i; j = R[j]) {
        remove(col[j]);
        if (col[j] <= 55) ans[getx[col[j]]][gety[col[j]]] = dfn[row[j]] + 'A';
      }
      if (dance()) return true;
      for (j = L[i]; j != i; j = L[j]) recover(col[j]);
    }
    recover(c);
    return false;
  }
} solver;

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  for (int i = 1; i <= 10; ++i) {
    cin >> ans[i];
    ans[i] = " " + ans[i];
  }
  for (int i = 1; i <= 10; ++i)
    for (int j = 1; j <= i; ++j) {
      if (ans[i][j] != '.') vis[ans[i][j] - 'A'] = 1;
      num[i][j] = ++numcol;
    }
  solver.build(2730, numcol + 12);
  /*******build*******/
  for (int id = 0, op; id < 12; ++id) {  // every block
    for (++numcol, op = 0; op <= 1; ++op) {
      for (int dx = 0; dx <= 1; ++dx) {
        for (int dy = 0; dy <= 1; ++dy) {
          for (tx[0] = 1; tx[0] <= 10; ++tx[0]) {
            for (tx[1] = 1; tx[1] <= tx[0]; ++tx[1]) {
              bool flag = true;
              // Check if out of bound.
              for (int k = 0; k < len[id]; ++k) {
                nxt[op] = tx[op] + f[dx] * table[id][k][0];
                nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1];
                if (nxt[1] < 1 || nxt[0] < nxt[1] || nxt[0] > 10) {
                  flag = false;
                  break;
                }
              }
              if (!flag) continue;
              // Check if illegal.
              for (int k = 0; k < len[id]; ++k) {
                nxt[op] = tx[op] + f[dx] * table[id][k][0];
                nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1];
                if (vis[id]) {
                  if (ans[nxt[0]][nxt[1]] != id + 'A') {
                    flag = false;
                    break;
                  }
                } else if (ans[nxt[0]][nxt[1]] != '.') {
                  flag = false;
                  break;
                }
              }
              if (!flag) continue;
              // Try to insert.
              dfn[++numrow] = id;
              solver.insert(numrow, numcol);
              for (int k = 0; k < len[id]; ++k) {
                nxt[op] = tx[op] + f[dx] * table[id][k][0];
                nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1];
                solver.insert(numrow, num[nxt[0]][nxt[1]]);
              }
            }
          }
        }
      }
    }
  }
  /********end********/
  if (!solver.dance())
    cout << "No solution\n";
  else
    for (int i = 1; i <= 10; ++i, cout << '\n')
      for (int j = 1; j <= i; ++j) cout << ans[i][j];
  return 0;
}

Exercises

External Links

Notes

Footnotes

(Terminological differences between the two sides of the Taiwan Strait) Taiwan: vertical (column), horizontal (row) ↩