DLX

CmsMartin · 2021-11-11 16:36:32 · 题解

update2022.8.3：修改问题定义的第一条的错误。

更好的阅读体验

精确覆盖问题

问题定义

精确覆盖问题（英文：Exact Cover Problem) 是指给定许多集合 S_i(1\leq i \leq n) 以及一个集合 X ，求满足以下条件的无序多元组 (T_1,T_2,\cdots,T_m)：

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

例如，若给出：

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\}

则 (S_1,S_4 , S_5) 为一组合法解。

问题转化

将 \bigcup\limits_{i=1}^n S_i 中的所有数离散化，可以得到这么一个模型：

给定一个 01 矩阵，你可以选择一些行，使得最终每列都恰好有一个 1。举个例子，我们对上文中的例子进行建模，可以得到这么一个矩阵：

其中第 i 行表示着 S_i ，而这一行的每个数依次表示:

暴力求解

方法 1：直接暴力枚举，时间复杂度 O(nm \cdot 2^n)

int ok = 0;
for (int state = 0; state < 1 << n; ++state) {  // 枚举每行是否被选
  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.");

方法 2：二进制优化枚举，时间复杂度 O(n \cdot 2 ^ n)

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;
  for (int i = 1; i <= n; ++i)
    if ((1 << i - 1) & state) {
      if (tmp & num[i]) break;
      tmp |= num[i];
    }
  if (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.");

Algorithm X

算法过程

对于现在的矩阵 M ，选择并标记一列 r，将 r 添加至 S 中；
如果尝试了所有的 r 却无解，则算法结束，输出无解；
标记与 r 相关的行 r_i 和 c_i；
删除所有标记的行和列，得到新矩阵 M'；
如果 M' 为空，且 r 为全 1 ，则算法结束，输出被删除的行组成的集合；

如果 M' 为空，且 r 不全为 1 ，则恢复与 r 相关的行 r_i 以及列 c_i，跳转至步骤 1；

如果 M' 不为空，则跳转至步骤 1。

不难看出，X 算法需要大量的“删除行”、“删除列”和“恢复行”、“恢复列”的操作。

Donald E. Knuth 想到了用双向十字链表来维护这些操作。

而在双向十字链表上不断跳跃的过程被形象地比喻成“跳跃”，因此被用来优化 X 算法的双向十字链表也被称为 “Dancing Links” 。

所以舞蹈链算法名为 Dancing Links X（Dancing Links 优化 X 算法）

Dancing Links X

双向十字链表中存在四个指针域，分别指向上、下、左、右的元素；且每个元素在整个双向十字链表系中都对应着一个格子，因此还要表示所在的列和所在的行，如图所示：

图片来自于Oi-Wiki

大型的双向链表则更为复杂：

图片来自于 Oi-Wiki

所需变量

对于每个节点，需要左指针，右指针，上指针，下指针，以及该节点的行列信息；

int N , M , Cnt; //矩阵的长，宽，点的数量

int Left[MAXN] , Right[MAXN] , Up[MAXN] , Down[MAXN]; //每个节点的左指针，右指针，上指针，下指针

int Row[MAXN] , Cal[MAXN]; //行，列信息指针

int Head[MAXN] , S[MAXN]; //每行的头结点 , 每列的结点数

InIt

初始化结果(图片来源于 Oi-Wiki )：

显然用类似于双向链表的方式初始化，~~非常简单~~

void InIt(int M) {
    for(int i = 0; i <= M; i++) {
        Right[i] = i + 1;
        Left[i] = i - 1;
        Up[i] = Down[i] = i;
    }
    Right[M] = 0; //M的右侧是0
    Left[0] = M;  //0的左侧是M
    memset(Head , -1 , sizeof Head);
    memset(S , 0 , sizeof S);
    Cnt = M + 1; //开始时有M个结点（0结点和各列头结点）
}

Links

插入操作分为两种基本情况

如果第 R 行没有元素，那么直接插入一个元素，并使 Head[R] 指向这个元素。这可以通过 Head[R] = Right[Cnt] = Left[Cnt] = Cnt; 来实现。
如果第 R 行有元素，用类似于双向链表的方式将该点插入到 Head[R] 的正右方

Right[Cnt] = Head[R];
Left[Cnt] = Left[Head[R]];
Right[Left[Head[R]]] = Cnt;
Left[Head[R]] = Cnt;

最后用类似于双向链表的方式将该点插入到 C 的正下方

Up[Cnt] = C; 
Down[Cnt] = Down[C];
Up[Down[C]] = Cnt;
Down[C] = Cnt;

图解(来源于 Oi-Wiki )：

void Link(int R , int C) { //在R行C列插入点
    S[C]++; //C 列节点多了1个
    Row[Cnt] = R; //更新该节点的行号
    Col[Cnt] = C; //更新该节点的列标
    Up[Cnt] = C; 
    Down[Cnt] = Down[C];
    Up[Down[C]] = Cnt;
    Down[C] = Cnt;
    if(Head[R] == -1) { //该行没有别的点,把第一个加入的点作为该行的行头结点
        Head[R] = Right[Cnt] = Left[Cnt] = Cnt;
    }
    else { 
        Right[Cnt] = Head[R];
        Left[Cnt] = Left[Head[R]];
        Right[Left[Head[R]]] = Cnt;
        Left[Head[R]] = Cnt;
    }
    ++Cnt;
    return;
}

ReMove

ReMove(C) 表示在 Dancing Links 中删除第 C 列以及与其相关的行和列。

先将 C 删除，此时：

即为 Right[Left[C]] = Right[C],Left[Right[C]] = Left[C];

然后顺着这一列往下走，把走过的每一行都删掉。

如何删掉每一行呢？枚举当前行的指针 j ，此时：

**注意要修改每一列的元素个数。**

即 Up[Down[j]] = Up[j],Down[Up[j]] = Down[j],S[Col[j]]--;。

void ReMove(int C) {
    Right[Left[C]] = Right[C];
    Left[Right[C]] = Left[C];
    //顺着这一列从上往下遍历
    for(int i = Down[C]; i != C; i = Down[i]) {
        //顺着这一列从左往右遍历
        for(int j = Right[i]; j != i; j = Right[j]) {
            Up[Down[j]] = Up[j];
            Down[Up[j]] = Down[j];
            S[Col[j]]--;
        }
    }
}

ReSume

ReSume 就是逆着跑一此 ReMove ,不做解释

注意操作顺序与 ReMove 正好相反

void ReSume(int C) {
    for(int i = Up[C]; i != C; i = Up[i]) {
        for(int j = Left[i]; j != i; j = Left[j]) {
            Up[Down[j]] = j;
            Down[Up[j]] = j;
            S[Col[j]]++;
        }
    }
    Right[Left[C]] = C;
    Left[Right[C]] = C;
}

Dance

dance() 即为递归地删除以及还原各个行列的过程。

如果 0 号结点没有右结点，那么矩阵为空，记录答案并返回；
选择列元素个数最少的一列，并删掉这一列；
遍历这一列所有有 1 的行，枚举它是否被选择；
递归调用 dance()，如果可行，则返回；如果不可行，则恢复被选择的行；如果无解，则返回。

bool Dance(int Dep) {
    if(Right[0] == 0) {
        for(int i = 0; i < Dep; i++)
            cout << Ans[i] << " ";
        return 1;
    }
    int C = Right[0];
    int i , j;
    for(i = Right[0]; i != 0; i = Right[i]) if(S[i] < S[C]) C = i;
    ReMove(C);
    for(i = Down[C]; i != C; i = Down[i]) {
        Ans[Dep] = Row[i];
        for(j = Right[i]; j != i; j = Right[j]) ReMove(Col[j]);
        if(Dance(Dep + 1)) return 1;
        for(int j = Left[i]; j != i; j = Left[j]) ReSume(Col[j]);
    }
    ReSume(C);
    return 0;
}

注意我们每次优先选择列元素个数最少的一列进行删除，这样能保证程序具有一定的启发性，使搜索树分支最少。

时间复杂度

DLX 递归及回溯的次数与矩阵中 1 的个数有关，与矩阵的 r , c 等参数无关。因此，它的时间复杂度是 指数级 的，理论复杂度大概在 O(c^n) 左右，其中 c 为某个非常接近于 1 的常数，n 为矩阵中 1 的个数。

的个数。

但实际情况下 DLX 表现良好，一般能解决大部分的问题

例题讲解

【模板】舞蹈链（DLX）

题目传送门

思路

直接使用 DLX 算法，无技术含量

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250100;

int N , M;
int Cnt;
int Left[MAXN] , Right[MAXN] , Up[MAXN] , Down[MAXN] , Col[MAXN] , Row[MAXN];

int Head[MAXN];

int S[MAXN];

int Ans[MAXN];

void InIt(int M) {
    for(int i = 0; i <= M; i++) {
        Right[i] = i + 1;
        Left[i] = i - 1;
        Up[i] = Down[i] = i;
    }
    Right[M] = 0;
    Left[0] = M;
    memset(Head , -1 , sizeof Head);
    memset(S , 0 , sizeof S);
    Cnt = M + 1;
}

void Link(int R , int C) {
    S[C]++;
    Row[Cnt] = R;
    Col[Cnt] = C;
    Up[Cnt] = C;
    Down[Cnt] = Down[C];
    Up[Down[C]] = Cnt;
    Down[C] = Cnt;
    if(Head[R] == -1) {
        Head[R] = Right[Cnt] = Left[Cnt] = Cnt;
    }
    else {
        Right[Cnt] = Head[R];
        Left[Cnt] = Left[Head[R]];
        Right[Left[Head[R]]] = Cnt;
        Left[Head[R]] = Cnt;
    }
    ++Cnt;
    return;
}

void ReMove(int C) {
    Right[Left[C]] = Right[C];
    Left[Right[C]] = Left[C];
    for(int i = Down[C]; i != C; i = Down[i]) {
        for(int j = Right[i]; j != i; j = Right[j]) {
            Up[Down[j]] = Up[j];
            Down[Up[j]] = Down[j];
            S[Col[j]]--;
        }
    }
}

void ReSume(int C) {
    for(int i = Up[C]; i != C; i = Up[i]) {
        for(int j = Left[i]; j != i; j = Left[j]) {
            Up[Down[j]] = j;
            Down[Up[j]] = j;
            S[Col[j]]++;
        }
    }
    Right[Left[C]] = C;
    Left[Right[C]] = C;
}

bool Dance(int Dep) {
    if(Right[0] == 0) {
        for(int i = 0; i < Dep; i++)
            cout << Ans[i] << " ";
        return 1;
    }
    int C = Right[0];
    int i , j;
    for(i = Right[0]; i != 0; i = Right[i]) if(S[i] < S[C]) C = i;
    ReMove(C);
    for(i = Down[C]; i != C; i = Down[i]) {
        Ans[Dep] = Row[i];
        for(j = Right[i]; j != i; j = Right[j]) ReMove(Col[j]);
        if(Dance(Dep + 1)) return 1;
        for(int j = Left[i]; j != i; j = Left[j]) ReSume(Col[j]);
    }
    ReSume(C);
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> M;
    int f;
    InIt(M);

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            cin >> f;
            if(f) Link(i , j);
        }
    }
    if(!Dance(0)) cout << "No Solution!" << endl;

    return 0;
}

