编程练习回溯溶液（配件管道） [英] Backtracking solution for programming exercise (fitting pipes)
问题描述
我是从一个本地程序设计大赛审阅规划问题。
您也可以下载问题这里（PDF）。这是在荷兰，但图片将有助于理解它。
您接收AM * m的网格，输入一些管道和缺少一些点（在questionmarks）。 其余的管道必须被放置在网格，以便它们与其他人联系。
每个管道重新psented上书$ P $（见图片2页）。字母A的值为1，'B'的值为2，..
我试着用回溯解决它（这完全不是那么回事还）。但由于网格可以10X10这将是太慢了。 有人建议可以更好（快）解决方案/办法？
的#include＆LT;的iostream＆GT;
＃包括＆LT; stdio.h中＆GT;
＃包括＆LT;载体＆GT;
使用名字空间std;
的#define SZ（一）INT（（一）.size（））
＃定义PB的push_back
INT男，找到;
包含字母;
矢量＆lt; int的＆GT;完成;
矢量＆lt;串GT;一个;
INT OK（字符信，诠释三，INT读）
{
INT VAL =字母 - 'A'+ 1;
//检查，如果无副作用，去外面
如果（R == 0＆安培;及（VAL＆安培; 1））
返回0;
如果（R ==米 - 1和;及（VAL和4））
返回0;
如果（C == 0安培;及（VAL和8））
返回0;
如果（三==米 - 1和;及（VAL和2））
返回0;
//检查侧连接其他管道上的网格
如果（R大于0＆安培;＆安培;一个[R - 1] [C] =＆安培！'？';及（一个[R - 1] [C]＆安培;！4）及及（VAL＆安培; 1））
返回0;
如果（c取代; 0＆安培;＆安培;一个[R]并[c - 1] =＆安培！'？';＆安培;！（一个[R]并[c - 1]和2）及及（VAL＆安培; 8））
返回0;
如果（为r！ - '？'！米1和;;＆安培一个[R + 1] [C] =＆安培;及（一个[R + 1] [C]＆安培; 1）及及（ VAL和4））
返回0;
如果（℃下！ - '？'！米1和;;＆安培一个[R] [C + 1] =＆安培;及（一个[R]并[c + 1]安培; 8）及及（ VAL和2））
返回0;
返回1;
}
解决无效（INT num_placed，INT POS）
{
如果（发现）的回报;
//完成
如果（num_placed == SZ（字母））{
的for（int i = 0; I＆LT;米; ++ I）
COUT＆LT;＆LT;一[1] - ;＆其中; ENDL;
发现= 1;
返回;
}
INT C = POS％米;
INT R = POS /平方米;
如果（A [R] [C]！='？'）
解决（num_placed，POS + 1）;
//尝试在这个位置上的所有管道
的for（int i = 0; I＆LT; SZ（字母）; ++ I）{
如果（做[1] - 安培;！＆安培; OK（字母[我]，C，R））{
A [R] [C] =字母[I]
完成[I] = 1;
解决（num_placed + 1，POS + 1）;
完成[I] = 0;
一个[R] [C] ='？';
}
}
}
诠释的main（）
{
freopen函数（input.txt的，R，标准输入）;
INT N;
CIN＆GT;＆GT; N;
而（N--）{
CIN＆GT;＆GT;米;
CIN＆GT;＆GT;信;
COUT＆LT;＆LT; M＆LT;＆LT; ENDL;
a.clear（）;
的for（int i = 0; I＆LT;米; ++ I）{
串线;
CIN＆GT;＆GT;线;
a.pb（线）;
}
做=矢量＆lt; INT＆GT;（SZ（字母），0）;
发现= 0;
解决（0，0）;
}
返回0;
}
原答复
你必须写所有的C自己的$ C $或您有兴趣探索其他的工具？因为我会建议看约束传播/线性规划。你已经有很多的边界约束 - 的外边缘不能有管道，再加上内边缘 - 所以我想这会工作得非常有效。同时，约束看起来像他们将是简单的等式，所以它应该是pretty的容易成立。
我没有足够的经验，这让更多的细节在这里（不过如果我有时间在下周我可以给它一个去在某个时候），但是如果这种事情很有趣有一点背景另一个答案我写了前段时间。
PS有趣的问题;感谢张贴这一点。
更新回复（2012-04-06 - 更新了博客引用;旧的评论是越野车）
一个深度优先搜索，其中该下一个空盒中填充与每个可用，的一致的瓦，与一致性检查包括两边缘约束（无管道断边）和最近的邻居，是相当有效率。我有一个未经优化的实现Clojure中，将解决较小的例子在各地0.4ms（1000 360ms JVM预热后）和在3毫秒（塞德里克面包车goethem大报告为1ms优化 - 但仍然OO - java实现，这似乎是合理的）。它可以解决一个10x10字谜（管有没有初始提示同心圆）的12S。
我还花时间寻找一个聪明的方式，跟踪约束每一个细胞上，就像在弱势族群的纸上面。然后我尝试使用巧克力。这一切是在更详细的博客文章这里描述（我确实有一个更新的详细细节这个答案，但他们的基础上马车code - 该博客有更多，更好的信息）。源也可以下载了。
这是这一切的总的结论是，直接搜索是罚款高达10×10。在这之后，更多的智慧可以帮助，但它很难确定，因为生成测试用例是很难（它们往往是模糊的，很多细胞都给出即使）。
I'm reviewing a programming problem from a local programming contest.
You can download the problem here (pdf). It's in dutch but the pictures will help to understand it.
You receive a m*m grid as input with some pipes and some missing spots (the questionmarks). The remaining pipes have to be placed in the grid so that they connect with the others.
Each pipe is represented as a letter (see picture on page 2). The letter 'A' has value 1, 'B' has value 2, ..
I tried solving it with backtracking (it doesn't quite work yet). But since the grid can be 10x10 this will be too slow. Can someone suggest a better (faster) solution/approach?
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
int m, found;
string letters;
vector<int> done;
vector<string> a;
int ok(char letter, int c, int r)
{
int val = letter - 'A' + 1;
//checking if no side goes outside
if (r == 0 && (val & 1))
return 0;
if (r == m - 1 && (val & 4))
return 0;
if (c == 0 && (val & 8))
return 0;
if (c == m - 1 && (val & 2))
return 0;
//check if the side is connected the other pipe on the grid
if (r > 0 && a[r - 1][c] != '?' && (a[r - 1][c] & 4) && !(val & 1))
return 0;
if (c > 0 && a[r][c - 1] != '?' && (a[r][c - 1] & 2) && !(val & 8))
return 0;
if (r < m - 1 && a[r + 1][c] != '?' && (a[r + 1][c] & 1) && !(val & 4))
return 0;
if (c < m - 1 && a[r][c + 1] != '?' && (a[r][c + 1] & 8) && !(val & 2))
return 0;
return 1;
}
void solve(int num_placed, int pos)
{
if (found) return;
//done
if (num_placed == sz(letters)) {
for (int i = 0; i < m; ++i)
cout << a[i] << endl;
found = 1;
return;
}
int c = pos % m;
int r = pos / m;
if (a[r][c] != '?')
solve(num_placed, pos + 1);
//try all the pipes on this position
for (int i = 0; i < sz(letters); ++i) {
if (!done[i] && ok(letters[i], c, r)) {
a[r][c] = letters[i];
done[i] = 1;
solve(num_placed + 1, pos + 1);
done[i] = 0;
a[r][c] = '?';
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
int n;
cin >> n;
while (n--) {
cin >> m;
cin >> letters;
cout << m << endl;
a.clear();
for (int i = 0; i < m; ++i) {
string line;
cin >> line;
a.pb(line);
}
done = vector<int>(sz(letters), 0);
found = 0;
solve(0, 0);
}
return 0;
}
original reply
do you have to write all the code yourself or are you interested in exploring other tools? because i would suggest looking at constraint propagation / linear programming. you already have a lot of boundary constraints - that the outer edges cannot have pipes, plus the inner edges - so i imagine this will work quite efficiently. also, the constraints look like they will be simple equalities, so it should be pretty easy to set up.
i don't have enough experience with this to give more details here (although if i have time in the next week i may give it a go at some point), but if this kind of thing is interesting there's a bit more background in another answer i wrote some time ago.
ps interesting question; thanks for posting this.
[edit: if you cannot use other libraries then you can do the constraint propagation yourself. there's a wonderful article by norvig that shows how to do this for sudoku. i would strongly suggest reading that - i think you will see how to carry the techniques across, even though it's sudoku and python.]
updated reply (2012-04-06 - updated with blog references; old comments were buggy)
a depth-first search, where the next empty cell is filled with each available, consistent tile, and the consistency check includes both edge constraints (no pipes off the edge) and nearest neighbours, is quite efficient. i have an unoptimized implementation in clojure that will solve the smaller example in around 0.4ms (1000 in 360ms after JVM warmup) and the larger in 3ms (cedric van goethem reports 1ms for an optimised - but still OO - java implementation, which seems reasonable). it can solve a 10x10 puzzle (concentric circles of tubes with no initial hints) in 12s.
i also spent time looking at a "smart" approach, which tracks constraints on each cell, much like in norvig's paper above. and then i tried using choco. all this is described in much more detail in blog posts here (i did have more details in an update to this answer, but they were based on buggy code - the blog has more, better information). the source is also available for download.
the general conclusion from all this was that direct search is fine up to 10x10. after that, more smarts may help, but it's difficult to be sure because generating test cases is hard (they tend to be ambiguous, even when lots of cells are given).
这篇关于编程练习回溯溶液（配件管道）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
