Sudoku-Generator

CDW

0
Mitarbeiter
Eingereicht von Ook!
Schwierigkeit 2:
Passend zur Sudoku-Solver Aufgabe soll nun ein Sudoku-Generator geschrieben werden.
Es soll hier um Schnelligkeit gehen, deshalb erstellen wir 50 Sudokus und ermitteln daraus einen Durchschnittswert für ein Sudoku!
Da man allerdings die konkrete Laufzeit nur schlecht vergleichen kann (Core2Quad vs. Pentium3 oder TurboC vs Intel Compiler, Mono vs "original" Framework usw) wollen wir keinen ***Vergleich im Millisekundenbereich anstellen ;). Wer mag, kann die Performance angeben - dann aber bitte mit weiteren Details (Framework/Compiler/Rechnerausstattung).
 
Auf eine Geschwindigkeitsangabe habe ich bewusst verzichtet, da die Klasse Random verwendet wird und dadurch hauptsächlich die Geschwindigkeit beeinflusst wird. Die Komplexität kann sich ja jeder selbst ausrechnen, sollte nicht allzuschwer sein.

Besonders elegant ist sie desweiteren auch nicht, verzeiht mir bitte das, es ist nunmal schon kurz nach 2 uhr ;)

Achja.. TODO und so: Auf das Enfernen einzelner Felder habe ich auch noch verzichtet, eventl. implementiere ich das noch irgendwann ;) Aber das sollte ja auch jeder selbst können, z.b. mit einer Funktion emptyCell(int i,int j) innerhalb der Matrix-Klasse.

Code:
import java.util.Random;

public class SudokuGen {

	static class Matrix<T> {
		private T[][] matrix;
		private int linePointer=0;
		public Matrix(T[][] matrix) { 
			this.matrix=matrix;			
		}
		public void add(T[] row) {
			this.matrix[linePointer] = row;
			linePointer++;
		}
		public void switchRows(int i,int j) {
			T[] tmp = this.matrix[i];
			this.matrix[i] = this.matrix[j];
			this.matrix[j] = tmp;
		}
		public void switchCols(int i,int j) {
			T tmp = null;
			for(int x=0;x<matrix.length;x++) {
				tmp = this.matrix[x][i];
				this.matrix[x][i] = this.matrix[x][j];
				this.matrix[x][j] = tmp;
			}
		}
		public void print() {
			for(int i=0;i<10;i++)System.out.print("----");
			System.out.println();
			for(int i=0;i<matrix.length;i++) {
				System.out.print("|| ");
				for(int j=0;j<matrix[i].length;j++) {
					if((j+1)%3==0)System.out.print(matrix[i][j]+" || ");
					else System.out.print(matrix[i][j]+" | ");
				}
				System.out.println();
				if((i+1)%3==0) {
					for(int x=0;x<10;x++)System.out.print("----");
					System.out.println();
				}
			}
		}
	}

	public static void main(String[] args) {
		Matrix<Integer> field=new Matrix<Integer>(new Integer[9][9]);
		Integer[] row = {1,2,3,4,5,6,7,8,9};
		Random zufall=new Random();
		
		// (1) Add initial line
		field.add(row);
		
		// (2) Fill field with values
		for(int i=1;i<9;i++) {
			row=(i%3==0)?shiftInteger(row,4):shiftInteger(row,3);
			field.add(row);
		}
		
		// (3) Mix it, baby
		for(int i=0;i<zufall.nextInt(1000);i++) {
			int nextInt = zufall.nextInt(9);
			field.switchCols(nextInt, calcNextInt(nextInt,zufall));
			nextInt = zufall.nextInt(9);
			field.switchRows(nextInt, calcNextInt(nextInt,zufall));
		}
		
		// (4) I know you wanne print that...
		field.print();
	}
	
	private static int calcNextInt(int nextInt, Random zufall) {
		switch(nextInt%3) {
		case 0:
			return nextInt+zufall.nextInt(3);
		case 1: 
			int sign=(zufall.nextInt(10)>5)?-1:1;
			return nextInt+sign*zufall.nextInt(2);
		case 2: 
			return nextInt-zufall.nextInt(3);
		}
		return 0;
	}
	
	private static Integer[] shiftInteger(Integer[] arr,int shift) {
		Integer[] newRow = new Integer[9];
		for(int i=0,j=shift;i<9;i++,j++) {
			if(j==9)j=0;
			newRow[i] = arr[j];
		}
		return newRow;
	}

}
 
Zurück
Oben