Futoshiki is a board-based puzzle game, also known under the name Unequal. It is playable on a square board having a given fixed size (4×4 for example).
The purpose of the game is to discover the digits hidden inside the board’s cells; each cell is filled with a digit between 1 and the board’s size. On each row and column each digit appears exactly once; therefore, when revealed, the digits of the board form a so-called Latin square.
At the beginning of the game some digits might be revealed. The board might also contain some inequalities between the board cells; these inequalities must be respected and can be used as clues in order to discover the remaining hidden digits.
Each puzzle is guaranteed to have a solution and only one. You can play this game online: http://www.futoshiki.org/.
Please solve the above Futoshiki puzzle ( Figure 1 ) with forward checking algorithm.
下为运行代码。值得一提的是，这里表示可行域使用了位集bitset，从而把剪枝操作等都转化成了位运算，极大地提升了运行效率，最终运行时间仅有 0.019s。
#include <bits/stdc++.h>
using namespace std;
const int N = 9;
array<vector<int>, N * N> notEqual, greaterThan, lessThan;
array<int, N * N> ans;
bool fc(array<bitset<N>, N * N> &v, int pos) //对状态v进行前向检测剪枝
{
int mi = v[pos]._Find_first(), ma = mi;
for (int j = mi, jnex, je = v[pos].size(); j < je; j = jnex)
if ((jnex = v[pos]._Find_next(j)) >= je)
ma = j;
if (mi == ma)
for (int j : notEqual[pos])
{
v[j].reset(mi);
if (v[j].none())
return 0;
}
for (int j : lessThan[pos])
{
v[j] &= (1 << ma) - 1;
if (v[j].none())
return 0;
}
for (int j : greaterThan[pos])
{
v[j] &= -1 << mi + 1;
if (v[j].none())
return 0;
}
return 1;
}
bool dfs(const array<bitset<N>, N * N> &v)
{
int pick = v.size();
for (int i = 0, now, save = v.size(); i < v.size(); ++i)
if (!ans[i] && save > (now = v[i].count())) //MRV
if (pick = i, (save = now) == 1) //这里可以提前退出
break;
if (pick == v.size()) //没有选出点，说明找到答案
return 1;
for (int i = v[pick]._Find_first(); i < v[pick].size(); i = v[pick]._Find_next(i)) //遍历当前考虑的下标pick，他的可行值域{i}
{
auto tv = v;
tv[pick] = 1 << i;
ans[pick] = i + 1;
if (fc(tv, pick) && dfs(tv))
return 1;
}
return ans[pick] = 0;
}
int main()
{
array<bitset<N>, N * N> v; //使用bitset记录状态，方便判重
for (int i = 0, t; i < N; ++i)
for (int j = 0; j < N; ++j)
{
scanf("%d", &t);
v[i * N + j] = t ? 1 << t - 1 : (1 << N) - 1; //0代表所有状态都可行，因此将原值翻转
for (int k = 0; k < N; ++k)
{
if (k != i)
notEqual[i * N + j].push_back(k * N + j);
if (k != j)
notEqual[i * N + j].push_back(i * N + k);
}
}
for (int x1, x2, y1, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2) != EOF;)
{
greaterThan[y1 += N * x1].push_back(y2 += N * x2);
lessThan[y2].push_back(y1);
}
for (int k = 0; k < 4; ++k) //进行多次预剪枝，大幅减小搜索空间
for (int i = 0; i < v.size(); ++i)
fc(v, i);
if (dfs(v))
for (int i = 0; i < ans.size(); ++i)
printf("%d%c", ans[i], i % N < N - 1 ? ' ' : '\n');
else
printf("No solution exists.");
}
下为输入数据。
0 0 0 7 3 8 0 5 0
0 0 7 0 0 2 0 0 0
0 0 0 0 0 9 0 0 0
0 0 0 4 0 0 0 0 0
0 0 1 0 0 0 6 4 0
0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 6
0 0 0 1
0 3 0 2
1 3 1 4
1 6 1 7
2 6 1 6
2 1 2 0
2 2 2 3
2 3 3 3
4 1 3 1
3 3 3 2
3 5 3 4
3 5 3 6
4 5 3 5
3 8 3 7
4 0 4 1
5 4 4 4
5 8 4 8
5 1 5 2
5 1 6 1
5 4 5 5
5 7 5 6
6 6 5 6
6 8 5 8
6 3 6 4
7 7 6 7
7 1 8 1
8 2 7 2
7 5 8 5
8 8 7 8
8 5 8 6
$ g++ futoshiki.cpp -o futoshiki.out -O3
futoshiki.cpp: In function ‘int main()’:
futoshiki.cpp:58:9: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
$ time ./futoshiki.out < futoshiki.txt
1 6 9 7 3 8 4 5 2
4 1 7 5 6 2 8 9 3
8 7 2 3 1 9 5 6 4
3 9 6 4 8 5 7 2 1
2 5 1 9 7 3 6 4 8
9 3 4 8 5 6 2 1 7
6 4 3 2 9 7 1 8 5
5 2 8 6 4 1 3 7 9
7 8 5 1 2 4 9 3 6
real 0m0.019s
user 0m0.016s
sys 0m0.000s