Ein Rätsel (das man rekursiv lösen kann?)

Als erstes würde ich die Gleichungen so umformen, dass du nur Additionen und Multiplikationen hast; den Ärger mit Subtraktionen und Divisionen kannst du dir damit ersparen. Als zweites wäre es hilfreich, welche Schlussfolgerungsregeln es gibt, die man nutzen kann. Erst dann sollte man sich an das Brute-Force heranwagen.
In puncto Brute-Force-Algorithmen gilkt Donald Knuth's Dancing Links Algorithmus als effizient, den ich selber mal als solver-Klasse in C++/wxWidgets sowie in PHP und JavaScript (ja, es geht!) implementiert habe; wenn man das Grundprinzip erstmal begriffen hat, ist es gar nicht so schwer nachzuvollziehen, wie er funktioniert.
Oder du löst es in PROLOG.

PS: Vielleicht kann man es auch mit Genetischen Algorithmen lösen.
 
Zuletzt bearbeitet:
Ich hab mal ein kleines Programm geschrieben, in ca 800 Minuten hab ich das Ergebnis :)

(Man könnte sicher einiges besser machen, aber hab nicht so viel Zeit investiert)
 
Zuletzt bearbeitet:
Hallo VanHellsehn,

im prinzip ist das ähnlich eines Sudoku-Rätzels. Du hast eine Menge an Bedngungen die erfüllt sein müssen und eine Menge an Zahlen die in der richtigen Kombination die Bedingungen erfüllen.
Schwierig ist hier nur, wie man die Bedingungen formuliert.

Ich hab mal ein Sudoku-Solver geschrieben und das nach folgendem Alg. gemacht: (Der Alg hat auch einen Namen, der mir aber mom nicht mehr einfallen will)


start: funktion(erste variable)
Code: 
function(Variable)
{
	for(Variable = 0; Variable < 10; Variable++)
	{
		IF(checkBedingungen() == true)
		{
			funktion(nächste variable)
		}
	}
}
vlt. hilfts ja

gruß
Col.Blake
 
Der Vergleich mit Sudoku ist gar nicht so schlecht. Bei Sudoku wird mit Kandidaten gearbeitet, das sind Zahlen, die in den Zellen platziert sein könnten. Nach und nach werden die Kandidaten ermittelt, die ausgeschlossen werden können, weil sie bestimmte Bedingungen nicht erfüllen; so wird allmählich die Lösung ermittelt.
Bei deinem Rätsel hast du die Kandidaten 0-9 für deine Variablen. Du kannst z.B. die Null für diejenigen Variablen ausschließen, die als erste Ziffer für eine Zahl erscheinen. Und wenn bei einer Addition die Summe mehr Ziffern hat als die Summanden, kannst du alle Ziffern außer 1 ausschließen. Allerdings verkompliziert die Mölglichkeit von Überträgen die Lösungssuche.
Bestünde das Rätsel nur aus Additionen, wäre es wesentlich einfacher, denn dann könntest du mit möglichen Zahlentripeln für die Stellen arbeiten, z.B. ist 7/8/6 eine mögliche Konstellation, wenn ein Übertrag vorhanden ist, denn 7+8+1=16, 7/8/3 ist aber keine, denn weder 7+8+1 noch 7+8 ergibt 3 oder 13.

Übrigens: Brute-Force-Solver für Sudoku verwenden meistens den oben erwähnten Dancing-Links-Algorithmus.
 
Zuletzt bearbeitet:
Hi,
Die Aufgabe die mir gestellt wurde soll aber mit C und ausschließlich mit der stdio.h libary gelöst werden..
also mit keiner anderen Sprache.. ^^
 
Hi.
VanHellsehn hat gesagt.:
Hi,
Die Aufgabe die mir gestellt wurde soll aber mit C und ausschließlich mit der stdio.h libary gelöst werden..
also mit keiner anderen Sprache.. ^^
Zum Vergrößern anklicken....
Es hat doch niemand etwas von einer anderen Sprache gesagt. \edit: Ach, es ist PROLOG genannt worden. Sorry.

Außerdem hat Matthias ja schon einen Hinweis gegeben wie man das relativ einfach lösen kann.

Gruß

PS: Ich hab grad mal den Permutationsansatz implementiert und das Programm liefert im Grunde sofort die einzige Lösung.
 
Zuletzt bearbeitet:
Hi,
Ja Mathias hat mir schöne mölichkeiten gezeigt doch kann ich diese nich umsetzten.
Mein Problem ist auch ich kenne nicht alle Funktionen von C.
Ich habe Jahre lang nur OOP mit PHP gemacht.
 
