Member 12851235 Ответов: 1

Как я могу найти все решение и использовать backtracking без алгоритма X и dancing link в C++?

Я только что разработал программу о решении Пентомино. Однако я сталкиваюсь с некоторыми проблемами, используя алгоритм обратного отслеживания. Я использую Code:: Block для отладки. Когда я попытался вернуться. Я обнаружил, что функция removepuzzle работает не очень хорошо. Цикл for внутри не может работать нормально. Он будет пропускать, и я буду увеличивать каждый шаг. Кроме того, эта программа, похоже, может найти только одно решение. Как я могу изменить его, чтобы найти решения? Точно так же, как решения платы 5х12-это 1088. Огромное спасибо.

Что я уже пробовал:

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;
}

1 Ответов

Рейтинг:
2

Jochen Arndt

Ошибка здесь:

void removepuzzle(Pentominoes p, Box box)

Вы проходите мимо Box параметр по значению, чтобы изменения применялись к локальной копии, а не к исходному объекту.

Решение состоит в том, чтобы передать его по ссылке или указателю (как это делается с другими функциями, которые его модифицируют):
void removepuzzle(const Pentominoes &p, Box &box)

Обратите внимание, что я тоже прошел Pentominoes по ссылке, чтобы избежать копирования массива и использования const чтобы указать, что он не модифицирован.

[РЕДАКТИРОВАТЬ]
Здесь есть еще одна ошибка в solve() функция:
count--;
usedChar[count] = '\0';

Это приведет к выходу из связанного доступа (вы вызываете solve() от main() с count = 0).
Там должен быть чек, если count становится негативным.
Однако я ожидал бы, что count должно быть увеличено, а не уменьшено и сломано, когда оно станет 12.
[/РЕДАКТИРОВАТЬ]

Member 12851235

Спасибо за ваш ответ. Я попытался изменить аргумент функции. Однако головоломку все равно нельзя убрать в доску. Я отслеживаю программу до тех пор, пока не будет поставлена буква "U". Больше никакая головоломка не может поместиться и поместиться на доске, и поэтому она будет возвращаться назад, чтобы удалить "U", помещенную на доску. usedChar[i] = ' U ' удаляется,и счетчик уменьшается. С 'U' в доску нельзя удалить, Новый 'у' вновь помещен в доску и есть двойное " у " головоломки размещенные. Я очень смущен, является ли моя концепция в этой программе неправильной. Большое спасибо.

Jochen Arndt

Честно говоря, я не проверял ваш алгоритм и то, что происходит в вашем коде. Это потребует слишком много времени.

Я только что понял, что передача поля по значению-это очевидная ошибка, которая мешает коду делать то, что ожидается.

Обычным методом решения таких алгоритмических задач является отладка. Пройдитесь по коду и сравните текущее состояние с ожидаемыми значениями.

В вашем случае это может помочь сбросить содержимое коробки на экран, как уже было сделано. Но тогда вы должны обрабатывать нулевой байт (например, печатая пробел).

Есть еще одна ошибка, которую я нашел:
Вы уменьшаете количество в функции solve (). Когда count равен нулю раньше, у вас будет доступ за пределы границ по адресу
usedChar[count] = '\0';
Не следует ли здесь увеличить счет?
И должно быть условие выхода, когда количество достигает предела.
Я обновлю свое решение.