An interactive solver program in Java

Programs which generate, solve, and analyze Sudoku puzzles

An interactive solver program in Java

Postby swaczin » Mon Jan 23, 2006 5:33 pm

Just type in the numbers and press
Start. Have fun, Helmut

Code: Select all
//---------------- File Sudoku.java ------------------

import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.Dimension;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.EmptyStackException;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

import javax.swing.BorderFactory;
import javax.swing.JButton;
import javax.swing.JDialog;
import javax.swing.JOptionPane;
import javax.swing.JPanel;

public class Sudoku extends JDialog implements ActionListener {

  private static final boolean DEBUG = false; 
                                     
  private Cell[][][][] cells;
  private JButton startButton;
  private Stack stack = new Stack();
               
  Sudoku() {
    setModal(true);
    setTitle("Sudoku");
    initComponents();
    layoutWindow();   
    setInitialSize();
    centerOnScreen();
  }
 
  private void setInitialSize() {
    Dimension preferredSize = getPreferredSize();
    Dimension minimumSize = getMinimumSize();
    int width = Math.max(preferredSize.width, minimumSize.width);
    int height = Math.max(preferredSize.height, minimumSize.height);
    setSize(width, height);
  }

  private void centerOnScreen() {
    Dimension size = getToolkit().getScreenSize();
    setLocation((size.width - getWidth()) / 2, (size.height - getHeight()) / 2 - 20);
  }

  private void initComponents() {
    cells = new Cell[3][3][3][3];
    for (int row1 = 0; row1 < 3; row1++) {
      for (int col1 = 0; col1 < 3; col1++) {
        for (int row2 = 0; row2 < 3; row2++) {
          for (int col2 = 0; col2 < 3; col2++) {
            cells[row1][col1][row2][col2] = new Cell();
          }
        }
      }
    }
    startButton = new JButton("Start");
    startButton.addActionListener(this);
  }
 
  private void layoutWindow() {
    Container pane = getContentPane();
    pane.setLayout(new BorderLayout());
    JPanel cellPanel = new JPanel();
    cellPanel.setLayout(new GridLayout(3, 3));
    for (int row1 = 0; row1 < 3; row1++) {
      for (int col1 = 0; col1 < 3; col1++) {
        JPanel panel = new JPanel();
        panel.setLayout(new GridLayout(3, 3));
        panel.setBorder(BorderFactory.createEmptyBorder(2, 2, 0, 2));
        for (int row2 = 0; row2 < 3; row2++) {
          for (int col2 = 0; col2 < 3; col2++) {
            panel.add(cells[row1][col1][row2][col2]);
          }
        }
        cellPanel.add(panel);
      }
    }
    pane.add(cellPanel, BorderLayout.CENTER);
    pane.add(startButton, BorderLayout.SOUTH);
  }
   
  public void actionPerformed(ActionEvent e) {
    if (checkCells()) {
      disableCells();
      startButton.setEnabled(false);
      Thread solver = new SolverThread();
      solver.start();
    } else {
      JOptionPane.showMessageDialog(this, "Ungültige Eingabe!", "Sudoku",
          JOptionPane.ERROR_MESSAGE);
    }   
  }
 
  private boolean checkCells() {
    initPossibleValues(true);
    for (int row1 = 0; row1 < 3; row1++) {
      for (int col1 = 0; col1 < 3; col1++) {
        for (int row2 = 0; row2 < 3; row2++) {
          for (int col2 = 0; col2 < 3; col2++) {
            Cell cell = cells[row1][col1][row2][col2];
            if (!cell.isValuePossible(cell.getValue())) {
              return false;
            }
          }
        }
      }
    }
    return true;
  }

  private void disableCells() {
    for (int row1 = 0; row1 < 3; row1++) {
      for (int col1 = 0; col1 < 3; col1++) {
        for (int row2 = 0; row2 < 3; row2++) {
          for (int col2 = 0; col2 < 3; col2++) {
            cells[row1][col1][row2][col2].setInputEnabled(false);
          }
        }
      }
    }
  }
 
  private class SolverThread extends Thread {
    public void run() {
      solv();
    }