[USACO1.5]八皇后 Checker Challenge

题目传送门

思路

对于八皇后问题我们可以把它转化为精确覆盖的问题：

每行只能放一个皇后
每列只能放一个皇后
每一个“/”斜行只能放一个皇后
每一个“\”斜行只能放一个皇后
我们把每个状态当成列，每个点当成一行然后精确覆盖这个矩阵

注意：与模版不同的是我们只需保证每行每列完全覆盖而每一斜行是肯定不能完全覆盖的（因为一共 2n-1 个斜行）

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100100;

long long ToT;

int N;
int Cnt;
int Left[MAXN] , Right[MAXN] , Up[MAXN] , Down[MAXN] , Col[MAXN] , Row[MAXN];

int Head[MAXN];

int S[MAXN];

int Ans[MAXN];

struct Node {
    int ans[14];
}SS[100000];

void InIt(int M) {
    for(int i = 0; i <= M; i++) {
        Right[i] = i + 1;
        Left[i] = i - 1;
        Up[i] = Down[i] = i;
    }
    Right[M] = 0;
    Left[0] = M;
    memset(Head , -1 , sizeof Head);
    memset(S , 0 , sizeof S);
    Cnt = M + 1;
}

void Link(int R , int C) { // Add (R , C)
    S[C]++;
    Row[Cnt] = R;
    Col[Cnt] = C;
    Up[Cnt] = C;
    Down[Cnt] = Down[C];
    Up[Down[C]] = Cnt;
    Down[C] = Cnt;
    if(Head[R] < 0) {
        Head[R] = Right[Cnt] = Left[Cnt] = Cnt;
    }
    else {
        Right[Cnt] = Head[R];
        Left[Cnt] = Left[Head[R]];
        Right[Left[Head[R]]] = Cnt;
        Left[Head[R]] = Cnt;
    }
    ++Cnt;
    return;
}

