Felder für eine Art Minisodoku automatisch füllen

  • GM 8

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Felder für eine Art Minisodoku automatisch füllen

    Tach!
    Lange einiger zeit melde ich mich mal zurück und hab auch gleich eine Frage, an der ich mir schon eine Weile die Zähne ausbeisse.
    ich habe eine Minispiel im Spiel, das ähnlich wie ein Minisodoku funktioniert. Es besteht aus 4 x 4 Felden, die in einer Reihe und in einer Spalte jeweils Nur die Zahlen 1 - 4 enthalten dürfen. Nu is auch schon alles feritg und funzt gut.
    Das Problem: Ich bekomme es einfach nicht gebacken die felder automatisch zu generieren. Ich habe ein Arry angelegt mitdem namen field_numb[x} das von 0 bis 15 geht und die Zahlen der Felder enthält (oben links fängts an). Wie kann ich dies mit den Zahlen füllen, die regulär erlaubt sind?
    Jemand von den Mathe-Cracks ne idee?
    Battle Command - WeltraumEchtzeitStrategie | Meine GM Spiele auf Box.net
    GCM/FA/O d-(--)@>---xpu s-:- !a C++$@ U- P L+ E W++ N o K-- w++ O? M V PS PE-- Y PGP t 5 X R+++ tv+ b DI D G e+ h? r-- x
  • ich glaub nicht das man sudoku exact berechnen kann.
    wenn dann müsste man irgendwo zufällig anfangen und von da aus drauf zufällig weitermachen.

    natürlcih darf der generator nur weitermachen, wenn seine ausgewählte zahl den regeln enspricht.

    stell dir den zufall in einem baum diagramm vor, dein egerator wählt siich einen ast aus, und geht hinein bis es ncihtmehr geht, falls nicht alle felder ausgefüllt sind, geht er einen zug zurück und probiert so oft weiter bis er einen weg egfunden hat. Problem hierbei ist das er jeden schon abgeganngenen 'ast' speichern muss um nicht nochmal reinzugehn.

    alternatiev könntest du ihn jedes mal von anfang an neu generieren lassen.

    Beide methoden brauchen viel rechen power und zeit, vorprogramierte rätsel sind dabei noch die beste lösung.

    tipp: nutzt ein ds grid oder 2d array x[y,z], ist übersichtlicher
  • Meinst du en.wikipedia.org/wiki/Latin_square?

    Wenn ja, dann würde ich eine der folgenden beiden Methoden verwenden (kann man aber auch auf Sudoku übertragen):
    1. Ein rekursiver Ansatz mit Backtracking: Du fängst mit dem oberen linken Feld an und belegst es mit einer zufälligen Zahl. Danach machst du einen rekursiven Aufruf für das nächste Feld (rechts daneben) und belegst dieses mit einer zufälligen Zahl unter den noch zulässigen, d.h. eine Zahl, die in der aktuellen Zeile und Spalte noch nicht vorkommt. Dann wieder ein rekursiver Aufruf für das nächste Feld. Dies machst du so weiter bis alle 16 Felder belegt sind. Sollte es passieren, dass es an einer Stelle nicht weiter geht, da es keine zulässige Zahl gibt mit der das aktuelle Feld belegt werden kann, so wird der rekursive Aufruf beendet und zurück zum vorherigen Feld gegangen, welches mit einer anderen zufälligen Zahl belegt wird. Wurden alle zulässigen Zahlen für ein Feld durchprobiert, wird der Rekursionsaufruf ebenfalls beendet.

      Auf diese Weise gelangt man auf jeden Fall zu einer gültigen zufälligen Lösung unter Gleichverteilung. Für 4x4 sollte es auch von der Geschwindigkeit passen. Für größere Quadrate wird es wohl zu langsam sein.

    2. Man fängt mit dem "Standard-Quadrat"

      1 2 3 4
      2 3 4 1
      3 4 1 2
      4 1 2 3

      an und tauscht beliebig oft jeweils zwei Zeilen oder zwei Spalten.

      Diese Methode ist natürlich sehr einfach zu implementieren, aber ist nicht wirklich sehr zufällig geschweige denn gleichverteilt.

    Perfekt für etwas größere Quadrate ist diese interessante Methode hier: mathsci.sharif.edu/mahmoodian/…/RandomgeneratingLs40.pdf
    Wäre aber in deinem Fall wohl eher mit Kanonen auf Spatzen geschossen.