Vorstellung: Sudoku - Solver

[Samuel72]

Hallo zusammen,

ich hab mal ein Programm geschrieben, welches Sudokus löst (ohne jede Strategie, einfach durch Ausprobieren) - vielleicht interessiert's ja jemand.

Wenn diese Art von Präsentation nicht erwünscht/am falschen Platz ist, bitte ich einen Moderator, sie zu löschen/verschieben.

package sudoku;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Component;
import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.GraphicsEnvironment;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.BorderFactory;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTable;
import javax.swing.SwingConstants;
import javax.swing.table.AbstractTableModel;
import javax.swing.table.TableCellRenderer;

@SuppressWarnings("serial")
public class Sudoku extends AbstractTableModel {
	static final int[] p2 = new int[] {1,2,4,8,16,32,64,128,256};
	int[] z = new int[81];
	int[] l = new int[81];
	boolean solved;
	JLabel status;
	
	class MyRenderer extends JLabel implements TableCellRenderer {
		public Component getTableCellRendererComponent(JTable arg0,
				Object obj, boolean sel, boolean foc, int r, int c) {
			setText(obj.toString());
			setHorizontalAlignment(SwingConstants.CENTER);
			setOpaque(true);			
			setBorder(foc?BorderFactory.createLineBorder(Color.darkGray):null);
			setBackground((r/3+c/3)%2==0?Color.lightGray:Color.white);
			return this;
		}		
	}
	class Zahlen {
		int[] z = new int[81]; // enthält den Inhalt der Kästchen (0 = leer)
		int[] w = new int[81]; // gibt an, welche Zahlen nicht mehr gehen, z.B. 25 = 2^(1-1) + 2^(3-1) + 2^(4-1): 1,3 u. 4 gehen nicht mehr.
		int sol;

		Zahlen(int[] za) throws Exception {
			for (int i=0; i<81; i++) {
				z[i] = za[i];
				if (z[i]!=0) {
					if ((w[i]&p2[z[i]-1])!=0)
						throw new Exception("Keine Lösung!");
					add(i,z[i]);
				}
			}			
		}		
		Zahlen(Zahlen za) {
			for (int i=0; i<81; i++) {
				z[i] = za.z[i];
				w[i] = za.w[i];
			}
			sol = za.sol;
		}		
		void add(int x, int i) {
			z[x] = i;
			while (sol<81 && z[sol]!=0)
				sol++;
			for (int k=0; k<9; k++) {
				w[x%9+k*9] |= p2[i-1];
				w[x/9*9+k] |= p2[i-1];
				w[x/27*27+(x%9)/3*3+k%3+k/3*9] |= p2[i-1];
			}
		}		
	}

	Sudoku() {
		JTable tab = new JTable(this);
		tab.setDefaultRenderer(String.class, new MyRenderer());
		status = new JLabel(" ");
		status.setForeground(Color.red);
		status.setHorizontalAlignment(SwingConstants.CENTER);
		JFrame f = new JFrame("Sudoku");
		f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
		Rectangle r = GraphicsEnvironment.getLocalGraphicsEnvironment().getMaximumWindowBounds();
		f.setLocation(r.width/2-82,r.height/2-125);
		f.getContentPane().add(tab,BorderLayout.NORTH);
		f.getContentPane().add(status,BorderLayout.CENTER);
		f.getContentPane().add(getButtons(),BorderLayout.SOUTH);
		f.setSize(new Dimension(180,230));
		f.setVisible(true);
	}
	JPanel getButtons() {
		JPanel res = new JPanel(new FlowLayout());
		JButton loes = new JButton("Lösen");
		loes.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				try {
					solved = false;
					solve(new Zahlen(z));
					if (!solved) 
						throw new Exception("Keine Lösung!");
					for (int i=0; i<81; i++)
						z[i] = l[i];
					fireTableDataChanged();
					status.setText(" ");
				} catch (Exception ex) {
					status.setText(ex.getMessage());
				}									
			}			
		});
		res.add(loes);
		JButton neu = new JButton("Neu");
		neu.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				z = new int[81];
				fireTableDataChanged();
				status.setText(" ");
			}			
		}); 
		res.add(neu);
		return res;
	}	
	void solve(Zahlen zz) throws Exception {
		if (zz.sol==81) {
			if (!solved) {				
				solved = true;
				for (int i=0; i<81; i++)
					l[i] = zz.z[i];
			} else throw new Exception("Nicht eindeutig!");			
		} else {
			int i=zz.sol; while (zz.z[i]!=0) i++;
			for (int k=1; k<=9 ; k++) if ((zz.w[i]&p2[k-1])==0) { 
				Zahlen zan = new Zahlen(zz);
				zan.add(i,k);
				solve(zan);
			}
		}		
	}

	public static void main(String[] args) {
		new Sudoku();
	}
	// Methoden von TableModel

	public int getColumnCount() { 
		return 9;
	}
	public int getRowCount() {
		return 9;
	}	
	public boolean isCellEditable(int r, int c) {
		return true;
	}	
	public Class<?> getColumnClass(int c) {
		return String.class;
	}
	public Object getValueAt(int r, int c) {
		return z[r*9+c]==0?"":String.valueOf(z[r*9+c]);		
	}
	public void setValueAt(Object obj, int r, int c) {
		int zn=0;
		try {
			zn = Integer.parseInt((String)obj);
			if (zn<0 || zn>9)
				zn = 0;				
		} catch (Exception ex) {
			zn = 0;
		}
		z[r*9+c] = zn;				 		
	}
}

Und eine Frage hätte ich doch noch: Ich habe die 3x3 - Kästchen durch verschiedene Hintergrundfarben abgegrenzt. Kennt jemand eine einfache Möglichkeit, in der JTable die Zellenwände verschieden dick zu machen?

LG Samuel

 

[ifboolean]

Ein Programm, das Sudokus löst - interessant! Welchen Algorithmus hast du eingesetzt, um die Lösung zu berechnen? Was passiert bei mehreren möglichen Lösungen? Mit welchem Design wurde das GUI entworfen?

 

[Samuel72]

Der Algorithmus steht auf Zeilen 123-138.
Es handelt sich um einfaches Ausprobieren sämtlicher möglicher Kombinationen (rekursiv).
Sobald eine zweite Lösung gefunden wird, wird eine Exception geworfen.