目录黑白6*68*8二进制数独8*810*1014*14黑白plus6*68*810*1014*1420*2024*24计算机求解30*3030*40黑白在线play有一些格子一开始就有黑色或白色的圆点而其他格子是空的。 胜利的条件是按照如下规则用黑白圆形填满棋盘:1. 每行每列中黑子数量等于白子数量。2. 不能有超过两个相同颜色的圆形连在一起。3. 没有完全相同的两行或两列。6*68*8另一个不利用规则三就只能推到这一步利用规则三再继续往下推可以得到唯一解二进制数独规则和黑白的规则差不多但是没有“ 没有完全相同的两行或两列”这一条限制。8*810*1014*14黑白plus规则在二进制数独的基础上添加了和×表示相邻两格一样或者不一样。6*68*810*1014*1420*2024*24计算机求解思路一转化成覆盖问题好处就是用X算法求解效率很高坏处就是代码比较复杂思路二用普通的搜索算法#include iostream #include string_view #include string #include string.h #include vector #include time.h #include functional #include algorithm #include queue #include numeric #include map #include set #include unordered_map #include unordered_set #include stack #include array #include math.h #include fstream #include streambuf #include stdio.h #include mutex #include iomanip #include cmath #include limits #include climits #include stdint.h #include windows.h #include thread using namespace std; const int UNKNOWN -1; const int WHITE 0; const int BLACK 1; int R, C; vectorvectorint a; // 棋盘 vectorvectorbool given; // true 输入给定false 推理得出 vectorvectorint eqAdj; // 相等约束的邻接表存格子编号 vectorvectorint neqAdj; // 不等约束的邻接表 int id(int r, int c) { return r * C c; } vectorint getLine(int idx, bool isRow) { int L isRow ? C : R; vectorint line(L); for (int k 0; k L; k) line[k] isRow ? a[idx][k] : a[k][idx]; return line; } void setLine(int idx, bool isRow, const vectorint line) { int L isRow ? C : R; for (int k 0; k L; k) { if (isRow) a[idx][k] line[k]; else a[k][idx] line[k]; } } int countUnknown(const vectorint line) { int c 0; for (int x : line) if (x UNKNOWN) c; return c; } bool enforceLine(vectorint line) { int L (int)line.size(); bool changed true; while (changed) { changed false; // 1. 黑白数量各占一半 int cnt[2] { 0, 0 }; vectorint unk; for (int i 0; i L; i) { if (line[i] UNKNOWN) unk.push_back(i); else cnt[line[i]]; } if (cnt[WHITE] L / 2 || cnt[BLACK] L / 2) return false; if (cnt[WHITE] L / 2) { for (int p : unk) if (line[p] UNKNOWN) { line[p] BLACK; changed true; } } else if (cnt[BLACK] L / 2) { for (int p : unk) if (line[p] UNKNOWN) { line[p] WHITE; changed true; } } // 2. 无连续 3 个同色 for (int i 0; i L; i) { if (line[i] UNKNOWN) continue; if (i 1 L line[i 1] line[i]) { if (i - 1 0) { if (line[i - 1] line[i]) return false; if (line[i - 1] UNKNOWN) { line[i - 1] 1 - line[i]; changed true; } } if (i 2 L) { if (line[i 2] line[i]) return false; if (line[i 2] UNKNOWN) { line[i 2] 1 - line[i]; changed true; } } } if (i 2 L line[i 2] line[i]) { if (line[i 1] line[i]) return false; if (line[i 1] UNKNOWN) { line[i 1] 1 - line[i]; changed true; } } } } return true; } // 传播相等/不等约束。返回 1有变化0无变化-1矛盾 int applyPairs() { int changed 0; for (int v 0; v R * C; v) { int r v / C, c v % C; if (a[r][c] UNKNOWN) continue; // 相等另一格必须同色 for (int t : eqAdj[v]) { int tr t / C, tc t % C; if (a[tr][tc] UNKNOWN) { a[tr][tc] a[r][c]; changed 1; } else if (a[tr][tc] ! a[r][c]) return -1; } // 不等另一格必须异色 for (int t : neqAdj[v]) { int tr t / C, tc t % C; if (a[tr][tc] UNKNOWN) { a[tr][tc] 1 - a[r][c]; changed 1; } else if (a[tr][tc] a[r][c]) return -1; } } return changed; } bool propagate() { bool changed true; while (changed) { changed false; int pr applyPairs(); if (pr -1) return false; if (pr 1) changed true; for (int i 0; i R; i) { auto line getLine(i, true); int before countUnknown(line); if (!enforceLine(line)) return false; if (countUnknown(line) ! before) { setLine(i, true, line); changed true; } } for (int j 0; j C; j) { auto line getLine(j, false); int before countUnknown(line); if (!enforceLine(line)) return false; if (countUnknown(line) ! before) { setLine(j, false, line); changed true; } } } return true; } bool isComplete() { for (int i 0; i R; i) for (int j 0; j C; j) if (a[i][j] UNKNOWN) return false; return true; } // 检查 (i,j) 填 color 是否直接违反某条约束 bool pairOK(int i, int j, int color) { int v id(i, j); for (int t : eqAdj[v]) { int tr t / C, tc t % C; if (a[tr][tc] ! UNKNOWN a[tr][tc] ! color) return false; } for (int t : neqAdj[v]) { int tr t / C, tc t % C; if (a[tr][tc] ! UNKNOWN a[tr][tc] color) return false; } return true; } bool canBe(int i, int j, int color) { a[i][j] color; bool ok pairOK(i, j, color); // 行约束 int cnt[2] { 0, 0 }; for (int k 0; k C; k) if (a[i][k] ! UNKNOWN) cnt[a[i][k]]; ok ok cnt[WHITE] C / 2 cnt[BLACK] C / 2; for (int k 0; k 2 C ok; k) if (a[i][k] ! UNKNOWN a[i][k] a[i][k 1] a[i][k] a[i][k 2]) ok false; // 列约束 if (ok) { cnt[0] cnt[1] 0; for (int k 0; k R; k) if (a[k][j] ! UNKNOWN) cnt[a[k][j]]; ok cnt[WHITE] R / 2 cnt[BLACK] R / 2; for (int k 0; k 2 R ok; k) if (a[k][j] ! UNKNOWN a[k][j] a[k 1][j] a[k][j] a[k 2][j]) ok false; } a[i][j] UNKNOWN; return ok; } bool dfs() { if (!propagate()) return false; if (isComplete()) return true; // MRV选合法颜色最少的空格 int bi -1, bj -1, best 3; for (int i 0; i R; i) { for (int j 0; j C; j) { if (a[i][j] ! UNKNOWN) continue; int legal 0; if (canBe(i, j, WHITE)) legal; if (canBe(i, j, BLACK)) legal; if (legal 0) return false; if (legal best) { best legal; bi i; bj j; } if (best 1) break; } if (best 1) break; } auto backup a; for (int c : {WHITE, BLACK}) { a backup; if (!canBe(bi, bj, c)) continue; a[bi][bj] c; if (dfs()) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); if (!(cin R C)) return 0; a.assign(R, vectorint(C, UNKNOWN)); given.assign(R, vectorbool(C, false)); eqAdj.assign(R * C, {}); neqAdj.assign(R * C, {}); string s; bool allUnknown true; for (int i 0; i R; i) { cin s; for (int j 0; j C; j) { char ch s[j]; if (ch 0 || ch W || ch w) a[i][j] WHITE; else if (ch 1 || ch B || ch b) a[i][j] BLACK; else a[i][j] UNKNOWN; if (a[i][j] ! UNKNOWN) { given[i][j] true; allUnknown false; } } } // 读取限制先 E 条相等再 U 条不等 int E 0, U 0; if (cin E U) { for (int k 0; k E; k) { int r1, c1, r2, c2; cin r1 c1 r2 c2; eqAdj[id(r1, c1)].push_back(id(r2, c2)); eqAdj[id(r2, c2)].push_back(id(r1, c1)); } for (int k 0; k U; k) { int r1, c1, r2, c2; cin r1 c1 r2 c2; neqAdj[id(r1, c1)].push_back(id(r2, c2)); neqAdj[id(r2, c2)].push_back(id(r1, c1)); } } // 空棋盘且无限制直接用棋盘染色 if (allUnknown E 0 U 0) { for (int i 0; i R; i) { for (int j 0; j C; j) cout (((i j) 1) ? b : w); cout \n; } return 0; } if (!dfs()) { cout No solution\n; return 0; } // 输出数字 输入给定字母 推理得出 for (int i 0; i R; i) { for (int j 0; j C; j) { if (given[i][j]) cout (a[i][j] BLACK ? 1 : 0); else cout (a[i][j] BLACK ? b : w); } cout \n; } return 0; }以上面14*14的关卡为例输入14141..10110100100110011001010010011001101101001001101010110..0.1010100101..1.001001101..1..010101001..0..101010110.01..0101101010.0....01010101110..010100110.1.0..01011001.0...100..001.0....01100110.0 111 4 12 4输出其中w是求解出来的白子b是求解出来的黑子30*30输入30 30.01101..0..010101010..010010...1010...0101010101010101..011010101010101010101010101010100101010101100101010101010100110110101010010110..1010...01100101.0101010.100..10101.0100101010.10101010101.0..0101101101010.101010101010110.1010101010101101001001100110110101010011010.10.10.100110.1001010101100101001..1.01..01010101010100.101..10100101..101010011011001.01.1010..010.1..010110...0110010.0101..1.01010101.01010..10110.0.1001..10011010.1010.100100101.0110011010010010.101010101011010011001.010110..01..0101010010110010101010011010..1010101101001011010101100101010..1010010110100101001100110101100101001.01.0101011001100101.0101101.0101010101001.0101010.101001..10101010..010.10101010.....0.101010101.0110...0..101010.1..010101010..101010110010101.0.01100101010101010.101...0100111001.0101010..101100110.10.100.1001101010..10...0100110.101..011...010.100.1.0110010.101...10..01.10..1...0.00110...01.11 622 25 22 264 14 5 1410 3 10 428 0 29 00 24 1 2412 29 13 2925 22 25 23输出无解不知道是到这一步已经推理错了还是输入有问题毕竟900个格子有一个写错太正常了。30*40