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);
}
}
