如何在没有算法X和C ++中的跳舞链接的情况下找到所有解决方案并使用回溯？ [英] How can I find all the solution and using backtracking without algorithm X and dancing link in C++?
问题描述
我刚刚设计了一个关于解决Pentominoes的程序。但是，我使用回溯算法遇到了一些问题。我正在使用Code :: Block进行调试。当我试图回溯。我发现removepuzzle功能不能正常工作。内部的for循环无法正常运行。它将跳过，并且每增加一步。此外，这个程序似乎只能找到一个解决方案。如何修改它以找到解决方案？就像5x12板的解决方案是1088.非常感谢。
我尝试了什么：
I have just designed a program about solving the Pentominoes. However, I meet some problems using the backtracking algorithm. I'm using Code::Block to debug. When I tried to backtrack. I found that the removepuzzle function not working well. The for loop inside cannot run normally. It will skip and the i increment every step. Besides, this program seems like only can found one solution. How can I modify it to found the solutions? Just like the solutions of 5x12 board is 1088. Thank you so much.
What I have tried:
struct Pentominoes
{
int row[5];
int col[5];
int used;
char puzzle;
};
Pentominoes p[63] =
{
{{0,0,0,0,0},{0,1,2,3,4},-1,'I'},
{{0,1,2,3,4},{0,0,0,0,0},-1,'I'},
{{0,1,1,1,2},{0,-1,0,1,0},-1,'X'},
{{0,0,1,2,2},{0,1,0,-1,0},-1,'Z'},
{{0,1,1,1,2},{0,0,1,2,2},-1,'Z'},
{{0,0,1,2,2},{0,1,1,1,2},-1,'Z'},
{{0,1,1,1,2},{0,-2,-1,0,-2},-1,'Z'},
{{0,1,2,2,2},{0,0,0,1,2},-1,'V'},
{{0,0,0,1,2},{0,1,2,0,0},-1,'V'},
{{0,1,2,2,2},{0,0,-2,-1,0},-1,'V'},
{{0,0,0,1,2},{0,1,2,2,2},-1,'V'},
{{0,0,0,1,2},{0,1,2,1,1},-1,'T'},
{{0,1,1,1,2},{0,-1,-1,0,0},-1,'T'},
{{0,1,2,2,2},{0,0,-1,0,1},-1,'T'},
{{0,1,1,1,2},{0,0,1,2,0},-1,'T'},
{{0,1,1,2,2},{0,0,1,1,2},-1,'W'},
{{0,1,1,2,2},{0,-1,0,-2,-1},-1,'W'},
{{0,0,1,1,2},{0,1,1,2,2},-1,'W'},
{{0,0,1,1,2},{0,1,-1,0,-1},-1,'W'},
{{0,0,0,1,1},{0,1,2,0,2},-1,'U'},
{{0,0,1,2,2},{0,1,1,0,1},-1,'U'},
{{0,0,1,1,1},{0,2,0,1,2},-1,'U'},
{{0,0,1,2,2},{0,1,0,0,1},-1,'U'},
{{0,1,1,1,1},{0,0,1,2,3},-1,'L'},
{{0,1,2,3,3},{0,0,0,-1,0},-1,'L'},
{{0,0,0,0,1},{0,1,2,3,3},-1,'L'},
{{0,0,1,2,3},{0,1,0,0,0},-1,'L'},
{{0,0,1,2,3},{0,1,1,1,1},-1,'L'},
{{0,0,0,0,1},{0,1,2,3,0},-1,'L'},
{{0,1,2,3,3},{0,0,0,0,1},-1,'L'},
{{0,1,1,1,1},{0,-3,-2,-1,0},-1,'L'},
{{0,0,1,1,1},{0,1,-2,-1,0},-1,'N'},
{{0,1,1,2,3},{0,0,1,1,1},-1,'N'},
{{0,0,0,1,1},{0,1,2,-1,0},-1,'N'},
{{0,1,2,2,3},{0,0,0,1,1},-1,'N'},
{{0,0,1,1,1},{0,1,1,2,3},-1,'N'},
{{0,1,2,2,3},{0,0,-1,0,-1},-1,'N'},
{{0,0,0,1,1},{0,1,2,2,3},-1,'N'},
{{0,1,1,2,3},{0,-1,0,-1,-1},-1,'N'},
{{0,1,1,1,1},{0,-2,-1,0,1},-1,'Y'},
{{0,1,1,2,3},{0,-1,0,0,0},-1,'Y'},
{{0,0,0,0,1},{0,1,2,3,1},-1,'Y'},
{{0,1,2,2,3},{0,0,0,1,0},-1,'Y'},
{{0,0,0,0,1},{0,1,2,3,2},-1,'Y'},
{{0,1,1,2,3},{0,0,1,0,0},-1,'Y'},
{{0,1,1,1,1},{0,-1,0,1,2},-1,'Y'},
{{0,1,2,2,3},{0,0,-1,0,0},-1,'Y'},
{{0,1,1,1,2},{0,-1,0,1,1},-1,'F'},
{{0,0,1,1,2},{0,1,-1,0,0},-1,'F'},
{{0,1,1,1,2},{0,0,1,2,1},-1,'F'},
{{0,1,1,2,2},{0,0,1,-1,0},-1,'F'},
{{0,1,1,1,2},{0,-2,-1,0,-1},-1,'F'},
{{0,0,1,1,2},{0,1,1,2,1},-1,'F'},
{{0,1,1,1,2},{0,-1,0,1,-1},-1,'F'},
{{0,1,1,2,2},{0,-1,0,0,1},-1,'F'},
{{0,0,1,1,2},{0,1,0,1,1},-1,'P'},
{{0,0,0,1,1},{0,1,2,0,1},-1,'P'},
{{0,1,1,2,2},{0,0,1,0,1},-1,'P'},
{{0,0,1,1,1},{0,1,-1,0,1},-1,'P'},
{{0,0,1,1,1},{0,1,0,1,2},-1,'P'},
{{0,1,1,2,2},{0,-1,0,-1,0},-1,'P'},
{{0,0,0,1,1},{0,1,2,1,2},-1,'P'},
{{0,0,1,1,2},{0,1,0,1,0},-1,'P'}
};
char usedChar[12] = {'\0'};
class Box
{
public:
char **board;
int row = 0;
int col = 0;
int solCount = 0;
char c[12];
int r_size = 0;
int c_size = 0;
int r_temp = 0;
int c_temp = 0;
Box(int r, int c)
{
// complete your constructor
r_size = r;
c_size = c;
board = new char*[r];
for(int i=0; i<r; i++)
board[i] = new char[c];
for(int i=0; i<r; i++)
for(int j=0; j<c; j++)
board[i][j] = '\0';
}
/*
* Print the result F (first solution), L (last solution) and N (number of solutions)
* as required in the output format. If there is no solution, print 'nil' to replace
* the solution string.
*
* The function is called from main() when a puzzle is solved.
*
*/
void output() const
{
/*for(int i=0; i<r_size; i++) {
for(int j=0; j<c_size; j++) {
cout << board[i][j];
}
cout << endl;
}*/
// dummy output
cout << "F " << "L " << "N " << solCount;
}
};
bool checkUnusedChar(Pentominoes p)
{
for(int i=0; i<12; i++)
{
if(p.puzzle == usedChar[i]) {
return false;
}
}
return true;
}
void updateRC(Box &box) {
bool empty = false;
for(int i=0; i<box.r_size; i++) {
for(int j=0; j<box.c_size; j++) {
if(box.board[i][j] == '\0') {
box.row = i;
box.col = j;
empty = true;
break;
}
}
if(empty)
break;
}
}
void placePuzzle(Pentominoes p, Box& box)
{
int r;
int c;
for (int i=0; i<5; i++) {
r = box.row + p.row[i];
c = box.col + p.col[i];
box.board[r][c] = p.puzzle;
}
}
void removepuzzle(Pentominoes p, Box box) {
int r = box.r_size;
int c = box.c_size;
int i=0;
int j=0;
for(i=0; i<r; i++) {
for(j=0; j<c; j++) {
if(box.board[i][j] == p.puzzle)
box.board[i][j] == '\0';
}
}
/*for (int i=0; i<5; i++) {
r = box.row + p.row[i];
c = box.col + p.col[i];
box.board[r][c] = '\0';
}*/
}
bool canPut(Pentominoes p, Box box) {
int r;
int c;
for (int i=0; i<5; i++) {
r = box.row + p.row[i];
c = box.col + p.col[i];
if(r < 0 || r >= box.r_size || c < 0 || c >= box.c_size || box.board[r][c] != '\0')
return false;
}
return true;
}
/*
* Find all solutions having the 12 pentominoes touching the edges of the rectangle
* box using backtracking algorithm. The first argument 'count' is used to track the
* progress of your backtracking algorithm. Its actual use depends on how you model
* the problem.
*/
void solve(int count, Box& box)
{
if (count == 12)
{
box.solCount++;
return;
}
for(int i=0; i<63; i++)
{
if(checkUnusedChar(p[i]) && canPut(p[i], box))
{
//box.r_temp = box.row;
//box.c_temp = box.col;
usedChar[count++] = p[i].puzzle;
placePuzzle(p[i], box);
//cout << p[i].puzzle << box.row << box.col << "\t";
for(int a=0; a<box.r_size; a++) {
for(int b=0; b<box.c_size; b++) {
cout << box.board[a][b];
}
cout << endl;
}
cout << endl;
updateRC(box);
solve(count, box);
count--;
usedChar[count] = '\0';
//box.row = box.r_temp;
//box.col = box.c_temp;
removepuzzle(p[i], box);
}
}
}
/*
* Driver program to test above functions against default test cases.
* Input filename must be provided by command-line argument.
*
* **** DON'T modify this main function. ****
*/
int main(int argc, char** argv)
{
//ifstream fin(argv[1]);
ifstream fin("a2_input.txt");
if (!fin)
{
cout << "Input file not found.";
exit(1);
}
int testcase = 0;
fin >> testcase;
for (int t = 0; t < testcase; t++)
{
int row, col;
fin >> row >> col;
// run and measure
clock_t start = clock();
// create a box with specific dimension
Box* box = new Box(row, col);
solve(0, *box);
// output result F, L and N
box->output();
clock_t end = clock();
int time = (end - start) * 1000.0 / CLOCKS_PER_SEC;
// output result T and S
printf(" %d %d\n", time, SID);
// clean memory for every test case
delete box;
}
return 0;
}推荐答案
The error is here:
The error is here:
void removepuzzle(Pentominoes p, Box box)
You are passing the Box parameter by value so that changings are applied to the local copy and not the source object.
The solution is to pass it by reference or pointer (as done with the other functions that modify it):
You are passing the Box parameter by value so that changings are applied to the local copy and not the source object.
The solution is to pass it by reference or pointer (as done with the other functions that modify it):
void removepuzzle(const Pentominoes &p, Box &box)
Note that I have also passed Pentominoes by reference to avoid copying the array and used const to indicate that it is not modified.
There is another error here in the solve() function:
Note that I have also passed Pentominoes by reference to avoid copying the array and used const to indicate that it is not modified.
There is another error here in the solve() function:
count--;
usedChar[count] = '\0';
This will result in an out of bound access (you are calling solve() from main() with count = 0).
There should be a check if count becomes negative.
However, I would expect that count must be incremented instead of decremented and breaking when it becomes 12.
[/EDIT]
This will result in an out of bound access (you are calling solve() from main() with count = 0).
There should be a check if count becomes negative.
However, I would expect that count must be incremented instead of decremented and breaking when it becomes 12.
[/EDIT]
这篇关于如何在没有算法X和C ++中的跳舞链接的情况下找到所有解决方案并使用回溯？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
