迭代暴力数独求解器

Question

我正在尝试实现迭代数独求解器。为了避免递归，我使用了堆栈，但我在管理方面遇到了问题。起始板由一个字符串数组（以下代码中的变量 'input'）表示，其中每个元素由 3 个数字组成：[row, col] 及其值（即“006”表示该元素在第 1 行中，第 1 列为 6)，并由构造函数转换为 int 数组。当我运行它时，我无法得到解决方案，因此嵌套for循环可能有错误。感谢任何帮助。

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

通过添加和删除 ArrayList 的第 0 个元素来实现堆栈是一个非常糟糕的主意：它强制数组的全部内容每次都来回移动。使用LinkedList或修改链表尾部
当您在堆栈中来回添加和删除相同的矩阵实例时，它仍然是相同的矩阵对象，即使您可以将其称为 "current" 或任何其他名称。这意味着当您更改矩阵中的某些内容然后将其从堆栈中删除时，更改将保留在那里（并且在堆栈的每个其他元素中，它们是指向同一对象的相同链接）。您的解决方案的逻辑看起来需要将解决方案的先前状态存储在堆栈中，如果是这样 - 每次都分配一个新数组并复制数据（也不是很有效，但请尝试从那里开始）。
好问题一定要具体。 "Why this doesn't work?" 是个糟糕的问题。首先修复明显的问题，调试，如果有疑问，请提供有关程序状态的更多信息（数据输入，例如步骤 #1...N 的数据）

迭代暴力数独求解器

Iterative brute-force sudoku solver

java

nested

sudoku