1

私は現在、Java の 2 番目のプログラミング コースを勉強していますが、コースに合格するために完了する必要がある課題に問題があります。基本的には、数独をバックトラックで再帰的に解くプログラムを書くことです。これが私が思いついたアルゴリズムです。最初はゼロで埋められているグリッドを表すために、9x9 配列を使用しました。checkFill は、数値 (var) を位置 [i][j] に挿入できるかどうかをチェックします。問題は、数独を部分的にしか解決しないことです。常に false (解決なし) を返し、一部のセルにはまだゼロが含まれています。ここで何が間違っていますか？

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;

public class Sudoku {
    private int[][] sudoku;
    private JFrame frame;
    private JFormattedTextField[][] sudokuSquares;
    private JButton solve, clear;

    public Sudoku() {
        sudoku = new int[9][9];
        frame = new JFrame("Sudoku Solver");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        JPanel northPanel = new JPanel();
        northPanel.setLayout(new GridLayout(9, 9));
        northPanel.setBorder(BorderFactory.createEmptyBorder(10, 10, 10, 10));
        sudokuSquares = new JFormattedTextField[9][9];
        Font font1 = new Font("SansSerif", Font.BOLD, 20);
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                sudokuSquares[i][j] = new JFormattedTextField();
                sudokuSquares[i][j].setHorizontalAlignment(JTextField.CENTER);
                sudokuSquares[i][j].setFont(font1);
                sudokuSquares[i][j].setBorder(BorderFactory.createEtchedBorder(javax.swing.border.EtchedBorder.RAISED));
                northPanel.add(sudokuSquares[i][j]);
            }
        }
        setColor();
        frame.add(northPanel, BorderLayout.NORTH);
        JPanel southPanel = new JPanel();
        solve = new JButton("Solve");
        solve.addActionListener(new SolveButtonListener());
        clear = new JButton("Clear");
        clear.addActionListener(new ClearButtonListener());
        southPanel.add(clear);
        southPanel.add(solve);
        frame.add(southPanel, BorderLayout.SOUTH);
        frame.setResizable(false);
        frame.setSize(280, 330);
        frame.setVisible(true);
    }

    private void solveSudoku() {
        boolean hasSolution = solve(0, 0);
        if(hasSolution) {
            JOptionPane.showMessageDialog(frame, "Sudoku has been successfully solved");
        } else {
            JOptionPane.showMessageDialog(frame, "Sudoku has no solution");
        }

    }

    private class SolveButtonListener implements ActionListener {
        @Override
        /**
         * Checks input for errors and outputs the sudoku matrix after it's been solved.
         */
        public void actionPerformed(ActionEvent e) {
            String s;
            setColor();
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) {
                    s = sudokuSquares[i][j].getText();
                    if(s.isEmpty()) {
                        s = "0";
                    } else if(s.length() > 1 || !Character.isDigit(s.charAt(0)) || s.charAt(0) == '0') {
                        sudokuSquares[i][j].setBackground(Color.RED);
                        JOptionPane.showMessageDialog(frame, "Invalid entry! Please enter a number between 1-9");
                        return;
                    }
                    sudoku[i][j] = Integer.parseInt(s);
                }
            }
            solveSudoku();
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) {
                    sudokuSquares[i][j].setText(String.valueOf(sudoku[i][j]));
                }
            }
        }
    }

    private class ClearButtonListener implements ActionListener {
        @Override
        public void actionPerformed(ActionEvent e) {
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) {
                    sudokuSquares[i][j].setText("");
                }
            }
            setColor();
        }   
    }

    /**
     * Sets the background color of sudoku cells
     */
    private void setColor() {
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if((i / 3 < 1 || i / 3 >= 2) && (j / 3 < 1 || j / 3 >= 2) || 
                        (i / 3 >= 1 && i / 3 < 2) && (j / 3 >= 1 && j / 3 < 2)) {
                    sudokuSquares[i][j].setBackground(new Color(220, 220, 220));
                } else {
                    sudokuSquares[i][j].setBackground(Color.WHITE);
                }
            }
        }
    }

    /**
     * Solves the sudoku through recursive technique
     * @param i row
     * @param j column
     * @return returns true if the sudoku has a solution, returns false otherwise
     */
    private boolean solve(int i, int j) {
        if(i > 8) {
            return true;
        }
        if(sudoku[i][j] == 0) {
            for(int var = 1; var < 10; var++) {
                if(checkFill(i, j, var)) {
                    sudoku[i][j] = var;
                    if(j >= 8) {
                        solve(i + 1, 0);
                    } else {
                        solve(i, j+1);
                    }
                }
            }
        } else {
            if(j >= 8) {
                solve(i + 1, 0);
            } else {
                solve(i, j+1);
            }
        }
        return false;
    }

    /**
     * Checks if var could be inserted at position [i][j]
     * @param i row
     * @param j column
     * @param var number to be checked for possible insertion
     * @return
     */
    private boolean checkFill(int i, int j, int var) {
        for(int a = 0; a < 9; a++) {
            if(sudoku[a][j] == var) {
                return false;
            }
        }
        for(int a = 0; a < 9; a++) {
            if(sudoku[i][a] == var) {
                return false;
            }
        }
        int tempI = (i / 3) * 3;
        int tempJ = (j / 3) * 3;
        for(int a = 0; a < 3; a++) {
            for(int b = 0; b < 3; b++) {
                if(sudoku[tempI + a][tempJ + b] == var)
                    return false;
            }
        }
        return true;
    }

}

それで、誰かが何かアイデアを得ましたか？

4

3 に答える 3

2

あなたのプログラムは、与えられた数字が与えられたスロットに収まるかどうかをチェックし、行、列、およびローカル 3x3 グリッドをチェックし、これら 3 つのチェックに合格した場合はそこに永続的に配置するようです。

ほとんどの数独は、このような単純なチェックでは単一の可能性をもたらさないため、これは問題です。

各スポットの可能な値のリストを作成し、ダブル ペアなどの手法を使用してさらに解決する必要があります。

これはコンピューターであり、高速であるため、これらの手法のいくつかを使用した後、ブルート フォーシングを開始できます。

別のアプローチとして、数独問題を SAT 式に変換し、それを SAT ソルバーに入力して、その解を数独解に戻すという方法があります。最近では、9x9 数独を非常に迅速に処理できる非常に高度な SAT ソルバーがあります。ここに、より詳細な説明があります。

于 2013-03-14T02:43:20.480 に答える
1

solve メソッドでは、変更を加える前に sudoku[i][j]==0 かどうかをテストします。つまり、数字を配置したら、それが正しいか間違っているかにかかわらず、それを変更することはありません。誤った動きを取り消すことができる必要があります。

于 2013-03-16T01:33:03.843 に答える
0

簡略化された Java Sudoku プログラムはこちらにあります。http://www.heimetli.ch/ffh/simplifiedsudoku.html

メソッド checkFill を含む完全なソース コードを共有していただければ、さらにデバッグを支援できます。

于 2013-03-11T06:34:11.567 に答える