SuDoku lösen

Das ist Java Code.

snOOfy

Ja ich hab es in java geschrieben (woran du das jetzt auch immer erkannt hast ) aber ich dachte hier im c++ forum bekomme ich mehr antworten, darum hab ich die paar sachen, die unterschiedlich sind, umgeschrieben, boolean->bool und so...

aber hat keiner eine idee, wie ich try and error in den code reinkriege?

C++ Forumbot

Dieser Thread wurde von Moderator/in volkard aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

life

warum probierste nicht einfach alle sinnvollen Möglichkeiten durch? Eben genau nach try and error Methode oO.

dali

Sudoku ist np complete aber wenn nen Algorithmus findest kannst ihn mir gerne schicken.

Blue-Tiger

dali schrieb:

Sudoku ist np complete aber wenn nen Algorithmus findest kannst ihn mir gerne schicken.

ohne jetzt mehr als 5 Minuten drueber nachgedacht zu haben, aber koennte man dafuer nicht ein lineares Gleichungsystem in n (bei einem n*n-Sudoku) Unbekannten aufstellen und loesen?

dali

Du kannst soviele Gleichungssysteme wie du willst aufstellen aber wie schon gesagt in polynomialer Zeit wirst nicht auf eine Lösung kommen...

dali

Du kannst soviele Gleichungssysteme wie du willst aufstellen aber wie schon gesagt in polynomialer Zeit wirst nicht auf eine Lösung kommen...

life

dali schrieb:

Du kannst soviele Gleichungssysteme wie du willst aufstellen aber wie schon gesagt in polynomialer Zeit wirst nicht auf eine Lösung kommen...

Woher willste das wissen? Es ist nicht bewiesen, dass es keinen effektiven Algorithmus für NP-Vollständige Problemstellungen gibt..

dali

life schrieb:

dali schrieb:

Du kannst soviele Gleichungssysteme wie du willst aufstellen aber wie schon gesagt in polynomialer Zeit wirst nicht auf eine Lösung kommen...

Woher willste das wissen? Es ist nicht bewiesen, dass es keinen effektiven Algorithmus für NP-Vollständige Problemstellungen gibt..

dali schrieb:

Sudoku ist np complete aber wenn nen Algorithmus findest kannst ihn mir gerne schicken.

life

also widersprichst du dir selber?

dali

Gut ok schlecht ausgedrückt... Naja mit blos Gleichungen aufstellen wirst kein NP Problem polynomiell lösen werden können dafür haben sich schon genug Leute damit auseinandergesetzt... Wenn bräuchtest eine superneue tolle Idee und alle Leute die sich auskennen sagen dass es die Idee nie geben wird...

java konnte man anhand public void lösen erkennen.

zu deiner abbruchbedingung: du kannst die schleife so lange laufen lassen, wie noch veränderungen stattfinden. das heißt, sobald in einem schleifendurchlauf gar keine neue zahl gesetzt werden konnte, is feierabend.

du berücksichtigst folgendes nicht:

--x --- ---
1-- --- ---
--- 1-- ---

-1- --- ---
--- --- ---
--- --- ---

--- --- ---
--- --- ---
--- --- ---

da im oberen linken quadrat nirgends anders eine 1 kann, außer an die mit x markierte stelle, kannst du diese dort setzen. dadurch kannst du mehr sudokus lösen.

try and error geht dann mit backtracking. sobald du keine zahl mehr setzen konntest, nimmst du eine stelle (vielleicht die, wo am wenigstens möglichkeiten bleiben) und probierst die erste möglichkeit aus, und lässt dann deinen normalen algo wieder laufen (rekursiv).

gruß mata

snOOfy

Immer diese Rekursion
Ich sehe ja ein, dass sowas sinnvoll ist, aber ich durchschaue das immer nicht so ganz. Wenn man es sieht ist es ja nich so schwer, aber selber drauf zu kommen...
Könntest du mir vielleicht mal einen Ansatz für die rekursive Funktion geben?

sudoku(feld){
  for(alle möglichen zahlen z im feld){
      m(feld)=z
      if(feld != letztes feld)
             sudoku(feld+1)
      else
             lösung
      m(feld)=leer
  }
}

das is es im groben. da kann man dann eben noch deine lösung einbauen, man muss ja nur backtracking nutzen, wenn nix anderes geht.

snOOfy

hmm, das müsste bei mir dann so ungefähr so aussehen

public void BackTrack(int iFeld)
    {
        for (int i=0; i<9; ++i)
        {
            if (getMenge(iFeld % 9, iFeld / 9, i))
                setWert(iFeld % 9, iFeld / 9, i);
            if (iFeld < 81)
                BackTrack(iFeld + 1);
            else
                // Lösung ???
            setWert(iFeld % 9, iFeld / 9, 0); 
        }
    }

aber was mache ich jetzt bei Lösung?
Einfach den ganzen Kram reinkopieren, den ich am Anfang gepostet hab?

Und ist das jetzt überhaupt noch so, dass das in zumutbarer Zeit fertig wird? Es sieht irgendwie aus, als würde es 81 ineinander verschachtelte for Schleifen produzieren...