Click here to Skip to main content
15,896,259 members
Search within:


How can I find all the solution and using backtracking without algorithm X and dancing link in C++?
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
C++
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:

C++
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;
}
Posted
Updated 17-Nov-16 22:26pm
Add a Solution

1 solution

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):
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.

[EDIT]
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]
 
Share this answer
 
Posted
Updated 17-Nov-16 23:36pm
v2
Comments
Member 12851235 18-Nov-16 4:58am    
Thank you for your answer. I tried to change the function argument. However, the puzzle still cannot remove in the board. I trace the program until the 'U' is placed. No more puzzle can fit and place in the board and so it will backtrack to remove the 'U' placed in the board. usedChar[i] = 'U' is removed and the count is decremented. Since the 'U' in the board cannot remove, the new 'U' placed in the board again and there are double 'U' puzzle placed. I am very confused whether my concept in this program is wrong. Thank you very much.
Jochen Arndt 18-Nov-16 5:31am    
To be honest, I did not checked your algorithm and what is going on in your code. That would require too much time.

I just recognised that passing the box by value is an obvious error that prevents the code from doing what is expected.

The usual method to solve such algorithm problems is debugging. Step through the code an compare the current state with the expected values.

In your case it might help to dump the box content to the screen like done already. But then you should handle the null byte (e.g. by printing a space).

There is one more error I found:
You are decrementing count in the solve() function. When count is zero before, you will have an out of bounds access at
usedChar[count] = '\0';
Shouldn't count be incremented here?
And there should be an exit condition when count reaches a limit.
I will update my solution.
Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month

Advertise
Privacy
Cookies
Terms of Use
Last Updated 18 Nov 2016
Layout: fixed | fluid
Copyright © CodeProject, 1999-2024
All Rights Reserved.

Web03 2.8:2024-04-02:1

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900