3sat Problem in C

[Silahel]

Bashar schrieb:

Meinst du jetzt ich soll mir Bedingungen erstmal ausdenken oder meinst du ich soll einen generator schreiben der bedingungen generiert weil genau das ist ja mein Problem!

Du hast aber geschrieben, dein Problem wäre, Bedingungen zu generieren, die «die
Genug Verraten und trotztdem es nicht zu Offensichtlich machen».

ja genau das gehört ja bei einem generator dazu

[Silahel]

ich denke das Problem sollte jetzt mittlerweile ausreichend geklärt sein.
Gibt es denn irgendwelche lösungsvorschläge?

[knivil]

knivil schrieb:

... Loesung: generiere einfach die konjunktive Normalform aus der Wahrheitstabelle fuer deine Variablen.

Du musst dir natuerlich ueberlegen, wie die Wahrheitstabelle aussieht fuer deine zu erratene Belegung.

[Bashar]

Silahel schrieb:

ja genau das gehört ja bei einem generator dazu

Du willst es gar nicht verstehen, oder?

[SeppJ]

Meine Güte, dir muss man ja echt alles aus der Nase ziehen. Ich wiederhole mal noch einmal die allererste Antwort dieses Threads, mit der man sich zwei Seiten im Kreis drehen hätte sparen können (und die mMn immer noch nicht zufriedenstellend beantwortet wurde):

SeppJ schrieb:

Kannst du mal einen beispielhaften Programmablauf beschreiben?

Insbesondere zu deinen Bedingungen «die Genug Verraten und trotztdem es nicht zu Offensichtlich machen» würde ich gerne mal ein Beispiel sehen. Möchtest du ein unvollständiges 3SAT als Aufgabe an den Spieler stellen? Wie soll man das dann überhaupt lösen, wenn man nicht alle Bedingungen kennt? Das wäre wie ein Kreuzworträtsel ohne Fragen.

[nagel]

Silahel schrieb:

nein das stimmt beides leider nicht

doch es stimmt. knivil hat hat recht mit "konjunktiver Normalform"

3-SAT ist eine Variante des Erfüllbarkeitsproblems der
Aussagenlogik (Erfüllbarkeit engl.: satisfiability, kurz SAT).
Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform
vorliegende aussagenlogische Formel F, die höchstens 3 Literale pro Klausel
enthält, erfüllbar ist. Ein Beispiel für eine solche Formel:

[latex]F = (\overline{x_1} \vee x_2 \vee x_3) \wedge (x_2 \vee \overline{x_3} \vee x_4) \wedge (x_1 \vee \overline{x_2}) [/latex]

aus wikipedia wenn man die zauberworte spricht.

[Silahel]

knivil schrieb:

knivil schrieb:

... Loesung: generiere einfach die konjunktive Normalform aus der Wahrheitstabelle fuer deine Variablen.

Du musst dir natuerlich ueberlegen, wie die Wahrheitstabelle aussieht fuer deine zu erratene Belegung.

könntest du villeicht näher erläutern was du mit einer "konjunktive Normalform aus der Wahrheitstabelle" meinst ^^ danke für die idee

[knivil]

Beispiel Variablen ABC, zu erraten ist A=1, B=0, C=1
Wahrheitstabelle:

A B C  F(ABC)
0 0 0  0
0 0 1  0
0 1 0  0
0 1 1  0
1 0 0  0
1 0 1  1  <---- richtig, zu erratene Kombination
1 1 0  0
1 1 1  0

Das ist deine Wahrheitstabelle. Fuer die konjunktive Normalform sind nur die Stellen relevant fuer die F(ABC) = 0 ist, also 7 von den 8 moeglichen. Danach werden diese genommen und jede 1 negiert:

