Алгоритм решения логики (для судоку в Java)

У меня проблемы с моим алгоритмом решения логики. Он решает головоломки с большим количеством подсказок очень хорошо, у него просто проблемы с головоломками, которые имеют менее 45 подсказок.

Это алгоритм для решения. Immutable - это логическое значение, которое определяет, можно ли изменить это значение. cell [row] [col].possibleValues ​​- это LinkedList в классе SudokuCell, который сохраняет значения, которые возможны для этого элемента сетки. grid.sGrid является основным массивом int [] [] головоломки. removeFromCells() - метод, который удаляет значения из строки, столбца и квадранта сетки. Этот код предоставляется ниже.

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

public boolean solve(){

    for(int i = 0; i < 81; i++){
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                if(!immutable[row][col]){
                    if(cell[row][col].getSize() == 1){
                        int value = cell[row][col].possibleValues.get(0);
                        grid.sGrid[row][col] = value;
                        immutable[row][col] = true;
                        removeFromCells(row, col, value);
                    }
                }
            }
        }
    }


    int i = 0;
    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            if(grid.sGrid[row][col] == 0){
                i++;
            }
        }
    }

    if(i != 0){
        return false;
    } else{
        return true;
    }
}

Это код для удаленияFromCells()

Я думаю, что большая часть кода довольно понятна. Первый цикл for удаляет значение из строки и столбца (x, y), а второй цикл удаляет значение из квадранта.

public void removeFromCells(int x, int y, int value){

    /*
     * First thing to do, find the quadrant where cell[x][y] belong.
     */

    int topLeftCornerRow = 3 * (x / 3) ;
    int topLeftCornerCol = 3 * (y / 3) ;

    /*
     * Remove the values from each row and column including the one
     * where the original value to be removed is.
     */
    for(int i = 0; i < 9; i++){
        cell[i][y].removeValue(value);
        cell[x][i].removeValue(value);
    }


    for(int row = 0; row < 3; row++){
        for(int col = 0; col < 3; col++){
            cell[topLeftCornerRow + row][topLeftCornerCol + col].removeValue(value);
        }
    }
}

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

Первый цикл for создает новые SudokuCells, чтобы избежать исключения ужасного нулевого указателя.

Любые нулевые значения в sGrid представлены как 0, поэтому цикл for пропускает их.

Конструктор для SudokuBoard вызывает этот метод, поэтому я знаю, что он вызывается.

public void constructBoard(){

    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            cell[row][col] = new SudokuCell();
        }
    }

    immutable = new boolean[9][9];

    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            immutable[row][col] = false;
            if(grid.sGrid[row][col] != 0){
                removeFromCells(row, col, grid.sGrid[row][col]);
                immutable[row][col] = true;
            }
        }
    }
}

Я бы опубликовал весь файл, но там много ненужных методов. Я опубликовал то, что, по моему мнению, вызывает проблемы.

Ответы

Ответ 1

Кажется, вы построили только упрощенное решение, основанное на разрешении. Вам нужен полный откат, чтобы решать головоломки с меньшими намеками. Есть некоторые случаи, которые вы не можете решить без возврата.

В качестве альтернативы вам следует попытаться реализовать алгоритм Кнута (Dancing Links) для решения таких проблем. Это сложнее понять и реализовать, чем алгоритм обратного отслеживания, но он работает лучше:). См. Здесь: http://en.wikipedia.org/wiki/Dancing_Links

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

В wikipedia есть ссылка на статью, в которой подробно описывается, какие типы экземпляров можно решить с помощью программирования ограничений: http://4c.ucc.ie/~hsimonis/sudoku.pdf (найдено из здесь: http://en.wikipedia.org/wiki/Sudoku_algorithms). Таблица 4 действительно интересна:).

Ответ 2

Я использовал множество таких правил для разработки моего решения sudoku. Тем не менее я всегда оказывался вынужденным использовать откат для очень трудного судоку. Согласно википедии, некоторые судоку фактически невозможно решить, используя только правила.

Я выполнил в общей сложности 6 правил.

• Никакое другое значение не допускается.
• Некоторое значение разрешено в любом другом квадрате в том же разделе.
• Некоторое значение разрешено в любом другом квадрате в той же строке или столбце.
• Определенное значение разрешено только для одного столбца или строки внутри раздела, поэтому мы можем исключить это значение из этой строки или столбца в других разделах.
• Голые пары
• Линии

Я описал весь алгоритм и дал код в этих двух блогах (исходная версия использовала только первые 4 правила).

http://www.byteauthor.com/2010/08/sudoku-solver/

http://www.byteauthor.com/2010/08/sudoku-solver-update/

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