    private void solv() {
      int count = countInitialValues();
      debug("Initial count: " + count);
      boolean solvable = true;     
      Choice chosen = null;
      while (count < 81 && solvable) {
        if (chosen == null) {
          int size = 1;
          do {
            chosen = chooseValue(size);
            size++;
          } while (chosen == null && size <= 9);
        } else {
          chosen = chooseNextValue(chosen);
        }
        if (chosen != null) {
          setValue(chosen.row1, chosen.col1, chosen.row2, chosen.col2, chosen.value);
          stack.push(chosen);
          count++;
          if (updatePossibleValues(chosen.row1, chosen.col1, chosen.row2, chosen.col2, chosen.value)) {
            chosen = null;
          } else {
            debug("Wrong way, must backtrack...");
            try {
              do {
                chosen = (Choice)stack.pop();
                unsetValue(chosen.row1, chosen.col1, chosen.row2, chosen.col2);
                count--;
              } while (chosen.choices.size() == 1);
              initPossibleValues(false);
            } catch (EmptyStackException x) {
              debug("Stack is Empty");
              solvable = false;
            }
          }
        } else {
          debug("No value found");
          solvable = false;
        }
      }
      if (!solvable) {
        JOptionPane.showMessageDialog(Sudoku.this, "Not solvable!", "Sudoku",
            JOptionPane.ERROR_MESSAGE);
      }
    }
  }

  private int countInitialValues() {
    int count = 0;
    for (int row1 = 0; row1 < 3; row1++) {
      for (int col1 = 0; col1 < 3; col1++) {
        for (int row2 = 0; row2 < 3; row2++) {
          for (int col2 = 0; col2 < 3; col2++) {
            if (cells[row1][col1][row2][col2].getValue() != null) {
              count++;
            }
          }
        }
      }
    }
    return count;
  }
 
  private void initPossibleValues(boolean all) {
    for (int row1 = 0; row1 < 3; row1++) {
      for (int col1 = 0; col1 < 3; col1++) {
        for (int row2 = 0; row2 < 3; row2++) {
          for (int col2 = 0; col2 < 3; col2++) {
            Cell cell = cells[row1][col1][row2][col2];
            if (all || cell.getValue() == null) {
              for (int i = 1; i < 10; i++) {
                cell.getPossibleValues().add(new Integer(i));
              }
              Set values = new HashSet();
              values.addAll(collectMasterCellValues(row1, col1, row2, col2));
              values.addAll(collectRowValues(row1, col1, row2, col2));
              values.addAll(collectColumnValues(row1, col1, row2, col2));
              cell.getPossibleValues().removeAll(values);
              debug("Possible values " + row1 + "," + col1 + "," + row2 + "," + col2 + ": " + cell.getPossibleValues());
            }
          }
        }
      }
    }
  }
 
  private Set collectMasterCellValues(int row1, int col1, int row2, int col2) {
    Set values = new HashSet();
    for (int r2 = 0; r2 < 3; r2++) {
      for (int c2 = 0; c2 < 3; c2++) {
        if (r2 != row2 || c2 != col2) {
          Integer value = cells[row1][col1][r2][c2].getValue();
          if (value != null) {
            values.add(value);
          }
        }
      }
    }
    return values;
  }
 
  private Set collectRowValues(int row1, int col1, int row2, int col2) {
    Set values = new HashSet();
    for (int c1 = 0; c1 < 3; c1++) {
      if (c1 != col1) {
        for (int c2 = 0; c2 < 3; c2++) {
          Integer value = cells[row1][c1][row2][c2].getValue();
          if (value != null) {
            values.add(value);
          }
        }
      }
    }
    return values;
  }

  private Set collectColumnValues(int row1, int col1, int row2, int col2) {
    Set values = new HashSet();
    for (int r1 = 0; r1 < 3; r1++) {
      if (r1 != row1) {
        for (int r2 = 0; r2 < 3; r2++) {
          Integer value = cells[r1][col1][r2][col2].getValue();
          if (value != null) {
            values.add(value);
          }
        }
      }
    }
    return values;
  }
 
  private boolean updatePossibleValues(int row1, int col1, int row2, int col2, Integer value)  {
    return updateMasterCell(row1, col1, row2, col2, value) &&
        updateRow(row1, col1, row2, col2, value) &&
        updateColumn(row1, col1, row2, col2, value);
  }

  private boolean updateMasterCell(int row1, int col1, int row2, int col2, Integer value) {
    for (int r2 = 0; r2 < 3; r2++) {
      for (int c2 = 0; c2 < 3; c2++) {
        if (r2 != row2 || c2 != col2) {
          Cell cell = cells[row1][col1][r2][c2];
          if (cell.getValue() == null) {
            cell.getPossibleValues().remove(value);
            debug("Possible values " + row1 + "," + col1 + "," + r2 + "," + c2 + ": " + cell.getPossibleValues());
            if (cell.getPossibleValues().isEmpty()) {
              return false;
            }
          }
        }
      }
    }
    return true;
  }
 
