Sudoku generator: Allgemeine Frage zu Sudoku-Zusammenhängen.

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Montag 27. November 2006, 19:52

Ich habe mich an einem Sudoku Generator geübt.
Er ist noch nicht ganz fertig. Es gibt ja zwei Regeln beim Sudoku:

1. In jeder Zeile und Spalte kommt jede Zahl zw. 1 und 9 genau einmal vor. (Schon implementiert!)
2. In jedem der 9 Teilquadrate kommt jede Zahl zw. 1 und 9 genau einmal vor. (Nächster Schritt)

Ich will es wirklich alleine lösen, daher bitte _KEINE_ Codesamples geben.

Alles was ich fragen wollte ist, angenommen ich habe 1. schon korrekt implementiert,
gibt es dann im Anschluss eine Art logischen Zusammenhang, wie man im Anschluss effizient 2. erfüllen kann?

Ist es mathematisch (oder wie auch immer) bewiesen, dass jedes Sudoku dass 1. genügt,
durch einfaches Tauschen der Zeilen (oder sonstwie "effizient") in ein Sudoku überführt werden kann,
dass auch 2. erfüllt? (Also ein _richtiges_ Sudoku)

Hier mein Code so far:
(Update vom 28.11.06 12:41 GMT+0)

Code: Alles auswählen

#!/usr/bin/python

import random

def newline():
	line = range(1,10)
	random.shuffle(line)
	return line

def valid_sudoku():
	return rowscols_check() #and squares_check():

def rowscols_check():
	aset = set()
	for col in xrange(len(sudoku[0])):
		aset.clear()
		for row in xrange(len(sudoku)):
			aset.add(sudoku[row][col])
		if len(aset) < len(sudoku):
			return False
	return True

def squares_check():
	return True #not implemented yet, always True

sudoku = [newline()]

while len(sudoku) < 9:
	sudoku.append(newline())
	if valid_sudoku():
		continue
	else:
		sudoku.remove(sudoku[-1])

return sudoku

Zuletzt geändert von akis.kapo am Dienstag 28. November 2006, 13:41, insgesamt 6-mal geändert.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Montag 27. November 2006, 21:36

akis.kapo hat geschrieben:Alles was ich fragen wollte ist, angenommen ich habe 1. schon korrekt implementiert,
gibt es dann im Anschluss eine Art logischen Zusammenhang, wie man im Anschluss effizient 2. erfüllen kann?
Ich bin mir ziemlich sicher, dass das nicht der Fall ist. Bin aber zu Müde, ein Gegenbeispiel zu finden.
Aber

Code: Alles auswählen

1 2 3  4 5 6  7 8 9
2 3 4  5 6 7  8 9 1
3 4 5  6 7 8  9 1 2

4 5 6  7 8 9  1 2 3
5 6 7  8 9 1  2 3 4
6 7 8  9 1 2  3 4 5

7 8 9  1 2 3  4 5 6
8 9 1  2 3 4  5 6 7
9 1 2  3 4 5  6 7 8
halte ich für einen guten Gegenbeispiels-Kandidaten.
BlackJack

Montag 27. November 2006, 21:46

akis.kapo hat geschrieben:1. In jeder Zeile und Spalte kommt jede Zahl zw. 1 und 9 genau einmal vor. (Schon implementiert!)
2. In jedem der 9 Teilquadrate kommt jede Zahl zw. 1 und 9 genau einmal vor. (Nächster Schritt)

Ich will es wirklich alleine lösen, daher bitte _KEINE_ Codesamples geben.
Verbesserungsvorschläge die den Stil betreffen bekommst Du aber trotzdem. :P
Alles was ich fragen wollte ist, angenommen ich habe 1. schon korrekt implementiert,
gibt es dann im Anschluss eine Art logischen Zusammenhang, wie man im Anschluss effizient 2. erfüllen kann?

Ist es mathematisch (oder wie auch immer) bewiesen, dass jedes Sudoku dass 1. genügt,
durch einfaches Tauschen der Zeilen (oder sonstwie "effizient") in ein Sudoku überführt werden kann,
dass auch 2. erfüllt? (Also ein _richtiges_ Sudoku)
Einen Beweis hätte ich jetzt nicht, aber vom Bauchgefühl her würde ich sagen, einfaches Zeilenvertauschen dürfte nicht immer möglich sein wenn 1. erfüllt ist. Man könnte ein Programm schreiben, welches ein "Sudoku" nimmt, das 1. erfüllt und versucht die Zeilen in eine Reihenfolge zu bringen, das auch 2. erfüllt wird. Wenn man eins findet, bei dem das nicht möglich ist, hat man den Beweis das Zeilentauschen nicht immer zum Erfolg führt.

Zum Quelltext: Steck am besten alles in Funktionen, also auch das erzeugen des "fast-Sudokus" und übergib das Sudoku als Argument.

Zwei Änderungsvorschläge für die vorhandenen Funktionen:

Code: Alles auswählen

def is_valid_sudoku(sudoku):
    return rowscols_check(sudoku) and squares_check(sudoku)

def rowscols_check(sudoku):
    for column_number in xrange(len(sudoku[0])):
        numbers = set()
        for row in sudoku:
            numbers.add(row[column_number])
        if len(numbers) < len(sudoku):
            return False
    return True
`is_valid_sudoku()` ist so etwas kürzer und klarer und die Testfunktion vermeidet in der inneren Schleife den Index und geht direkt über die Zeilen. Die Ausnahmebehandlung habe ich nicht so ganz verstanden. Und die würde auch greifen falls Du einen Tippfehler bei einem Namen gemacht hättest. Das ist dann schwer zu finden. Bei ``except`` sollte man immer eine konkrete Ausnahme angeben.
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Dienstag 28. November 2006, 11:03

Du hast recht. Wäre ja auch einfach wenn man durch einfaches Tauschen immer ein richtiges Sudoku hinbekommt.
Ich dachte nur vielleicht kann ich "abkürzen" und ausserdem gibts ja zu Hauf sudoku generatoren... nur ein Algorithmus ist mir nicht bekannt.

Mein Ansatz bleibt da Brute Force, nur nicht auf einmal, sondern Zeilenweise.
BlackJack

Dienstag 28. November 2006, 11:22

Hm geh' doch einfach alle Möglichkeiten der Belegung der Felder durch und filtere die, die Sudokus sind raus. Brauchst ja nur 5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000 mögliche Felder testen. :lol:

Edit: Wenn Du aber ein gültiges Sudoku gefunden hast, dann kannst Du durch Zeilen/Spalten vertauschen andere gültige Sudokus erzeugen. Du kannst die 3 Zeilen/Spalten in jedem Block beliebig vertauschen und auch die Blöcke selbst "zeilen-" und "spaltenweise" vertauschen ohne die Bedingungen zu verletzen.
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Dienstag 28. November 2006, 11:44

Ähm? Sind das wirklich so viele? Falls ja, bitte Rechnung/Beleg/Seite/Quelle mal angeben.
Oder hast nur wild auf die Tastatur getippt um damit auszudrücken: "Es sind wirklich viele Möglichkeiten."?

Code wurde auf deinen Wunsch hin verschönert.
BlackJack

Dienstag 28. November 2006, 13:01

Äh, nein es sind ein paar weniger, ich hatte einfach 81! angenommen, aber die Werte sind ja nicht alle paarweise verschieden. :oops:

Man wählt für jedes Kästchen aus 9 möglichen Ziffern aus, also sind es nur 196627050475552913618075908526912116283103450944214766927315415537966391196809 Möglichkeiten.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Dienstag 28. November 2006, 16:41

akis.kapo hat geschrieben:Ähm? Sind das wirklich so viele? Falls ja, bitte Rechnung/Beleg/Seite/Quelle mal angeben.
Oder hast nur wild auf die Tastatur getippt um damit auszudrücken: "Es sind wirklich viele Möglichkeiten."?
Zumindest hätte er am Schluss sehr einseitig getippt. Andererseits ist es Schulwissen, dass Fakultäten mit einer bestimmten Anzahl Nullen enden müssen.

Gut, dass Python lange Integers beherrscht, denn damit muss man nicht wild auf der Tastatur herumtippen. ;)
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Dienstag 28. November 2006, 22:01

BlackJack hat geschrieben:Man wählt für jedes Kästchen aus 9 möglichen Ziffern aus, also sind es nur 196627050475552913618075908526912116283103450944214766927315415537966391196809 Möglichkeiten.
Die Anzahl aller Sodukus ist übrigens 6,670,903,752,021,072,936,960. Das ist aber nichttrivial zu errechnen.
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Mittwoch 6. Dezember 2006, 10:42

Es scheint Probleme mit meiner Annahme zu geben,
da ich keinen Fehler im Programm erkennen kann, oder etwa ihr?

Code: Alles auswählen

#!/usr/bin/python

import random

def newline():
	line = range(1,10)
	random.shuffle(line)
	return line

def show():
	for i in sudoku: print i

def valid_sudoku():
	return rowscols_check() and squares_check()

