3sat Problem in C

Silahel

Hallo liebe Leute.
Ich habe das Problem das ich ein das 3sat Problem in C als Spiel darstellen will aber keine Ahnung habe wie ich es machen soll.
Für alle die die nicht wissen wovon ich spreche:

-man hat eine bestimmte anzahl an variablen (etwa 4)
-diese können entweder 0 oder 1 sein
-man hat eine anzahl an bedingungen die etwa so aussehen:
A= 1 oder B = 0 oder C = 1
C = 0 oder D = 1 oder A = 0
und so weiter halt
der Spieler soll jetzt anhand der Bedingungen entscheiden wie die Variablen heißen

Das Problem ist :
Ich habe keien Ahnung wie ich jetzt Bedingungen generieren soll die
Genug Verraten und trotztdem es nicht zu Offensichtlich machen
Diese müssen natürlich Zufällig Erzeugt werden

Wäre Nett wenn jemand sich die Zeit nehmen könnte mir zu helfen!
Ich bin schon ganz verzweifelt

Falls es hilft hier ist ein Zufallsgenerator den ich geschrieben habe der 4
Nullen oder Einsen generiert!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(){

	unsigned int a, b, c, d;

	srand(time( NULL )); // benutzt die Zeit um rand() "anzukurbeln"
	a = rand();
	b = rand();
	c = rand();
	d = rand();	

	a = a & 1;	// stellt sicher das  die variablen entweder 1 oder 0 ist
	b = b & 1;	// da bei & jeder bit verglichen wierd und es ist entweder
	c = c & 1;	// 00000001 oder
	d = d & 1;	// 00000000

	printf("Die Variable A: %d\n", a);
	printf("Die Variable B: %d\n", b);
	printf("Die Variable C: %d\n", c);
	printf("Die Variable D: %d\n", d);
}

Hoffe auf Baldige Antort
Lg Ich

SeppJ

Kannst du mal einen beispielhaften Programmablauf beschreiben? Ich habe keine Ahnung, was du überhaupt genau möchtest. Und ich habe den Eindruck, dir geht es ähnlich.

knivil

Also zum Verstaendnis: Du hast eine Belegung fuer die Variablen ABCD und moechtest daraus eine konjuktive Normalform generieren. Diese wird dem Spieler vorgelegt und er soll die Variablenbelegung erraten.

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

Silahel

nein das stimmt beides leider nicht

ich habe sagen wir 4 bedingungen
wie zum beispiel entweder ist A 1 oder B ist 1 (das ist nur eine bedingung)
und so weiter
diese weisen dann auf die 4 variablen hin und der spieler muss diese erraten

tut mich echt leid falls ich mich schlecht ausdrücke das ist mein erster forumsbeitrag überhaupt ^^

knivil

Am Ende soll der Spieler also beispielsweise sagen: A=1, B=1, C=0, D=0? Oder soll er nur sagen, die Variablen heissen A,B,C,D (was irgendwie beknackt ist)?

Bashar

Silahel schrieb:

Hallo liebe Leute.
Ich habe das Problem das ich ein das 3sat Problem in C als Spiel darstellen will aber keine Ahnung habe wie ich es machen soll.
Für alle die die nicht wissen wovon ich spreche:

-man hat eine bestimmte anzahl an variablen (etwa 4)
-diese können entweder 0 oder 1 sein
-man hat eine anzahl an bedingungen die etwa so aussehen:
A= 1 oder B = 0 oder C = 1
C = 0 oder D = 1 oder A = 0
und so weiter halt
der Spieler soll jetzt anhand der Bedingungen entscheiden wie die Variablen heißen

Die Variablen heißen A, B, C und D. Da die Namen in den auszugebenden Bedingungen vorkommen müssen, ist das Spiel ziemlich sinnlos. Vielleicht liegt das daran, dass du das 3SAT-Problem missverstanden hast? Wenn du deinen letzten Satz ersetzt durch "Der Spieler soll eine Belegung der Variablen mit Werten finden, so dass alle Bedingungen erfüllt sind." wird ein Schuh draus (eigentlich reicht es herauszufinden, ob eine solche Belegung existiert, aber wo ist dann das Spiel).

