用於解決數獨的遞歸方法

我目前正在學習我在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; 
    } 

}

那麼有人有什麼想法？

來源

2013-03-11 user2155599

你試過調試過嗎？ – kunal 2013-03-11 06:03:41