Also: allgemein gesprochen hast musst du eine verträgliche Zuordnung von Aktionen zu Ressourcen finden. Bei dir ist eine Aktion das Zuordnen einer Ziffer zu einem Ort in deiner Rätseltabelle. Die Ressourcen sind die Variablen und die möglichen Zahlentripel. Eine Aktion verbraucht eine Ressource, und aufgrund der verbrauchten Ressourcen sind alle die Möglichkeiten auszuschliessen, die diese verbrauchten Ressourcen benötigen. Du hast genau dann eine Lösung gefunden, wenn deine verwendeten Möglichkeiten nicht mehr und nicht weniger Ressourcen verbrauchen als du hast.
Du kannst dann eine Tabelle der Möglichkeiten und Ressourcen anlegen, mit der du die Information verwaltest, welche Möglichkeiten und Ressourcen noch zur Verfügung stehen und welche auszuschließen sind, und diese dann rekursiv abarbeiten.
Der Dancing-Links-Algorithmus verwendet , wie es für schwach besetzte Matrizen üblich ist, für diese Tabelle Listenelemente, die sowohl in der Zeile (die Ressourcen, die eine bestimmte Aktion verbraucht) als auch in der Spalte (die Aktionen, die eine bestimmte Ressource benötigen) doppelt verzeigert sind. Elemente, die nicht verwendet werden, werden aus der Liste herausgenommen und beim Rollback in umgekehrter Reihenfolge wieder eingehängt. Wegen der doppelten Verzeigerung beinhaltet das herausgenommene Element die Information, bei welchen Nachbarn es wieder einzuhängen ist. So etwas kann man auch mit ANSI-C implementieren, man braucht allerdings schon etwas Übung.
Wenn du nur stdio.h verwenden darfst, dann musst du diese Tabelle als Array implementieren, denn für dynamische Speicherverwaltung brauchst du malloc.h; die Möglichkeiten der Verzeigerung kannst du trotzdem nutzen, wenn du dir eine passende struct definierst.
 
Der Tipp mit dem Suchen war überflüssig.. ich habe gesucht und diesen Artikel gefunden doch erzeugte der Code bei mir nen Error.. nach diesem Fehler habe ich diesen Thread erröffnet ;)
Aber ich bin einfach zu schlecht ><
Also ein guter hacker würde ich aufjedenfall nicht werden :D
Hmm..

C: 
#include <stdio.h>

bool pruefe(int x[10])
{
	// Rechnungen pruefen
	if( (x[0]*1000+x[1]*100+x[2]*10+x[3]) /
		(x[4]*10+x[5]) ==
		(x[4]*100+x[6]*10+x[3])
		&&
		(x[7]*1000+x[8]*100+x[9]*10+x[4]) -
		(x[7]*1000+x[8]*100+x[1]*10+x[6])==
		(x[5]*10+x[4])
		&&
		(x[9]*1000+x[8]*100+x[3]*10+x[1]) -
		(x[7]*1000+x[8]*100+x[3]*10+x[5]) ==
		(x[2]*1000+x[6]*100+x[6]*10+x[2])
		&&
		(x[0]*1000+x[1]*100+x[2]*10+x[3]) -
		(x[7]*1000+x[8]*100+x[9]*10+x[4]) ==
		(x[9]*1000+x[8]*100+x[3]*10+x[1])
		&&
		(x[4]*10+x[5]) +
		(x[7]*1000+x[8]*100+x[1]*10+x[6]) ==
		(x[7]*1000+x[8]*100+x[3]*10+x[5])
		&&
		(x[4]*100+x[6]*10+x[3]) *
		(x[5]*10+x[4]) == 
		(x[2]*1000+x[6]*100+x[6]*10+x[2])
	)
	{
		return true;
	}
	else
		return false;
}

int erhoehe(int symbol)
{
	int i;

	if(symbol==9)
		symbol=0;
	else
		symbol++;
	
	return symbol;
}

void main(void)
{
	int symbol[10]={0,1,2,3,4,5,6,7,8,9},x[10],i=0;
	
	while(true)
	{		
		// Zahlen mit den Rechnungen pruefen
		if(pruefe(x)==true)
		{
			for(i;i<=9;i++)
			{
				// Zahlen ausgeben
				printf("\n\tSymbol %i: %i",i+1,x[i]);
			}
			printf("\n\n\tIch habs geschaft! ! ! !\n\n\n\t");
			break;
		}

		for(i=0;i<=9;i++)
			symbol[i] = erhoehe(symbol[i]);
	}
}

Das war mein aller erster Versuch.. nur dieser Versuch Testet ja eindeutig immer nur in der gleichein Rheinfolge die Zahlen ab.
Also 0 1 2 3 4 5 6 7 8 9 dann 9 0 1 2 3 4 5 6 7 8 das macht er bis 0 9 8 7 6 5 4 3 2 1 und fängt von vorne an.. also 0 7 8 2 3 4 9 5 6 würde er z.B. nicht Testen..
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück