[GELÖST] Levelgenerator Sudoku - Algorithmus?

Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Neue Antwort erstellen

 

CO2

ehemals "SirMO"

Betreff: [GELÖST] Levelgenerator Sudoku - Algorithmus?

BeitragMi, Feb 13, 2013 20:35
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,
ich versuche mich gerade an einem Generator für ein Sudoku-Level. Der Generator soll ein Sudoku-Level nach den bekannten Sudoku-Regeln erstellen. Dazu habe ich mir eine Klasse TSudoku erstellt, welche alle benötigten Funktionen und Variablen enthält BlitzMax: [AUSKLAPPEN]
Type TSudoku
Field Data:Int[9, 9]

Method CreateGame(DiffLevel:Int = 0)
Local x:Int
Local y:Int
Local z:Int
Local a:Int

For x = 1 To 9
For y = 0 To 8
Local Test:Int = 1
While(Test <> 0)
z = Rand(0, 8)
a = Rand(0, 8)
Test = 0
Test = Test + Self.CheckValueIsInRow(z, x, 8)
Test = Test + Self.CheckValueIsInCol(a, x, 8)
Test = Test + Self.Data[z, a]
Wend
Self.Data[z, a] = x
Next
Next

Select DiffLevel
Case 0 'Einfach
Case 1 'Mittel
Case 2 'Schwierig
End Select
End Method

Method GetValueAtPos:Int(PosX:Int, PosY:Int)
Return Self.Data[PosX, PosY]
End Method

Method CheckValueIsInRow:Int(Row:Int, Value:Int, Size:Int)
For Local x:Int = 0 To Size
If(Self.Data[Row, x] = Value)
Return 1
EndIf
Next
Return 0
End Method

Method CheckValueIsInCol:Int(Col:Int, Value:Int, Size:Int)
For Local x:Int = 0 To Size
If(Self.Data[x, Col] = Value)
Return 1
EndIf
Next
Return 0
End Method
End Type


Zur Erklärung:
- Field Data:Int[9, 9]: Dies ist das Spielfeld später
- Method CreateGame(DiffLevel:Int): Dies ist der Spielfeld-Generator, später muss eigentlich noch überprüft werden, ob sich die Zahl in einem Block befindet, sowie der Schwierigkeitsgrad (DiffLevel) muss noch umgesetzt werden.
- Method GetValueAtPos:Int(PosX:Int, PosY:Int): Diese Funktion liefert den Wert an Position X, Y zurück
- Method CheckValueIsInRow:Int(Row:Int, Value:Int, Size:Int): Diese Funktion liefert 0 zurück, sollte der angegebene Wert nicht in der angegebenen Reihe vorkommen, sonst 1. Size ist die Angabe der Spielfeldgröße (Für eventuelle Spielvariationen)
- Method CheckValueIsInCol:Int(Col:Int, Value:Int, Size:Int): Diese Funktion liefert 0 zurück, sollte der angegebene Wert nicht in der angegebenen Spalte vorkommen, sonst 1. Size ist die Angabe der Spielfeldgröße.

Das Problem ist: Wenn ich ein Sudoku erstellen will mit BlitzMax: [AUSKLAPPEN]
Global Sudoku:TSudoku = New TSudoku
Sudoku.CreateGame()

Benötigt der Generator unheimlich lange... Ich weiß aber auch nicht, wie ich die Regeln anders Abfragen soll (Das überprüfen, ob die Zahl sich bereits in einem Block befindet ist noch gar nicht umgesetzt).
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti
  • Zuletzt bearbeitet von CO2 am Mi, Feb 13, 2013 22:14, insgesamt einmal bearbeitet
 

BBPro2

BeitragMi, Feb 13, 2013 21:02
Antworten mit Zitat
Benutzer-Profile anzeigen
erste unausgereifte idee, wie mans dann im endeffekt umsetzt müsste man sich noch gut überlegen:

es gibt einen "pool" von zahlen für jedes feld, die das feld noch annehmen kann -
genau genommen gibt es sogar 3 pools pro feld

einmal (zu anfang) die zahlen 1-9 für die jeweilige reihe, dann für die spalte und für den block

dann wird feld für feld "gefüllt"
zur verfügung stehen nur zahlen, die in der schnittmenge der 3 zugehörigen pools liegt
daraus wird eine zufällig gewählt

sollte keine zahl mehr in frage kommen (leere schnittmenge) benötigst du backtracking (teuer, aber da wird man wohl nicht drumrum kommen, bei keinem ansatz - denke ich zumindest)

am ende hast du ein zufälliges, fertiges sudokufeld

danach musst du schritt für schritt zahlen "entfernen", die sich nach den regeln ableiten ließen.
das ist zwar viel arbeit, aber eigentlich relativ einfach zu implementieren denke ich.

klingt kompliziert, ist es vermutlich auch - zumindest komplizierter als die meisten anfangs denken würden, wenn man sagt "ich mach mal nen sudoku generator"

sollte es einfachere lösungen geben: nur her damit, würde mich interessieren

Xeres

Moderator

BeitragMi, Feb 13, 2013 21:18
Antworten mit Zitat
Benutzer-Profile anzeigen
Es gibt schon einige Sudoku Generatoren im Forum, da kann man sich bestimmt etwas abschauen.
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Tennisball

BeitragMi, Feb 13, 2013 21:34
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,

Zur Idee von BBPro2 gibt es diesen Link: Link

Dort ist das ganze noch etwas genauer beschrieben und erklärt. Am Ende ist der Algorithmus auch ziemlich schnell. Wink

Viel Spaß.

Gruß,
Tennisball
 

CO2

ehemals "SirMO"

BeitragMi, Feb 13, 2013 22:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Vielen Dank für die Antworten!

Werde mal dem Link nachgehen und schauen was sich draus entwickelt Wink

Sollte ich den Code in BlitzMax übersetzen poste ich ihn natürlich... solange ist das Thema als [GELÖST] getaggt.
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group