解决数独的递归方法
我目前正在学习我的第二个java编程课程，并且我需要完成一项通过该课程的作业有问题。 基本上它是关于编写一个程序，递归地解决数据与回溯。 这是我提出的算法。 我使用了一个9×9数组来表示网格，该网格在开头用零填充。 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 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 = 2) && (j / 3 = 2) || (i / 3 >= 1 && i / 3 = 1 && j / 3 8) { return true; } if(sudoku[i][j] == 0) { for(int var = 1; var = 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; } } 所以任何人都有任何想法？
您的程序似乎只是检查给定的数字是否适合给定的插槽，检查行，列和本地3×3网格，如果这三个检查通过则将其永久放置在那里。
这是有问题的，因为大多数数独在这种简单的检查中不会产生单一的可能性。
您需要为每个点制作一个可能的值列表，然后开始使用双对等技术来进一步解决它。
由于它是一台计算机并且速度很快，因此在您使用其中一些技术后，您可以开始强制它。
另一种方法是将数独问题转换为SAT公式，将其提供给SAT求解器，并将解决方案转换回数独解决方案。 如今有非常先进的SAT求解器可以非常快速地处理9×9数独游戏。 这是一个更深入的解释。
在您的求解方法中，您在进行更改之前测试sudoku [i] [j] == 0。 这意味着一旦你输入一个数字，无论是对还是错，你永远不会改变它。 你需要能够退出错误的举动。
你可以在这里找到一个简化的java Sudoku程序。 http://www.heimetli.ch/ffh/simplifiedsudoku.html
如果您可以分享完整的源代码，包括方法checkFill，我们可以帮助您进一步调试