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

バックトラッキング メカニズムを実装していないようです。正しいヒューリスティックが実装されていない場合、数字を推測しなければならない場合があります。

ヒューリスティックは「商売の秘訣」です。数独の一般的なもののリストを次に示します。

それらのいくつかだけをプログラムした場合、行き止まりになり、推測する必要があります。これらの推測が間違っている可能性があることを考慮に入れる必要があるため、これはより困難になります。バックトラッキングは、いくつかの推測を「ロールバック」して別の推測を行うことを可能にする戦略です。数独を解決するためにある種のブルートフォースを作成する可能性のツリーと考えてください。

したがって、2つの可能性は、より多くのヒューリスティックを実装するか、より広い範囲の推測を行う方法を見つけることです

于 2012-05-01T22:03:58.170 に答える