数独求解程序错误

Question

我不知道我的错误在哪里，我一整天都在盯着这段代码看。 这是一个Java中的“标准”数独求解器，它接受一个int [] []数组，其中0表示空格。 因为我只传入了一个有35个空格的数独棋盘，所以应该能够解决绝大多数问题，但只能解决约66％的问题。在其他情况下，还剩下一些（通常是2或4）无法解决的空格（即在board中写入了错误的数字）。几乎总是缺少9。

我知道这样简单的解决方案不能解决所有数独游戏。 我故意给它一些易解的数独。

import java.util.ArrayList;
import java.util.List;

public class SudokuSolver
{
    public SudokuSolver()
    {
        init();
    }

    public boolean solve()
    {
        /* Each method checks (in different ways) to see if it can find a new number
            If said method does find a number, it sets off a chain reaction, starting back at the beginning.
        */
        int countdown = 20;
        while(!solved() && --countdown > 0)
        {
            if(given())
                continue;
            if(findSingletons())
                continue;
            if(zerosLeft() <= 4)
                justGuess();
        }
        return solved();
    }

    public boolean given()
    {
        boolean repeat = false;
        //Iterate through every given number
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j] != 0 && !found[i][j])
                {
                    repeat = true;
                    foundNum(i, j, board[i][j]);
                }
            }
        }
        //Call given every time a new number is found
        return repeat;
    }

    public boolean findSingletons()
    {
        boolean repeat = false;
        //LOTS of iteration, but I'm out of ideas.
        int[] values;
        ArrayList<Integer> singletons = new ArrayList<Integer>();
        for(int i=0;i<9;i++)
        {
            values = new int[10];
            singletons.clear();
            for(int j=0;j<9;j++)
                for(int k=0;k<possible[i][j].size();k++)
                    values[possible[i][j].get(k)]++;
            for(int j=1;j<10;j++)
                if(values[j] == 1)
                    singletons.add(j);
            for(int j=0;j<9;j++)
                for(int k=0;k<singletons.size();k++)
                    if(possible[i][j].contains(singletons.get(k)))
                    {
                        foundNum(i, j, singletons.get(k));
                        repeat = true;
                    }
        }

        for(int i=0;i<9;i++)
        {
            values = new int[10];
            singletons.clear();
            for(int j=0;j<9;j++)
                for(int k=0;k<possible[j][i].size();k++)
                    values[possible[j][i].get(k)]++;
            for(int j=1;j<10;j++)
                if(values[j] == 1)
                    singletons.add(j);
            for(int j=0;j<9;j++)
                for(int k=0;k<singletons.size();k++)
                    if(possible[j][i].contains(singletons.get(k)))
                    {
                        foundNum(j, i, singletons.get(k));
                        repeat = true;
                    }
        }

        int[] corners = {0,3,6};
        for(int a=0;a<3;a++)
            for(int l=0;l<3;l++)
                for(int i=corners[a];i<corners[a]+3;i++)
                {
                    values = new int[10];
                    singletons.clear();
                    for(int j=corners[l];j<corners[l]+3;j++)
                        for(int k=0;k<possible[i][j].size();k++)
                            values[possible[i][j].get(k)]++;
                    for(int j=1;j<10;j++)
                        if(values[j] == 1)
                            singletons.add(j);
                    for(int j=0;j<9;j++)
                        for(int k=0;k<singletons.size();k++)
                            if(possible[i][j].contains(singletons.get(k)))
                            {
                                foundNum(i, j, singletons.get(k));
                                repeat = true;
                            }
                }
        return repeat;
    }

    public void justGuess()
    {
        outer:
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(board[i][j] == 0)
                {
                    foundNum(i, j, possible[i][j].get(0));
                    break outer;
                }
    }

    public void foundNum(int x, int y, int numFound)
    {

        if(board[x][y] != 0 && board[x][y] != numFound)
        {
            throw new RuntimeException("Attempting to place a number where one was already found");
        }

        board[x][y] = numFound;
        possible[x][y].clear();
        possible[x][y].add(numFound);
        found[x][y] = true;

        for(int i=0;i<9;i++) {
            if(i != x)
                if(possible[i][y].indexOf(numFound) != -1)
                    possible[i][y].remove(possible[i][y].indexOf(numFound));
        }
        for(int i=0;i<9;i++) {
            if(i != y)
                if(possible[x][i].indexOf(numFound) != -1)
                    possible[x][i].remove(possible[x][i].indexOf(numFound));
        }
        int cornerX = 0;
        int cornerY = 0;
        if(x > 2)
            if(x > 5)
                cornerX = 6;
            else
                cornerX = 3;
        if(y > 2)
            if(y > 5)
                cornerY = 6;
            else
                cornerY = 3;
        for(int i=cornerX;i<10 && i<cornerX+3;i++)
            for(int j=cornerY;j<10 && j<cornerY+3;j++)
                if(i != x && j != y)
                    if(possible[i][j].indexOf(numFound) != -1)
                        possible[i][j].remove(possible[i][j].indexOf(numFound));
    }

    public boolean solved() {
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(!found[i][j])
                    return false;
        return true;
    }

    public void reset(int[][] board)
    {
        this.board = board;
        init();
    }

    public void init()
    {
        possible = new ArrayList[9][9];
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
            {
                possible[i][j] = new ArrayList<Integer>();
                for(int k=1;k<10;k++)
                    possible[i][j].add(k);
            }
        found = new boolean[9][9];
    }

    public void print()
    {
        for(int i=0;i<9;i++)
        {
            if(i%3==0 && i != 0)
                System.out.println("-  -  -  | -  -  -  |  -  -  -");
            for(int j=0;j<9;j++)
            {
                if(j%3==0 & j != 0)
                    System.out.print("| ");
                System.out.print(board[i][j] + "  ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private int zerosLeft()
    {
        int empty = 0;
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(board[i][j] == 0)
                    empty++;
        return empty;
    }

    private void data(int difficulty)
    {
        int empty = 0;
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(board[i][j] == 0)
                    empty++;
        System.out.println(empty);
    }

    public static void main(String[] args)
    {
        SudokuGenerator sg = new SudokuGenerator();
        SudokuSolver ss = new SudokuSolver();
        int[][] tempBoard = {{4, 0, 1, 0, 9, 7, 0, 5, 8 },
                        {2, 0, 0, 5, 3, 1, 4, 0, 6 },
                        {5, 0, 6, 4, 0, 2, 0, 3, 9 },
                        {0, 9, 0, 0, 0, 4, 3, 0, 2 },
                        {0, 0, 0, 9, 0, 0, 6, 4, 7 },
                        {7, 0, 4, 0, 0, 0, 9, 0, 5 },
                        {0, 0, 7, 0, 0, 3, 8, 9, 4 },
                        {8, 5, 0, 1, 4, 9, 7, 0, 0 },
                        {9, 0, 3, 8, 7, 6, 0, 0, 0 }};
        ss.reset(tempBoard);
        System.out.println(ss.solve());
        ss.print();
        ss.data(35);
    }

    int[][] board;
    ArrayList<Integer>[][] possible;
    boolean[][] found;
}

我对编程还很新，所以除了解决这个问题之外，任何建议都欢迎。(尤其是优化possible。那是我到目前为止写过的最糟糕的代码。)

谢谢！

- SomeKittens

---

"这是我迄今为止写过的最粗俗的代码。" Eric Lippert在他的C# 图形着色系列中编写了一个相当美丽的数独求解器。它使用了一些Java没有的功能，但我仍然建议您去看一看。" - Adam Mihalcin

通过编写jUnit测试来测试特定方法，推动开发。阅读有关测试驱动开发（TDD）和面向对象设计的资料。这里应用了一些明显的代码重构，但现在没有时间进行全面审查。以下是一些亮点：findSingletons非常冗长，请考虑将其重构为较小的方法。覆盖toString而不是使用print方法；请查看我在类似但更简单的问题上编写的代码，位于https://github.com/RobertKielty/q8impl/tree/master/workspace/EightQueens - Rob Kielty

@Rob：你可以删除自己的评论（你需要更多的声望吗？）- 比如说，如果你过早地点击了“回车”，可能是为了创建新的一行。 - user unknown

Answer 1

我开始阅读你的代码，但感觉代码比应该的要长，那些循环看起来很混乱。没有立即发现问题。你说你不只想要解决方案，还需要建议。

你必须确定问题是设计问题（不能解决数独）还是实现中有简单的错误。也许可以逐个注释每个循环所完成的任务，使用“橡皮鸭测试”，即强制解释所有内容，你会停下来并意识到某些内容是不必要的或者不是所需的。这对于设计问题很有帮助。

如果问题出在实现上，你知道如何正式调试应用程序吗？设置断点，逐指令进行调试？如果你有一个小错误，但不知道具体位置，这就是方法。找一个非常简单的失败案例，然后运行该测试并在开头打断点。跟随逻辑进行调试。希望你能看到何处出错了。编写JUnit测试或日志语句非常好，但当你遇到棘手的错误时，必须进行一些真正的断点调试。

你的通用框架很不错，你有一些对象来保存数据，以及一个漂亮干净的解决方法，它调用几种不同的方法并循环执行它们。但是每个方法，哇，它们非常混乱。这种代码，许多紧密的循环使用相同的变量名，大量的数组操作，很容易出错，并且很难阅读和找到错误。

如果你之前没有使用过Eclipse调试Java程序，Eclipse使Java调试变得非常容易。谷歌上有很多好的教程，所以我就不会再烦你了 ^_^

- SpacePrez

---

感谢您帮助我找到需要查看的地方。我将尝试清理循环语句。如果可以解决问题，我会接受！ - SomeKittens

Answer 2

您似乎没有实现回溯机制。有时候，如果您没有正确的启发式算法，就必须猜测数字。

启发式算法是“行业诀窍”，这里有一个数独常用启发式算法列表。

如果您只编写了其中几个，您将陷入死胡同，并且不得不猜测。这使得它更加困难，因为您必须考虑到那些猜测可能是错误的。回溯是一种策略，可以让您“回滚”几次猜测并进行不同的猜测。将其视为可能性树，以某种暴力方式解决数独问题。

因此，您有两种可能性：实现更多的启发式算法或找到一种方法来进行更广泛的猜测。

- Eric

---

我熟悉回溯算法，我在我的算法中使用它来生成数独棋盘。我不感兴趣解决每个棋盘，只是从我的生成器中传入的非常简单的那些。 - SomeKittens