void ReMove(int C) {
    Right[Left[C]] = Right[C];
    Left[Right[C]] = Left[C];
    for(int i = Down[C]; i != C; i = Down[i]) {
        for(int j = Right[i]; j != i; j = Right[j]) {
            Up[Down[j]] = Up[j];
            Down[Up[j]] = Down[j];
            S[Col[j]]--;
        }
    }
}

void ReSume(int C) {
    for(int i = Up[C]; i != C; i = Up[i]) {
        for(int j = Left[i]; j != i; j = Left[j]) {
            Up[Down[j]] = j;
            Down[Up[j]] = j;
            S[Col[j]]++;
        }
    }
    Right[Left[C]] = C;
    Left[Right[C]] = C;
}

void Dance(int Dep) {
    if(Right[0] > N) {
        ++ToT;
        for(int i = 0 , x , y; i < Dep; i++) {
            x = Ans[i] % N;
            y = (Ans[i] - 1) / N + 1;
            if(x == 0) x = N;
            SS[ToT].ans[x] = y;
        }
        return;
    }
    int C = Right[0];
    int i , j;
    for(i = Right[0]; i <= N ; i = Right[i]) 
        if(S[i] < S[C]) C = i;
    ReMove(C);
    for(i = Down[C]; i != C; i = Down[i]) {
        Ans[Dep] = Row[i];
        for(j = Right[i]; j != i; j = Right[j]) ReMove(Col[j]);
        Dance(Dep + 1);
        for(j = Left[i]; j != i; j = Left[j]) ReSume(Col[j]);
    }
    ReSume(C);
    return;
}

