用于解决数独的递归方法
我目前正在学习Java的第二门编程课程，并且在完成通过课程后需要完成的任务方面存在问题。 基本上它是关于编写一个递归解决数独与回溯的程序。 这是我想出的算法。 我用一个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;
}
}
所以任何人有任何想法？
看起来你的程序只是检查一个给定的数字是否可以放入给定的槽中，检查行，列和本地3x3网格，并且如果这三个检查通过，则将其永久放置在那里。
这是有问题的，因为大多数数独在这种简单的检查中不会产生单一的可能性。
您需要为每个点创建可能的值列表，然后开始使用双重对等技术来进一步解决问题。
由于它是一台计算机，而且速度很快，所以在使用其中一些技巧后，您可以开始蛮横的强制操作。
一种不同的方法是将数独问题转化为SAT公式，将其提供给SAT求解器，并将解决方案转化回数独解决方案。 目前有非常先进的SAT求解器，可以很快处理9x9数独。 这是一个更深入的解释。
在您的解决方法中，您在进行更改之前测试sudoku [i] [j] == 0。 这意味着一旦你发出一个号码，无论是对还是错，你都不会改变它。 你需要能够退出错误的举动。
你可以在这里找到一个简化的java Sudoku程序.http：//www.heimetli.ch/ffh/simplifiedsudoku.html
如果您可以与您分享包括checkFill方法在内的完整源代码，我们可以协助您进一步调试
链接地址: http://www.djcxy.com/p/96161.html