def rowscols_check():
	aset = set()
	for col in xrange(9):
		for row in xrange(len(sudoku)):
			aset.add(sudoku[row][col])
		if len(aset) < len(sudoku):
			return False
		aset.clear()
	return True

def squares_check():
	aset, bset, cset = set(), set(), set()
	for i in xrange(3):
		for row in sudoku[i*3:i*3+3]:
			for j in xrange(3):
				for s in [aset,bset,cset]:
					for e in row[j*3:j*3+3]:
						s.add(e)
		cursize = len(sudoku[i*3:i*3+3])
		for s in [aset,bset,cset]:
			if len(s) < 3*cursize:
				return False
		for s in [aset,bset,cset]:
			s.clear()
	return True

sudoku = [newline()]
s, f, l = 0, 0, 0
scala = 500000
while len(sudoku) < 9:
	sudoku.append(newline())
	if valid_sudoku():
		s += 1
		print "Successes: ", s
	else:
		sudoku.remove(sudoku[-1])
		f += 1
		if f % scala == 0:
			l += 1
			print "Failures: ", l, " x ", scala

return sudoku
Also entweder man muss wirklich ewig warten, oder ewig viele Versuche machen,
oder meine Annahme, dass man ein Sudoku zeilen-, statt elementenweise erzeugen kann ist nicht (in allen Fällen) richtig (,ergo nicht richtig).

Oder was meint ihr?

Nochmal zur Erinnerung:

Ich generiere eine zufällige Zeile nach der anderen und teste sie anschliessend auf "Sudoku-komformität". Falls sie "sudoku" ist behalte ich sie und generiere die nächste Zeile, sonst lösche ich die jeweils zuletzt generierte Zeile.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Mittwoch 6. Dezember 2006, 11:15

(Edit: Ich habe nicht gesehen, dass bereits nach jeder Zeile getestet wird; dieser Post bezieht sich also auf einen vollkommen naiven Ansatz)

Dein Verfahren ist theoretisch korrekt; allerdings nicht praktikabel:

Anzahl aller Sudokus / Anzahl aller Möglichkeiten, 9 Mal eine Permutation von 1-9 untereinanderzuschreiben =

6670903752021072936960. / ( (9*8*7*6*5*4*3*2) ** 9) = 6.11e-27 %

Die Wahrscheinlichkeit, durch Zufall ein Sudoku zu erzeugen, ist also verschwindend gering. Im Mittel brauchst du

1 / 6.11e-29 = 16.356.207.865.015.924.928.173.174.845 Versuche.

(Alle Angaben ohne Gewähr)

Du musst also schon etwas intelligenter rangehen; Stichwort Backtracking: immer irgendwo eine Zahl eintragen und Testen, geht das nicht, andere Zahl benutzen, geht keine, einen Schritt zurück und dort andere Zahl versuchen. Das ganze kann man dann natürlich noch intelligenter gestalten.
Zuletzt geändert von Joghurt am Mittwoch 6. Dezember 2006, 11:38, insgesamt 1-mal geändert.
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Mittwoch 6. Dezember 2006, 11:25

Mmh. Dadurch, dass akis.kapo zeilenweise vorgeht, muss bei den ersten Zeilen noch nicht solange "gesucht" werden. Der Algorithmus ist also schon etwas besser als wenn man das komplette Sudoku befuellt und danach erst checkt, ob es ein gueltiges ist. Bei mir dauert der Durchlauf des Programmes auch gar nicht so lange, allerdings scheint der Squares-Check nicht in Ordnung zu sein:

[9, 3, 5, 7, 2, 6, 8, 4, 1]
[8, 7, 1, 3, 6, 2, 4, 5, 9]
[1, 2, 6, 8, 3, 4, 5, 9, 7]
[3, 8, 4, 1, 9, 5, 2, 7, 6]
[7, 1, 2, 4, 8, 3, 9, 6, 5]
[5, 9, 3, 6, 4, 7, 1, 8, 2]
[6, 5, 8, 2, 7, 9, 3, 1, 4]
[2, 4, 7, 9, 5, 1, 6, 3, 8]
[4, 6, 9, 5, 1, 8, 7, 2, 3]

Leider ist die entspr. Funktion nicht sonderlich leicht zu verstehen.

(Warum steht in der letzten Zeile des gesamten Codes ein return???)
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Mittwoch 6. Dezember 2006, 11:54

Hmmm... wie lange musstest du auf diese 9 Zeilen warten?

Ich bin nie über 7 Zeilen hinausgegangen. Auf 7 erfolgreich erzeugte Zeilen folgten immer abermillionen Fehlversuche, bis ich abgebrochen habe.