Silahel

knivil schrieb:

Am Ende soll der Spieler also beispielsweise sagen: A=1, B=1, C=0, D=0? Oder soll er nur die Variablen heissen A,B,C,D (was irgendwie beknackt ist)?

na er soll sagen A = 1 B = 1 C = 0 D = 0 ^^ das andere wär ja auch bescheuert

Silahel

Bashar schrieb:

Die Variablen heißen A, B, C und D. Da die Namen in den auszugebenden Bedingungen vorkommen müssen, ist das Spiel ziemlich sinnlos. Vielleicht liegt das daran, dass du das 3SAT-Problem missverstanden hast? Wenn du deinen letzten Satz ersetzt durch "Der Spieler soll eine Belegung der Variablen mit Werten finden, so dass alle Bedingungen erfüllt sind." wird ein Schuh draus (eigentlich reicht es herauszufinden, ob eine solche Belegung existiert, aber wo ist dann das Spiel).

na er soll sagen A = 1 B = 1 C = 0 D = 0 ^^ das andere wär ja auch bescheuert [/quote]

genau ^^
das meinte ich eigendlich auch hab ich mich wohl doof ausgedrückt

knivil

Silahel schrieb:

na er soll sagen A = 1 B = 1 C = 0 D = 0 ^^ das andere wär ja auch bescheuert

Das ist eine Belegung der Variablen. Da wir nun das geklaert hat, kommen wir zum naechsten Punkt: Was sieht der Benutzer um das Ergebnis zu erraten?

Silahel

knivil schrieb:

Silahel schrieb:

na er soll sagen A = 1 B = 1 C = 0 D = 0 ^^ das andere wär ja auch bescheuert

Das ist eine Belegung der Variablen. Da wir nun das geklaert hat, kommen wir zum naechsten Punkt: Was sieht der Benutzer um das Ergebnis zu erraten?

naja der benutzer sieht zum beispiel 4 bedingungen die heißen zum beispiel

C = 1 ODER D = 0 ODER A = 1
und
A = 1 oder c = 0 oder b = 1
und
A = 0 ODER D = 1 ODER C = 0

Bashar

Silahel schrieb:

Das Problem ist :
Ich habe keien Ahnung wie ich jetzt Bedingungen generieren soll die
Genug Verraten und trotztdem es nicht zu Offensichtlich machen
Diese müssen natürlich Zufällig Erzeugt werden

Generiere doch erstmal irgendwelche Bedingungen, bevor du versuchst, den Schwierigkeitsgrad anzupassen.

Silahel

Bashar schrieb:

Silahel schrieb:

Das Problem ist :
Ich habe keien Ahnung wie ich jetzt Bedingungen generieren soll die
Genug Verraten und trotztdem es nicht zu Offensichtlich machen
Diese müssen natürlich Zufällig Erzeugt werden

Generiere doch erstmal irgendwelche Bedingungen, bevor du versuchst, den Schwierigkeitsgrad anzupassen.

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!

knivil

Silahel schrieb:

knivil schrieb:

Silahel schrieb:

na er soll sagen A = 1 B = 1 C = 0 D = 0 ^^ das andere wär ja auch bescheuert

Das ist eine Belegung der Variablen. Da wir nun das geklaert hat, kommen wir zum naechsten Punkt: Was sieht der Benutzer um das Ergebnis zu erraten?

naja der benutzer sieht zum beispiel 4 bedingungen die heißen zum beispiel

C = 1 ODER D = 0 ODER A = 1
und
A = 1 oder c = 0 oder b = 1
und
A = 0 ODER D = 1 ODER C = 0

Ja genau. Das ist die konjunktive Normalform nur etwas anders aufgeschrieben, uebersetzt:

(c || not(d) || a) && (a || not(c) || b) && ...

(keine Ahnung wie das hier in Latex geht)

Bashar

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».

Bashar

knivil schrieb:

(c || not(d) || a) && (a || not(c) || b) && ...

(keine Ahnung wie das hier in Latex geht)

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

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.

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.