Итеративный решатель судоку

Question

Я пытаюсь реализовать итеративное решение судоку. Чтобы избежать рекурсии, я использовал стек, но у меня проблемы с его управлением. Начальная доска представлена ​​массивом String (переменная 'input' в следующем коде), в котором каждый элемент состоит из 3 чисел: [row, col] и его значение (т. Е. "006" означает, что элемент в 1-я строка и 1-й столбец - 6) и переводятся в массив int конструктором. Когда я запускаю его, я не могу найти решение, поэтому в вложенных циклах могут быть ошибки. Любая помощь приветствуется.

import java.util.ArrayList;

public class SudokuSolver {

    private int[][] matrix = new int[9][9];
    private String[] input = { "006", "073", "102", "131", "149", "217",
        "235", "303", "345", "361", "378", "422", "465", "514", "521",
        "548", "582", "658", "679", "743", "752", "784", "818", "883" };

    private ArrayList<int[][]> stack = new ArrayList<>();

    public SudokuSolver() {
        // Building the board based on input array
        for (int n = 0; n < input.length; ++n) {
            int i = Integer.parseInt(input[n].substring(0, 1));
            int j = Integer.parseInt(input[n].substring(1, 2));
            int val = Integer.parseInt(input[n].substring(2, 3));
            matrix[i][j] = val;
        }
        stack.add(matrix);
    }

    private boolean isSolution(int[][] cells) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(cells[i][j] == 0)
                    return false;
            }
        }
        return true;
    }

    private boolean isValid(int i, int j, int val, int[][] cells) {
        for (int k = 0; k < 9; k++)
            if (val == cells[k][j])
                return false;
        for (int k = 0; k < 9; k++)
            if (val == cells[i][k])
                return false;
        return true;
    }

    private boolean iterativeSudokuSolver() {
        int[][] current = null;

        while(stack.size() > 0 && !isSolution(stack.get(0))) {
            current = stack.remove(0);

            for (int row = 0; row < 9; row++) {
                for (int col = 0; col < 9; col++) {
                    if (current[row][col] == 0) {
                        for (int val = 1; val <= 9; val++) {
                            if (isValid(row, col, val, current)) {
                                current[row][col] = val;
                                stack.add(0, current);
                                break;
                            }
                        }
                    }
                }
            }
        }
        if (current != null && isSolution(current))
            return true;
        else
            return false;
    }

    public static void main(String [] args) {
        SudokuSolver sudokuSolver = new SudokuSolver();
        boolean result = sudokuSolver.iterativeSudokuSolver();

        if (result)
            System.out.println("Sudoku solved");
        else
            System.out.println("Sudoku not solved");
    }
}

Answer 1

1. Реализация стека путем добавления и удаления 0-го элемента ArrayList - очень плохая идея: она заставляет весь контент массива каждый раз сдвигаться назад на четверть. Используйте LinkedList или измените конец списка.
2. Когда вы добавляете и удаляете один и тот же экземпляр матрицы назад и вперед в стек, это все тот же объект матрицы, даже если вы можете назвать его "текущим" или любым другим именем. Это означает, что когда вы изменяете что-то в матрице, а затем удаляете это из своего стека, изменение остается там (и во всех других элементах вашего стека, которые являются идентичными ссылками на один и тот же объект). Логика вашего решения выглядит так, как будто ему необходимо сохранить предыдущее состояние решения в стеке, если это так, - каждый раз выделять новый массив и копировать данные (тоже не очень эффективно, но попробуйте начать с него).
3. Хороший вопрос должен быть конкретным. "Почему это не работает?" это плохой вопрос. Сначала исправьте очевидные проблемы, отладьте, и, если озадачены, предоставьте больше информации о состоянии вашей программы (например, данные в, данные на шаге 1...N)