bool Cmp(Node a , Node b) {
    int i = 1;
    while(a.ans[i] == b.ans[i] && i <= N)
        ++i;
    return a.ans[i] < b.ans[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N ;
    int f = 0;
    InIt(6 * N - 2);
    //一共n*n格对应n*n行
    //对于第m列
    //若[1,n]对应在第m行放皇后 
    //若[n+1,2*n]对应在第m-n列放皇后 
    //若[2*n+1,4*n-1]对应在第m-2*n“\”斜行放皇后 （共2*n-1个“\”斜行） 
    //若[4*n,6*n-2]对应在第m-4*n+1“/”斜行放皇后（共2*n-1个“/”斜行） 
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            ++f;
            Link(f , i);
            Link(f , j + N);
            Link(f , i - j + 3 * N);
            Link(f , i + j + 4 * N - 2);
        }
    }

    Dance(0);

    sort(SS + 1 , SS + 1 + ToT , Cmp); 

    for(int i = 1; i <= 3; i++){
        for(int j = 1; j <= N; j++)
            cout << SS[i].ans[j] << " ";
        cout << endl;
    }

    cout << ToT << endl;

    return 0;
}

数独

题目传送门

思路

对于求解数独可以把它转化为精确覆盖的问题：

每个点只能填一个数
每个行只能填每种数各一个
每个列只能填每种数各一个
每个宫只能填每种数各一个

于是我们把点对应成一个集合，包含 4 个元素，分别表示对应的数，行，列，宫。然后精确覆盖即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250100;

inline int read() {
    int ret = 0;
    char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') {
        ret = (ret << 3) + (ret << 1) + c - 48;
        c = getchar();
    }
    return ret;
}

