- import java.awt.BorderLayout;
- import java.awt.Color;
- import java.awt.Font;
- import java.awt.GridLayout;
- import java.awt.event.ActionEvent;
- import java.awt.event.ActionListener;
- import java.util.ArrayList;
- import javax.swing.JButton;
- import javax.swing.JFrame;
- import javax.swing.JPanel;
- import javax.swing.JTextField;
- /**
- * Number类 保存用户输入的数字
- */
- class Number {
- int num = 0;
- public Number(int num) {
- // TODO 自动生成的构造函数存根
- this.num = num;
- }
- public void setNum(int num) {
- this.num = num;
- }
- public int getNum() {
- return num;
- }
- }
- /**
- * 深度优先搜索+回溯 解数独
- *
- * @author Vincent Chan
- *
- */
- public class Sudoku extends JFrame {
- private Number MAPS[][] = new Number[9][9];
- private ArrayList<Number> Grid[] = new ArrayList[9];
- private JTextField blocks[][] = new JTextField[9][9];
- private final int width = 400, height = 420;
- private JButton submit = new JButton("提交");
- private JButton reset = new JButton("重置");
- private boolean ok = false;
- public Sudoku() {
- // TODO 自动生成的构造函数存根
- initMap();
- initUi();
- initListener();
- }
- /**
- * 初始化界面
- */
- public void initUi() {
- setTitle("Sudoku");
- setSize(width, height);
- setLocationRelativeTo(null);
- JPanel panel1 = new JPanel();
- panel1.setLayout(new GridLayout(9, 9));
- for (int i = 0; i < 9; i++)
- for (int j = 0; j < 9; j++) {
- blocks[i][j] = new JTextField();
- blocks[i][j].setFont(new Font("serif", Font.BOLD, 30));
- blocks[i][j].setHorizontalAlignment(JTextField.CENTER);
- panel1.add(blocks[i][j]);
- }
- JPanel panel2 = new JPanel();
- panel2.setLayout(new GridLayout(1, 2));
- panel2.add(submit);
- panel2.add(reset);
- add(panel1, BorderLayout.CENTER);
- add(panel2, BorderLayout.SOUTH);
- setVisible(true);
- }
- /**
- * 初始化监听器
- */
- public void initListener() {
- submit.addActionListener(new ActionListener() {
- @Override
- public void actionPerformed(ActionEvent e) {
- // TODO 自动生成的方法存根
- ok = false;
- for (int i = 0; i < 9; i++)
- for (int j = 0; j < 9; j++) {
- if (!blocks[i][j].getText().equals(""))
- MAPS[i][j].setNum(Integer.valueOf(blocks[i][j]
- .getText()));
- }
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++)
- System.out.print(MAPS[i][j].getNum() + " ");
- System.out.println();
- }
- System.out.println();
- dfs(0, 0);
- }
- });
- reset.addActionListener(new ActionListener() {
- @Override
- public void actionPerformed(ActionEvent e) {
- // TODO 自动生成的方法存根
- for (int i = 0; i < 9; i++)
- for (int j = 0; j < 9; j++) {
- MAPS[i][j].setNum(0);
- blocks[i][j].setForeground(Color.black);
- blocks[i][j].setText(null);
- }
- }
- });
- }
- /**
- * 深度优先搜索
- */
- private void dfs(int i, int j) {
- if (i >= 9) {
- ok = true;
- printResult(); // 输出结果
- return;
- }
- // 若数字已填 则填下一个
- if (MAPS[i][j].getNum() != 0)
- dfs(i + (j + 1) / 9, (j + 1) % 9);
- else {
- // 从1填到9
- for (int num = 1; num <= 9; num++) {
- MAPS[i][j].setNum(num);
- if (check(i, j))
- dfs(i + (j + 1) / 9, (j + 1) % 9);
- if (ok)
- return;
- }
- MAPS[i][j].setNum(0);
- }
- }
- /**
- * 检测第i行j列的数字是否合理
- *
- * @param i
- * @param j
- * @return
- */
- private boolean check(int i, int j) {
- boolean result = true;
- if (!checkColumn(i, j))
- result = false;
- else if (!checkRow(i, j))
- result = false;
- else if (!checkGrid(i, j))
- result = false;
- return result;
- }
- /**
- * 检测行
- *
- * @param i
- * @param j
- * @return
- */
- private boolean checkRow(int i, int j) {
- for (int k = 0; k <= 8; k++) {
- if (j != k && MAPS[i][k].getNum() == MAPS[i][j].getNum())
- return false;
- }
- return true;
- }
- /**
- * 检测列
- *
- * @param i
- * @param j
- * @return
- */
- private boolean checkColumn(int i, int j) {
- for (int k = 0; k <= 8; k++) {
- if (i != k && MAPS[k][j].getNum() == MAPS[i][j].getNum())
- return false;
- }
- return true;
- }
- /**
- * 检测宫格
- *
- * @return
- */
- private boolean checkGrid(int i, int j) {
- int g = 0;// 表示第g宫格
- if (i >= 0 && i <= 2 && j >= 0 && j <= 2)
- g = 0;
- else if (i >= 0 && i <= 2 && j >= 3 && j <= 5)
- g = 1;
- else if (i >= 0 && i <= 2 && j >= 6 && j <= 8)
- g = 2;
- else if (i >= 3 && i <= 5 && j >= 0 && j <= 2)
- g = 3;
- else if (i >= 3 && i <= 5 && j >= 3 && j <= 5)
- g = 4;
- else if (i >= 3 && i <= 5 && j >= 6 && j <= 8)
- g = 5;
- else if (i >= 6 && i <= 8 && j >= 0 && j <= 2)
- g = 6;
- else if (i >= 6 && i <= 8 && j >= 3 && j <= 5)
- g = 7;
- else if (i >= 6 && i <= 8 && j >= 6 && j <= 8)
- g = 8;
- int locate = 3 * (i % 3) + j % 3;
- for (int k = 0; k <= 8; k++)
- if (k != locate && MAPS[i][j].getNum() == Grid[g].get(k).getNum())
- return false;
- return true;
- }
- /**
- * 初始化地图
- */
- public void initMap() {
- for (int i = 0; i < 9; i++)
- for (int j = 0; j < 9; j++)
- MAPS[i][j] = new Number(0);
- for (int i = 0; i < 9; i++)
- Grid[i] = new ArrayList<Number>();
- for (int I = 0; I <= 2; I++)
- for (int J = 0; J <= 2; J++)
- Grid[0].add(MAPS[I][J]);
- for (int I = 0; I <= 2; I++)
- for (int J = 3; J <= 5; J++)
- Grid[1].add(MAPS[I][J]);
- for (int I = 0; I <= 2; I++)
- for (int J = 6; J <= 8; J++)
- Grid[2].add(MAPS[I][J]);
- for (int I = 3; I <= 5; I++)
- for (int J = 0; J <= 2; J++)
- Grid[3].add(MAPS[I][J]);
- for (int I = 3; I <= 5; I++)
- for (int J = 3; J <= 5; J++)
- Grid[4].add(MAPS[I][J]);
- for (int I = 3; I <= 5; I++)
- for (int J = 6; J <= 8; J++)
- Grid[5].add(MAPS[I][J]);
- for (int I = 6; I <= 8; I++)
- for (int J = 0; J <= 2; J++)
- Grid[6].add(MAPS[I][J]);
- for (int I = 6; I <= 8; I++)
- for (int J = 3; J <= 5; J++)
- Grid[7].add(MAPS[I][J]);
- for (int I = 6; I <= 8; I++)
- for (int J = 6; J <= 8; J++)
- Grid[8].add(MAPS[I][J]);
- }
- /**
- * 输出结果
- */
- private void printResult() {
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- System.out.print(" " + MAPS[i][j].getNum());
- if (blocks[i][j].getText().equals("")) {
- blocks[i][j].setForeground(Color.red);
- blocks[i][j].setText("" + MAPS[i][j].getNum());
- }
- }
- System.out.println();
- }
- }
- public static void main(String[] args) {
- new Sudoku();
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/3112201411453.html
来源: http://www.codesnippet.cn/detail/3112201411453.html