UVa 10265 Toroidal Chess Queens‘ Problem

题目描述

本题要求在一个特殊的 $M\times N$ 棋盘上放置 $K$ 个皇后，使得它们互不攻击。棋盘的特殊之处在于它是一个环面（$\text{Toroidal}$）棋盘，即通过将普通 $M\times N$ 棋盘的上边界与下边界粘合、左边界与右边界粘合而形成的一个环面结构（类似甜甜圈的形状）。

环面棋盘的特点

• 从最左列向左移动会到达最右列
• 从最右列向右移动会到达最左列
• 从最上行向上移动会到达最下行
• 从最下行向下移动会到达最上行

皇后的移动规则

皇后在环面棋盘上的移动方式与普通棋盘相同：可以攻击同一行、同一列或同一对角线上的任何棋子。

输入输出

• 输入：多组测试数据，每组包含三个整数 $M$ , $N$ , $K$ （$1\le M,N,K\le 14$），分别表示棋盘列数、行数和要放置的皇后数。
• 输出：对于每组数据，输出一种放置方案，每个皇后位置占一行，格式为“列 行”（从 $1$ 开始编号）。若无解，输出一行“$00$”。若有多解，输出任意一个即可。

题目分析

问题本质

这是一个典型的约束满足问题（$\text{CSP}$） ，需要在满足特定约束条件下放置指定数量的皇后。与经典的 $N$ 皇后问题相比，本题有两个主要区别：

关键约束条件

对于环面棋盘，皇后之间的冲突条件如下：

环面对角线的定义

在环面棋盘上，两点 $(r_1,c_1)$ 和 $(r_2,c_2)$ 在同一对角线当且仅当存在整数 $t$ 满足以下条件之一：

• 主对角线：$r_2\equiv r_1+t(\mathrm{mod}N)$ 且 $c_2\equiv c_1+t(\mathrm{mod}M)$
• 副对角线：$r_2\equiv r_1+t(\mathrm{mod}N)$ 且 $c_2\equiv c_1-t(\mathrm{mod}M)$

重要性质

最大皇后数：在 $M\times N$ 环面棋盘上，最多只能放置 $\min (M,N)$ 个互不攻击的皇后。

证明：

这一性质提供了重要的剪枝条件：当 $K>\min (M,N)$ 时，直接判定无解。

解题思路

1. 总体策略

由于数据范围较小（$M,N,K\le 14$），可以使用深度优先搜索（$\text{DFS}$） 配合回溯法求解。但普通的回溯搜索会超时，需要加入以下优化：

2. 优化策略

(1) 预计算对角线冲突关系

由于每次检查对角线冲突的计算成本较高，且 $M,N\le 14$（棋盘最多 $14\times 14=196$ 个格子），我们可以预计算所有位置之间的对角线冲突关系，并用位掩码表示。

• 对于每个位置 $(r,c)$，计算一个 $196$ 位的掩码，其中第 $i$ 位为 $1$ 表示位置 $i$ 与 $(r,c)$ 在对角线上冲突。
• 由于 $196$ 位超过 $64$ 位，需要用两个 unsigned long long 存储（每个 $64$ 位）。

(2) 位运算加速

• 使用位掩码表示已放置皇后的位置、已占用的列等。
• 通过位运算快速判断位置是否可用。

(3) 搜索顺序优化

• 按行搜索：每次在一行中尝试放置皇后，然后进入下一行。
• 剪枝：如果剩余行数小于还需要放置的皇后数，则回溯。

(4) 对称性利用

• 由于环面对称性，如果 $(M,N,K)$ 无解，则 $(N,M,K)$ 也无解。
• 但在实现中，我们主要依赖预计算和位运算优化。

3. 算法步骤

时间复杂度分析

最坏情况

• 预计算：$O((MN{)}^2)\approx O(196^2)\approx 38,416$ 次操作，可接受。
• 搜索：由于强剪枝和位运算优化，实际搜索空间远小于 $2^{MN}$。
• 每组测试数据都能在时限内完成。

空间复杂度