int N , M;
int Cnt;
int Left[MAXN] , Right[MAXN] , Up[MAXN] , Down[MAXN] , Col[MAXN] , Row[MAXN];

int Head[MAXN];

int S[MAXN];

int Ans[MAXN];

int Num[10][10];

void InIt(int M) {
    for(int i = 0; i <= M; i++) {
        Right[i] = i + 1;
        Left[i] = i - 1;
        Up[i] = Down[i] = i;
    }
    Right[M] = 0;
    Left[0] = M;
    memset(Head , -1 , sizeof Head);
    memset(S , 0 , sizeof S);
    Cnt = M + 1;
}

void Link(int R , int C) { // Add (R , C)
    S[C]++;
    Row[Cnt] = R;
    Col[Cnt] = C;
    Up[Cnt] = C;
    Down[Cnt] = Down[C];
    Up[Down[C]] = Cnt;
    Down[C] = Cnt;
    if(Head[R] == -1) {
        Head[R] = Right[Cnt] = Left[Cnt] = Cnt;
    }
    else {
        Right[Cnt] = Head[R];
        Left[Cnt] = Left[Head[R]];
        Right[Left[Head[R]]] = Cnt;
        Left[Head[R]] = Cnt;
    }
    ++Cnt;
    return;
}

void ReMove(int C) {
    Right[Left[C]] = Right[C];
    Left[Right[C]] = Left[C];
    for(int i = Down[C]; i != C; i = Down[i]) {
        for(int j = Right[i]; j != i; j = Right[j]) {
            Up[Down[j]] = Up[j];
            Down[Up[j]] = Down[j];
            S[Col[j]]--;
        }
    }
}

void ReSume(int C) {
    for(int i = Up[C]; i != C; i = Up[i]) {
        for(int j = Left[i]; j != i; j = Left[j]) {
            Up[Down[j]] = j;
            Down[Up[j]] = j;
            S[Col[j]]++;
        }
    }
    Right[Left[C]] = C;
    Left[Right[C]] = C;
}

bool Dance(int Dep) {
    if(Right[0] == 0) {
        for(int i = 0 , x , y , v; i < Dep; i++) {
            x = (Ans[i] - 1) / 9 / 9;
            y = (Ans[i] - 1) / 9 % 9;
            v = (Ans[i]) % 9;
            if(v == 0) v = 9;
            Num[x][y] = v;
        }
        return 1;
    }
    int C = Right[0];
    int i , j;
    for(i = Right[0]; i != 0; i = Right[i]) if(S[i] < S[C]) C = i;
    ReMove(C);
    for(i = Down[C]; i != C; i = Down[i]) {
        Ans[Dep] = Row[i];
        for(j = Right[i]; j != i; j = Right[j]) ReMove(Col[j]);
        if(Dance(Dep + 1)) return 1;
        for(int j = Left[i]; j != i; j = Left[j]) ReSume(Col[j]);
    }
    ReSume(C);
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    N = 729;
        M = 324;
    InIt(M);

        for (int i = 0 , x , o; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                    cin >> Num[i][j];
                    x = Num[i][j];
                    for(int k = 1; k <= 9; k++) {
                        if(x != k && x != 0) continue;
                        Link(i * 9 * 9 + j * 9 + k , i * 9 + j + 1);
                        Link(i * 9 * 9 + j * 9 + k , i * 9 + 81 + k);
                        Link(i * 9 * 9 + j * 9 + k , j * 9 + 81 * 2 + k);
                        Link(i * 9 * 9 + j * 9 + k , 81 * 3 + (i / 3 * 3 + j / 3) * 9 + k);
                    }
            }
        }

     Dance(0);

        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++)
                cout << Num[i][j] << " ";
            cout << endl;
        }
    return 0;
}

[NOIP2009 提高组] 靶形数独

题目传送门

思路

首先，要将数独问题转化为一个精确覆盖问题。

于是我们重新建立一个 (N \times N \times N) 矩阵。

由于每个格子只能填一个数，用 1 \sim 81 列表示每一个是否填数
由于每个数在每一列只能出现一次，用 82 \sim 162 列表示是否满足这个条件
行和宫的方法是一样的

