при завершении последнего шага рекурсия не возвращается на шаг назад - PullRequest
Новая
       15

при завершении последнего шага рекурсия не возвращается на шаг назад

0 голосов
/ 30 апреля 2018

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

public static void dfs(int x, int y, int value )

{
    if(matriz[x][y]==0)
    {
        SudokuSolved[x][y]=value;
    }
    boolean br= breakrule(x,y);
    if (br==false)
    {
        sol = solved();
    }
    if(solved()==false&&br==false)
    {
        f++;
        if (f>=9)
        {
            f=0;
            c++;
        }
        for (int num=1;num<10;num++)
        {               
            dfs(f,c,num);
        }
    }
    if(solved()==true&&br==false)
    {
        for (int i=0; i<9;i++)
        {
            System.out.println("-------------------");
            System.out.print('|');
            for (int j=0; j<9;j++)
            {
                System.out.print(SudokuSolved[i][j]);
                System.out.print('|');
            }
            System.out.println();
        }
        System.out.println("-------------------");
    }
}

Любые советы или предложения приветствуются

1 Ответ

0 голосов
/ 30 апреля 2018

Трудно диагностировать по предоставленному вами коду, но похоже, что вы неправильно понимаете, как работает обратный трекинг. В псевдокоде ваш алгоритм должен выглядеть примерно так: 

test value:
    change state to include value
    if state is legal
        if state is complete
            use completed state
        else
            test all possible values in next step
    change state to remove value

Попробуйте изменить код в соответствии с этим шаблоном.

Например, если у вас есть хорошо инкапсулированные классы для представления доски Судоко, то код для решения может быть: 

private void solve(Board board, CellValue value) {
    board.add(value);
    if (board.isLegal()) {
        if (board.isComplete()) {
            useSolution(board);
        } else {
            Cell cell = board.firstEmptyCell();
            for (Value value: Value.values())
                solve(board, new CellValue(cell, value));
        }
    }
    board.remove(value);
}
...