$(a \vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge \cdots$

Der Term $(a \vee \neg b \vee c)$ darf nicht vorkommen, da fuer ihn ja F(ABC) = 1 gilt. Willst du es einfacher machen, kannst du die Loesungsmenge vergroessern und F(ABC) = 1 fuer andere Stellen hinzufuegen. Diese duerfen dann nicht in der konjunktiven Normalform auftauchen. Ueber mehr Variablen aber trotzdem 3-SAT habe ich noch nicht nachgedacht, vielleicht realisiert du diese Variante hier erstmal. Potentiell koennen alle Variablen weggelassen werden, die in dem "gleichen" Term negiert bzw. unnegiert auftauchen. Also $(a \vee b \vee \neg c) \wedge (a \vee b \vee c)$ kann zu $(a \vee b)$ zusammengefasst werden.

PS: Danke fuer den Latex-Trick. Er scheint gleich im Mathemodus zu sein.

[Silahel]

knivil schrieb:

Beispiel Variablen ABC, zu erraten ist A=1, B=0, C=1
Wahrheitstabelle:

A B C  F(ABC)
0 0 0  0
0 0 1  0
0 1 0  0
0 1 1  0
1 0 0  0
1 0 1  1  <---- richtig, zu erratene Kombination
1 1 0  0
1 1 1  0

Das ist deine Wahrheitstabelle. Fuer die konjunktive Normalform sind nur die Stellen relevant fuer die F(ABC) = 0 ist, also 7 von den 8 moeglichen. Danach werden diese genommen und jede 1 negiert:

$(a \vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge \cdots$

Der Term $(a \vee \neg b \vee c)$ darf nicht vorkommen, da fuer ihn ja F(ABC) = 1 gilt. Willst du es einfacher machen, kannst du die Loesungsmenge vergroessern und F(ABC) = 1 fuer andere Stellen hinzufuegen. Diese duerfen dann nicht in der konjunktiven Normalform auftauchen. Ueber mehr Variablen aber trotzdem 3-SAT habe ich noch nicht nachgedacht, vielleicht realisiert du diese Variante hier erstmal. Potentiell koennen alle Variablen weggelassen werden, die in dem "gleichen" Term negiert bzw. unnegiert auftauchen. Also $(a \vee b \vee \neg c) \wedge (a \vee b \vee c)$ kann zu $(a \vee b)$ zusammengefasst werden.

PS: Danke fuer den Latex-Trick. Er scheint gleich im Mathemodus zu sein.

Ok ich glaube das habe ich soweit verstanden
Danke für die Hilfe soweit!
Aber ich frage mich trotzdem noch wie ich daraus einen Generator bauen soll

[rkhb]

Silahel schrieb:

Meinst du jetzt ich soll mir Bedingungen erstmal ausdenken oder meinst du ich soll einen generator schreiben der bedingungen generiert weil genau das ist ja mein Problem!

Ich hätte da eine Idee:

Angenommen, Du hast genau 4 Variablen (A,B,C,D).
Eine Klausel hätte dann die Form (A=x || B=x || C=x || D=x), wobei x für drei Möglichkeiten steht: 0, 1 oder - (gar nicht vorhanden). Aus einer Folge "01-1" würde dann: (A=0 || B=1 || D=1). C ist minus, also gar nicht vorhanden. Du musst also erst einmal alle denkbaren Folgen (Strings) generieren, wobei jede Stelle drei mögliche Werte annehmen kann. Wenn jede Stelle zwei Werte annehmen kann, haben wir ein Dualsystem, wenn jede Stelle 10 Werte annehmen kann, ein Dezimalsystem, wenn jede Stelle 16 Werte annehmen kann, ein Hexadezimalsystem. In diesem Fall haben wir also ein System mit der Radix 3. Und netterweise kann der Befehl itoa (MSVC, mindestens auch Mingw-GCC) mit ungewöhnlichen Radices umgehen:

char k[5];
for (int i=0; i<81; ++i)
{
    itoa (i,k,3);
    printf ("Klauselstring: %04s\n",k); // GCC-Warnung kann ignoriert werden
}

Wenn Du einen String wie "0121" bekommst, steht die '2' dann für "nicht vorhanden".

Nun kannst Du die möglichen Strings (mindestens eine '2') und die richtigen Strings (mindestens eine Stelle stimmt mit der Vorgabe überein) filtern.

Kommst Du jetzt weiter?

viele grüße
ralph