接着，枚举每个格子的方案，将这些方案在新的矩阵中所能覆盖的格子用二维链表连起来。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250100;

inline int read() {
    int ret = 0;
    char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') {
        ret = (ret << 3) + (ret << 1) + c - 48;
        c = getchar();
    }
    return ret;
}

int N , M;
int Cnt;
int Left[MAXN] , Right[MAXN] , Up[MAXN] , Down[MAXN] , Col[MAXN] , Row[MAXN];

int Head[MAXN];

int S[MAXN];

int Ans[MAXN];

long long Sum;

int Value[9][9]={
    {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}
};

void InIt(int M) {
    for(int i = 0; i <= M; i++) {
        Right[i] = i + 1;
        Left[i] = i - 1;
        Up[i] = Down[i] = i;
    }
    Right[M] = 0;
    Left[0] = M;
    memset(Head , -1 , sizeof Head);
    memset(S , 0 , sizeof S);
    Cnt = M + 1;
}

void Link(int R , int C) { // Add (R , C)
    S[C]++;
    Row[Cnt] = R;
    Col[Cnt] = C;
    Up[Cnt] = C;
    Down[Cnt] = Down[C];
    Up[Down[C]] = Cnt;
    Down[C] = Cnt;
    if(Head[R] == -1) {
        Head[R] = Right[Cnt] = Left[Cnt] = Cnt;
    }
    else {
        Right[Cnt] = Head[R];
        Left[Cnt] = Left[Head[R]];
        Right[Left[Head[R]]] = Cnt;
        Left[Head[R]] = Cnt;
    }
    ++Cnt;
    return;
}

void ReMove(int C) {
    Right[Left[C]] = Right[C];
    Left[Right[C]] = Left[C];
    for(int i = Down[C]; i != C; i = Down[i]) {
        for(int j = Right[i]; j != i; j = Right[j]) {
            Up[Down[j]] = Up[j];
            Down[Up[j]] = Down[j];
            S[Col[j]]--;
        }
    }
}

void ReSume(int C) {
    for(int i = Up[C]; i != C; i = Up[i]) {
        for(int j = Left[i]; j != i; j = Left[j]) {
            Up[Down[j]] = j;
            Down[Up[j]] = j;
            S[Col[j]]++;
        }
    }
    Right[Left[C]] = C;
    Left[Right[C]] = C;
}

void Dance(int Dep) {
    if(Right[0] == 0) {
        long long sum = 0;
        for(int i = 0 , x , y , v; i < Dep; i++) {
            x = (Ans[i] - 1) / 9 / 9;
            y = (Ans[i] - 1) / 9 % 9;
            v = (Ans[i] - 1) % 9;
            sum += Value[x][y] * (v + 1);
        }
        Sum = max(Sum , sum);
        return;
    }
    int C = Right[0];
    int i , j;
    for(i = Right[0]; i != 0; i = Right[i]) if(S[i] < S[C]) C = i;
    ReMove(C);
    for(i = Down[C]; i != C; i = Down[i]) {
        Ans[Dep] = Row[i];
        for(j = Right[i]; j != i; j = Right[j]) ReMove(Col[j]);
        Dance(Dep + 1);
        for(int j = Left[i]; j != i; j = Left[j]) ReSume(Col[j]);
    }
    ReSume(C);
    return;
}

int main() {
    ios::sync_with_stdio(false);
    N = 729;
        M = 324;
    InIt(M);

        for (int i = 0 , x; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                    cin >> x;
                    for(int k = 1; k <= 9; k++) {
                        if(x != k && x != 0) continue;
                        Link(i * 9 * 9 + j * 9 + k , i * 9 + j + 1);
                        Link(i * 9 * 9 + j * 9 + k , i * 9 + 81 + k);
                        Link(i * 9 * 9 + j * 9 + k , j * 9 + 81 * 2 + k);
                        Link(i * 9 * 9 + j * 9 + k , 81 * 3 + (i / 3 * 3 + j / 3) * 9 + k);
                    }
            }
        }

        Dance(0);

        if(Sum != 0) cout << Sum << endl;
        else cout << -1 << endl;

    return 0;
}