Sie sind nicht angemeldet.

  • Anmelden

Java: Sudoku

myabba|abra

Erleuchteter

  • »myabba|abra« ist der Autor dieses Themas

Beiträge: 4 305

Wohnort: Regensburg

Beruf: GER

  • Nachricht senden

1

03.07.2006, 18:58

Java: Sudoku

Hi,
ein Freund von mir stresst sich grade ziemlich wegen Programmieren II.
Er soll in Java ein Sudoku programmieren und bekommts ned auf die Reihe. Freitag ist Abgabe.. er hat schon zig Arbeitsstunden investiert, aber bekommt einen "Backtracking Algorithmus" (was auch immer das ist) nicht hin.

Ein wenig Hilfe wäre sicher nett. Ich biete ein paar Neteller $ ;)

Sheep

Erleuchteter

Beiträge: 4 172

Beruf: GER

  • Nachricht senden

2

03.07.2006, 19:23

Hat er sich schon...

http://de.wikipedia.org/wiki/Sudoku#Erstellung_neuer_Sudokus

...angeschaut? Der dritte Weg ist ohne Backtracking - oder ist der Ansatz Pflicht?

EDIT: Ahja, da war noch was... Habe mich schon mal mit dem Thema beschäftigt, es gibt ein Problem mit der Verschiebung in jeder Zeile. Selbst wenn in jeder Zeile eine andere Folge steht, muss das Sudoku nicht gültig sein. Folgende Variante funzt aber...

123456789
789123456
456789123
912345678
678912345
345678912
891234567
234567891

Zum Beginn brauchst du nur irgendeine, lohnt sich also nicht, jetzt die Menge aller gültigen Varianten herzuleiten.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Sheep« (03.07.2006, 19:36)

myabba|abra

Erleuchteter

  • »myabba|abra« ist der Autor dieses Themas

Beiträge: 4 305

Wohnort: Regensburg

Beruf: GER

  • Nachricht senden

3

03.07.2006, 19:40

erreiche ihn grade nicht, aber ich vermute, dass der backtracking pflicht ist, da sie den algorithmus in einer vorlesung hatten (die er verpennt hat ._.)

Sheep

Erleuchteter

Beiträge: 4 172

Beruf: GER

  • Nachricht senden

4

03.07.2006, 20:21

Ok, ich nehme mal den zweiten Weg.

Auf jeden Fall braucht man eine Methode, die checkt, ob das Feld gültig ist (keine gleichen Ziffern in Zeile, Spalte und / oder Block). Ich tauf sie mal isOK, sie kriegt als Parameter immer das ganze Feld und gibt entweder false oder true zurück, also einen boolean.

Pseudo-Code...

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

boolean isOK(feld) {...}

boolean setDigit(feld, ziffer, position)
{
	setze ziffer an position ins feld
	wenn nicht isOK(feld) return false
	ansonsten
	{
		führe aus
		{
			ändere ziffer, falls nötig
			ändere position
		} (solange !setDigit(feld, ziffer, position) // Backtrack

		return true
	}
}

main()
{
	setDigit(neues Feld, 1, irgendwo)
	gib feld aus
}


Ich bin eigentlich der Meinung, dass man immer nur einen Schritt zurückgehen ("backtracken") muss, kann aber sein, dass man damit irgendwann in eine Sackgasse gerät.