• 存储预计算掩码：$O(MN\times MN/64)\approx 196\times 4=784$ 个 unsigned long long。
• 搜索栈深度：$O(N)\le 14$。

代码实现

// Toroidal Chess Queens' Problem
// UVa ID: 10265
// Verdict: Accepted
// Submission Date: 2026-01-19
// UVa Run Time: 0.070s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

int M, N, K; // M列，N行
vector<pair<int, int>> solution;
bool found;

// 预计算：maskDiag[row][col] 表示与(row,col)冲突的所有位置掩码
vector<vector<unsigned long long>> diagMask1, diagMask2; // 每个位置的对角线冲突掩码

// 初始化对角线冲突掩码
void initDiagMasks() {
diagMask1.assign(N, vector<unsigned long long>(M, 0));
diagMask2.assign(N, vector<unsigned long long>(M, 0));
for (int r1 = 0; r1 < N; r1++) {
for (int c1 = 0; c1 < M; c1++) {
unsigned long long mask1 = 0, mask2 = 0;
// 检查所有其他位置
for (int r2 = 0; r2 < N; r2++) {
for (int c2 = 0; c2 < M; c2++) {
if (r1 == r2 && c1 == c2) continue;
int dr = (r2 – r1 + N) % N;
bool conflict = false;
// 快速对角线检查
for (int k = 0; k < M && !conflict; k++) {
int t = dr + k * N;
if ((c1 + t) % M == c2 || (c1 – t + M * N) % M == c2) {
conflict = true;
}
}
if (conflict) {
int idx = r2 * M + c2;
if (idx < 64) mask1 |= (1ULL << idx);
else mask2 |= (1ULL << (idx – 64));
}
}
}
diagMask1[r1][c1] = mask1;
diagMask2[r1][c1] = mask2;
}
}
}

// 快速冲突检查（使用预计算的掩码）
bool canPlaceFast(int r, int c, unsigned long long used1, unsigned long long used2) {
// 检查对角线冲突
if ((used1 & diagMask1[r][c]) || (used2 & diagMask2[r][c])) return false;
return true;
}

// 搜索函数
void dfs(int row, int placed, unsigned long long used1, unsigned long long used2,
int colMask, vector<pair<int, int>>& queens) {
if (found) return;
if (placed == K) {
solution = queens;
found = true;
return;
}
if (row >= N) return;
if (N – row < K – placed) return; // 剩余行数不足
// 生成当前行可放置的列
for (int c = 0; c < M; c++) {
if (colMask & (1 << c)) continue; // 列已被占用
// 快速对角线检查
if (!canPlaceFast(row, c, used1, used2)) continue;
// 放置皇后
queens.push_back({row, c});
int idx = row * M + c;
unsigned long long newUsed1 = used1;
unsigned long long newUsed2 = used2;
if (idx < 64) newUsed1 |= (1ULL << idx);
else newUsed2 |= (1ULL << (idx – 64));
dfs(row + 1, placed + 1, newUsed1, newUsed2, colMask | (1 << c), queens);
queens.pop_back();
if (found) return;
}
// 不放皇后
dfs(row + 1, placed, used1, used2, colMask, queens);
}

int main() {
while (cin >> M >> N >> K) {
if (K > min(M, N)) {
cout << "0 0\\n";
continue;
}
// 初始化对角线掩码
initDiagMasks();
solution.clear();
found = false;
vector<pair<int, int>> queens;
dfs(0, 0, 0ULL, 0ULL, 0, queens);
if (found) {
for (auto& p : solution) {
cout << p.second + 1 << " " << p.first + 1 << "\\n";
}
} else cout << "0 0\\n";
}
return 0;
}

总结

本题的核心难点在于环面对角线的判断。通过预计算所有位置之间的对角线冲突关系，并使用位运算加速，我们可以在合理的时间内求解 $14\times 14$ 规模的问题。关键的优化点包括：

这种“预计算+位运算+深度优先搜索”的组合策略，对于小规模约束满足问题是十分有效的，可以在竞赛中应对类似的题目。