Вопрос по algorithm – Алгоритм судоку, перебор [закрыт]

-2

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

Для каждой строки, столбца и поля создается объект, который содержит все квадраты (ячейки), которые принадлежат фактически столбцу, квадрату и строке, это используется в legalValue () для проверки возможности помещения значения в ячейку.

Я не могу найти структуру, которая заставляет алгоритм работать.

<code>    boolean setNumberMeAndTheRest(Board board) {


    if(getNext() == null) {
        for(int i = 1; i <= board.getDimension(); i++) {
            if(legalValue(i)) {
                setValue(i);
            }
        }
        board.saveSolution();
    } else {
        if(this instanceof DefinedSquare) {
            getNext().setNumberMeAndTheRest(board);

        } else {
            for(int i = 1; i <= board.getDimension(); i++) {
                if(legalValue(i)) {
                    setValue(i);

                    if(getNext().setNumberMeAndTheRest(board)) {
                        return true;
                    } else {
                        setValue(i);
                    }
                }
            }
            return false;
        }
    }

    return false;
}
</code>

Вот юридическое значение (int i);

<code>/**
 * Checks if value is legal in box, row and column.
 * @param value to check.
 * @return true if value is legal, else false.
 */
boolean legalValue(int value) {
    if(box.legalValue(value) && row.legalValue(value) && columne.legalValue(value)) {
        return true;
    }
    return false;
}
</code>
<code>**4x4 Sudoku board INPUT**

0 2 | 1 3
0 0 | 0 4
---------
0 0 | 0 1
0 4 | 3 2

**Expected OUTPUT**

4 2 | 1 3
3 1 | 2 4
---------
2 3 | 4 1
1 4 | 3 2

**Actually OUTPUT**

4 2 | 1 3
2 4 | 3 4
---------
3 0 | 0 1
0 4 | 3 2
</code>

Добавлен сброс платы

<code>boolean setNumberMeAndTheRest(Board board) {

    Board original = board;

    if(getNext() == null) { 
        for(int i = 1; i <= board.getDimension(); i++) {
            if(legalValue(i)) {
                setValue(i);
            }
        }
        board.saveSolution();

    } else {
        if(this instanceof DefinedSquare) {
            getNext().setNumberMeAndTheRest(board);

        } else {
            for(int i = 1; i <= board.getDimension(); i++) {
                if(legalValue(i)) {
                    setValue(i);

                    if(getNext().setNumberMeAndTheRest(board)) {
                        return true;
                    } else {
                        setValue(i);
                    }
                }
            }
            board = original;
            return false;
        }
    }
    board = original;
    return false;
}
</code>

Ее решение, спустя долгое время: D

<code>boolean setNumberMeAndTheRest(Board board) {

    if(next == null) {
        board.saveSolution();
        return true;
    }

    if(this instanceof DefinedSquare) {
        return next.setNumberMeAndTheRest(board);
    }

    for(int i = 1; i <= board.getDimension(); ++i) {
        if(legalValue(i)) {
            setValue(i);

            if(next.setNumberMeAndTheRest(board)) {
                return true;
            }
        }
    }
    setValue(0);
    return false;
}
</code>
Хорошо спасибо. Сделали б и в, некоторые а. user265767
Вам необходимо сбросить значение перед возвратомfalse, (Вы пытались заполнить ячейку, но потерпели неудачу, оставив ячейку в точности так, как вы ее получили). Кроме того, «объектно-ориентированный» подход не покупает здесь ничего, кроме осложнений. Простой двумерный массив чисел отлично подойдет. n.m.
что вы имеете в виду, что вы не можете заставить его работать? В чем ошибка? twain249
а. закомментируйте свой код, чтобы мы могли сказать, что вы делаете b. предоставить выборочные входные данные, ожидаемые выходные данные и фактические выходные данные c. используйте 3x3 или 4x4 для тестирования, намного легче отследить, чем 6x6 Jason
Вывод такой: в последней строке нули. 561733 242567 624364 265642 756350 300102 user265767

Ваш Ответ

1   ответ
1
boolean setNumberMeAndTheRest(Board board) {

  // make a copy of the original board
  Board original = board;

когда вы возвращаете ложь, вам также нужно сбросить доску в исходное состояние

board = original;
return false;
Я считаю, что это ничего не делает, потому что результат остается прежним. user265767
Не знаю. Если бы я был вами, я бы попробовал 2x2 или 3x3 и просто пошагово прошел весь алгоритм в отладчике, пока не найдете его.
Ага. Я возвращаю ложные два места в алгоритме, см. Мое редактирование. user265767
Я тоже, я слепой в коде user265767
Вы сбрасывали доску в исходное состояние каждый раз, когда возвращали false?

Похожие вопросы