  private boolean updateRow(int row1, int col1, int row2, int col2, Integer value) {
    for (int c1 = 0; c1 < 3; c1++) {
      if (c1 != col1) {
        for (int c2 = 0; c2 < 3; c2++) {
          Cell cell = cells[row1][c1][row2][c2];
          if (cell.getValue() == null) {
            cell.getPossibleValues().remove(value);
            debug("Possible values " + row1 + "," + c1 + "," + row2 + "," + c2 + ": " + cell.getPossibleValues());
            if (cell.getPossibleValues().isEmpty()) {
              return false;
            }
          }
        }
      }
    }
    return true;
  }
 
  private boolean updateColumn(int row1, int col1, int row2, int col2, Integer value) {
    for (int r1 = 0; r1 < 3; r1++) {
      if (r1 != row1) {
        for (int r2 = 0; r2 < 3; r2++) {
          Cell cell = cells[r1][col1][r2][col2];
          if (cell.getValue() == null) {
            cell.getPossibleValues().remove(value);
            debug("Possible values " + r1 + "," + col1 + "," + r2 + "," + col2 + ": " + cell.getPossibleValues());
            if (cell.getPossibleValues().isEmpty()) {
              return false;
            }
          }
        }
      }
    }
    return true;
  }
 
  private Choice chooseValue(int size) {
    for (int row1 = 0; row1 < 3; row1++) {
      for (int col1 = 0; col1 < 3; col1++) {
        for (int row2 = 0; row2 < 3; row2++) {
          for (int col2 = 0; col2 < 3; col2++) {
            Cell cell = cells[row1][col1][row2][col2];
            if (cell.getValue() == null && cell.getPossibleValues().size() == size) {
              Integer value = (Integer)cell.getPossibleValues().iterator().next();
              debug("Choosing " + value + " from " + cell.getPossibleValues());               
              return new Choice(row1, col1, row2, col2, value, cell.getPossibleValues());
            }
          }
        }
      }
    }
    return null;
  }
   
  private Choice chooseNextValue(Choice chosen) {
    chosen.choices.remove(chosen.value);
    chosen.value = (Integer)chosen.choices.iterator().next();
    debug("Choosing next " + chosen.value + " from " + chosen.choices);
    return chosen;
  }

  private void setValue(int row1, int col1, int row2, int col2, Integer value) {
    Cell cell = cells[row1][col1][row2][col2];
    cell.setValue(value);
    debug("Value set " + row1 + "," + col1 + "," + row2 + "," + col2 + ": " + value);               
  }

  private void unsetValue(int row1, int col1, int row2, int col2) {
    Cell cell = cells[row1][col1][row2][col2];
    Integer value = cell.getValue();
    cell.setValue(null);
    debug("Value unset " + row1 + "," + col1 + "," + row2 + "," + col2 + ": " + value);               
  }
 
  private static void debug(String s) {
    if (DEBUG) {
      System.out.println(s);
    }
  }
 
  public static void main(String[] args) {
    Sudoku sudoku = new Sudoku();
    sudoku.show();
    System.exit(0);
  }
 
  private static class Choice {
    int row1;
    int col1;
    int row2;
    int col2;
    Integer value;
    Set choices;
       
    Choice(int row1, int col1, int row2, int col2, Integer value, Set choices) {
      this.row1 = row1;
      this.col1 = col1;
      this.row2 = row2;
      this.col2 = col2;
      this.value = value;
      this.choices = choices;
    }
  }
}

//---------------- File Cell.java ------------------

import java.awt.Color;
import java.awt.Dimension;
import java.util.HashSet;
import java.util.Set;

import javax.swing.JTextField;

public class Cell extends JTextField {
 
  private boolean inputEnabled = true;
  private Integer value;
  private Set possibleValues;
 
  Cell() {
    setHorizontalAlignment(JTextField.CENTER);
    setPreferredSize(new Dimension(20, 22));
   
    possibleValues = new HashSet(9);
    for (int i = 1; i < 10; i++) {
      possibleValues.add(new Integer(i));
    }
    showValue();
  }
   
  private void showValue() {
    setForeground(isValuePossible(value) ? Color.BLACK : Color.RED);
    String text = value == null ? "" : value.toString();
    setText(text);
  }

  void setInputEnabled(boolean b) {
    inputEnabled = b;
    setEnabled(b);
  }
 
  void setValue(Integer value) {
    this.value = value;
    showValue();
  }
 
  Integer getValue() {
    if (inputEnabled) {     
      String text = getText();
      if (text.length() > 0) {
        try {
          value = new Integer(text);
        } catch (NumberFormatException x) {
          value = new Integer(99);
        }
      } else {
        value = null;
      }
      showValue();
    }
    return value;
  }

  Set getPossibleValues() {
    return possibleValues;
  }
   
  boolean isValuePossible(Integer value) {
    return value == null || possibleValues.contains(value);
  }
}
swaczin
 
Posts: 1
Joined: 23 January 2006

Return to Software