You are not logged in.

  • Login

Java: Sudoku

myabba|abra

Sage

  • "myabba|abra" started this thread

Posts: 4,305

Location: Regensburg

Occupation: GER

  • Send private message

1

Monday, July 3rd 2006, 6:58pm

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

Sage

Posts: 4,172

Occupation: GER

  • Send private message

2

Monday, July 3rd 2006, 7:23pm

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.

This post has been edited 1 times, last edit by "Sheep" (Jul 3rd 2006, 7:36pm)

myabba|abra

Sage

  • "myabba|abra" started this thread

Posts: 4,305

Location: Regensburg

Occupation: GER

  • Send private message

3

Monday, July 3rd 2006, 7:40pm

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

Sage

Posts: 4,172

Occupation: GER

  • Send private message

4

Monday, July 3rd 2006, 8:21pm

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...

Source code

 
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.