 Das n-Läufer und Türme Problem |
Dennis P.
unregistriert
 |
|
| Das n-Läufer und Türme Problem |
     |
Meine Frage:
Für ein gegebenes n?N>0 sollen Türme und Läufer auf einem n×n-Schachbrett so platziert werden, dass sie sich nicht gegenseitig bedrohen, d.h. keine Figur soll eine andere Figur schlagen können. Außerdem muss in jeder Spalte und in jeder Zeile mindestens eine Figur stehen und es muss insgesamt mindestens einen Läufer und mindestens einen Turm geben. Natürlich kann auf jedem Feld höchstens eine Figur stehen. Eine Platzierung gemäß dieser Regeln bezeichnen wir als Lösung des n-Läufer- und-Türme-Problems.
Zur Erinnerung: Ein Turm darf beliebig viele Felder in horizontale
oder vertikale Richtung ziehen. Ein Läufer darf beliebig viele Felder in diagonale Richtung ziehen.
a) Besitzt das n-Läufer-und-Türme-Problem für n=3 bzw. n=4 eine Lösung?
b) Modellieren Sie das n-Läufer-und-Türme-Problem durch aussagenlogische Formeln. Verwenden Sie im Folgenden für alle i, j ? {1, . . . , n} die aussagenlogische Variable Ti,j mit der Bedeutung ?auf dem Feld (i,j) in Zeile i und Spalte j steht ein Turm? sowie die Variable Li,j mit der Bedeutung ?auf dem Feld (i,j) in Zeile i und Spalte j steht ein Läufer?.
Geben Sie jeweils auch eine kurze umgangssprachliche Erläuterung Ihrer Formeln an. Hinweis: Notationen wie 1113089ni=1(. . . ), 1113088ni=1(. . . ) oder 1113088(i,j)?...(. . . ) und Beispiel 3.48 (Sudoku)
aus dem Skript können hilfreich sein.
i) Konstruieren Sie eine Formel Höchstensi,j, die aussagt, dass auf dem Feld (i,j) höchstens eine Schachfigur steht.
ii) Konstruieren Sie eine Formel Turmi,j, die aussagt: ?wenn ein Turm auf dem Feld (i,j) steht, darf in Zeile i und Spalte j keine weitere Schachfigur stehen?.
iii) Konstruieren Sie eine Formel Läuferi,j, die aussagt: ?wenn ein Läufer auf dem Feld (i,j) steht, darf in den Diagonalen des Feldes (i,j) keine weitere Schachfigur stehen?.
iv) Konstruieren Sie Formeln Zeilei bzw. Spaltej, die aussagen, dass in Zeile i bzw. Spalte j mindestens eine Schachfigur steht.
v) Konstruieren Sie eine Formel Mindestens, die aussagt, dass mindestens ein Läufer und mindestens ein Turm auf dem Schachbrett stehen.
c) Geben Sie eine Formel ?n an, sodass die erfüllenden Belegungen von ?n genau den Lösungen des n-Läufer-und-Türme-Problems entsprechen.
d) Geben Sie eine zu ?n äquivalente Formel ?n in KNF an.
Meine Ideen:
Bitte könnt ihr mir mal helfen ich kann diese Aufgabe einfach nicht lösen und habe keine Ahnung, wie ich voran gehen soll.
(p.s ich bin kein Informatiker sondern belege ein WPF)
Danke schon mal !
|
|
12.11.2018 18:36 |
|
|
SC/MP
Grünschnabel
Dabei seit: 11.11.2018
Beiträge: 1
|
|
Die Aufgabe ist offensichtlich sehr einfach. Ich kann sie gerne zur Fingerübung lösen. Vermutlich wurde diese Aufgabe als sanftes Aufweckerlebnis für Studenten konzipiert, die vorher wochenlang zechend durch die Kneipen gezogen sind. Das Ergebnis kann ich gerne hier reinstellen, aber sie würden den eigentlichen Zweck der Aufgabenstellung nicht erkennen. Zur Lösungskompetenz gehört nicht nur kurzfristige Lösungsökonomie.
btw. Was ist ein WPF?
|
|
|
12.11.2018 23:44 |
|
|
DennisP.
unregistriert
|
|
Das wäre echt cool.
Wpf = wahlpflichtfach 
|
|
|
13.11.2018 06:49 |
|
|
|
