考虑用类似 2-SAT 的处理方式来做 $c_{i,j}\in\{a_i,b_j\}$，即为若 $c_{i,j}\ne a_i$ 则一定有 $b_j=c_{i,j}$ 否则无限制。

增量地考虑所有行，每次决策一个 $a_i$，会有一个初始为全集的集合 $S$ 描述 $b_j$ 的限制，若 $j\not\in S$ 则 $b_j$ 已经确定，否则 $j\in S$ 表示 $b_j$ 在 $[1,k]$ 任取。先考虑所有 $j\not\in S$ 且 $b_j\ne c_{i,j}$ 的 $c$ 取值集合构成集合 $C$，若 $|C|>1$ 显然无解，否则：

• $|C|=1$ 时 $a_i$ 唯一确定从而可以对 $S$ 中 $c_{i,j}\ne a_i$ 的位置都限制成 $b_j=c_{i,j}$ 并从 $S$ 中删除 $j$ 最终转移到唯一的 $S'$ 上。
• $C=\varnothing$ 时 $S$ 外无限制，$S$ 中每个颜色的出现位置划分成若干不交子集，枚举 $a_i$ 是哪种取值从而转移到对应的 $S'$ 上。

对这个进行搜索，发现每一行的所有状态的 $S$ 一定是不交的，从而至多有 $m$ 个，总复杂度正确。总状态量即为 $O(nm)$ 的，进行一些预处理就可以做到总时间复杂度 $O(n^3)$。