Daher konnte ich auch nie das Ergebnis bestaunen, aber wenn dein Sudoku die Ausgabe meines Programms ist,
dann stimmt die squares_check() Funktion nicht und das Sudoku ist vollkommen falsch.
So war das natürlich nicht gedacht von mir.

Die Square_check() Funktion überprüft alle 9 9x9 Quadrate.
Für jedes Quadrat erzeuge ich ein set() und füge die Elemente des Quadrats in die sets.
aset = alle 3 Quadrate der 1. "Spalte"
bset = alle 3 Quadrate der 2. "Spalte"
cset = alle 3 Quadrate der 3. "Spalte"
Am Ende einer Befüllung überprüfe ich die Anzahl der Elemente im set.
Ist diese kleiner als die Anzahl der Elemente im Quadrat, bedeutet das, dass sich eine oder mehrere Zahlen wiederholt haben, ergo kann es kein Sudoku mehr sein, da in jedem Quadrat alle Zahlen vorkommen müssen und die Anzahl der Elemente im set immer = der Anzahl der Elemente im Quadrat sein muss, nicht geringer.
Der einzige Grund wieso ich nicht set() < 9 abfrage ist, dass ich das Sudoku zeilenweise erzeuge, somit kann ein (gedachtes) Quadrat k*3 Elemente enthalten (0 < k < 4).

Hmm. Mein Algorithmus ist falsch implementiert.

Ich returne False, falls die Anzahl der Elemente im Set < #Elemente im Quadrat, sonst immer True.
Zuletzt geändert von akis.kapo am Mittwoch 6. Dezember 2006, 12:11, insgesamt 1-mal geändert.
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Mittwoch 6. Dezember 2006, 12:06

hier mal eine "aufgeschwämmte" version meiner squares_check():

Code: Alles auswählen

#!/usr/bin/python

def squares_check():
	aset, bset, cset = set(), set(), set()
	for row in sudoku[0:3]:
		for elem in row[0:3]:
			aset.add(elem)
		for elem in row[3:6]:
			bset.add(elem)
		for elem in row[6:9]:
			cset.add(elem)
	cursize = len(sudoku[0:3])
	for s in [aset,bset,cset]:
		if len(s) < 3*cursize:
			return False
	aset.clear()
	bset.clear()
	cset.clear()
	for row in sudoku[3:6]:
		for elem in row[0:3]:
			aset.add(elem)
		for elem in row[3:6]:
			bset.add(elem)
		for elem in row[6:9]:
			cset.add(elem)
	cursize = len(sudoku[3:6])
	for s in [aset,bset,cset]:
		if len(s) < 3*cursize:
			return False
	aset.clear()
	bset.clear()
	cset.clear()
	for row in sudoku[6:9]:
		for elem in row[0:3]:
			aset.add(elem)
		for elem in row[3:6]:
			bset.add(elem)
		for elem in row[6:9]:
			cset.add(elem)
	cursize = len(sudoku[6:9])
	for s in [aset,bset,cset]:
		if len(s) < 3*cursize:
			return False
	aset.clear()
	bset.clear()
	cset.clear()
	return True
PS: und wer sich fragt wie ich das so kurzfristig aufschwämmen konnte, dem sag ich nur: VIM rockt!
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Mittwoch 6. Dezember 2006, 12:25

der hier sagt "squares_check()" not defined.

Wo ist der Fehler:

Code: Alles auswählen

#!/usr/bin/python

import random

def newline():
	line = range(1,10)
	random.shuffle(line)
	return line

def rowscols_check():
	aset = set()
	for col in xrange(9):
		for row in xrange(len(sudoku)):
			aset.add(sudoku[row][col])
		if len(aset) < len(sudoku):
			return False
		aset.clear()
	return True

def squares_check():
    aset, bset, cset = set(), set(), set()
	for i in xrange(3):
		for row in sudoku[i*3:i*3+3]:
			for elem in row[0:3]:
				aset.add(elem)
			for elem in row[3:6]:
				bset.add(elem)
			for elem in row[6:9]:
				cset.add(elem)
		cursize = len(sudoku[i*3:i*3+3])
		for s in [aset,bset,cset]:
			if len(s) < 3 * cursize:
				return False
			s.clear()
    return True

sudoku = [newline()]
while len(sudoku) < 9:
	sudoku.append(newline())
	if not (rowscols_check() and squares_check()):
		sudoku.remove(sudoku[-1])

return sudoku
Zuletzt geändert von akis.kapo am Mittwoch 6. Dezember 2006, 12:49, insgesamt 2-mal geändert.
Antworten