6

我不知道自己做错了什么，整天盯着这段代码。这是 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. 这是我迄今为止写的最亵渎的代码。）

谢谢！

4

2 回答 2

3

我开始阅读您的代码，但感觉比应该的要长，而且这些循环变得非常混乱。没有什么会立即向我跳出来。您确实说过您不仅想要解决方案，还想要建议。

您必须弄清楚问题是否出在您的设计上（它不适用于解决数独问题），或者是否在实现中的某个地方存在一个简单的错误。也许通过并写评论每个循环正在完成什么，“橡皮鸭测试”，被迫解释一切，你会停下来并意识到某些事情是不必要的，或者不是它需要的。这有助于解决设计问题。

如果问题是实现，你知道如何正式调试应用程序吗？设置断点并逐条执行？如果你有一个小错误，但你不知道在哪里，那就是要走的路。找到一个非常简单的失败示例，然后运行该测试并在开始时将其中断。逐步进行，并遵循逻辑。希望你会看到哪里出了问题。编写 JUnit 测试或日志语句很棒，但是当您遇到棘手的错误时，您必须进行一些真正的断点调试。

你的通用框架很好，你有一些对象来保存数据，还有一个很好的干净的解决方法，它调用了一些不同的方法并循环它们。但是这些方法中的每一个，哇，他们肯定是一团糟。那种代码，大量使用相同变量名的紧密循环，大量数组操作，很容易弄错东西并得到一个错误，这使得阅读和找到错误变得非常困难。

Eclipse 使调试 java 变得非常容易，如果您以前没有的话。google上很多不错的教程，就不打扰了^_~

于 2012-05-01T21:45:39.000 回答
1

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

启发式是“交易技巧”，这里是数独的常用技巧列表。

如果你只对其中的几个进行编程，你就会陷入死胡同，不得不猜测。这使得它变得更加困难，因为必须考虑到这些猜测可能是错误的。回溯是一种策略，可让您“回滚”一些猜测并做出不同的猜测。把它想象成一棵用蛮力解决数独的可能性树。

所以你的两种可能性是实施更多的启发式或找到一种方法来进行更广泛的猜测

于 2012-05-01T22:03:58.170 回答