Zahlenrätsel

Sage

Occupation: GER

Sunday, October 19th 2008, 2:31am

Das Rätsel spielt auf einem 5x5 Brett, wobei jedes der 25 Felder mit einer Ziffer von 1 bis 4 zu besetzen ist. Für das Füllen gelten folgende Regeln:

1. Eine 1 darf man immer setzen.
2. Eine 2 darf man setzen, wenn eine 1 daneben steht.
3. Eine 3 darf man setzen, wenn eine 1 und eine 2 daneben steht.
4. Eine 4 darf man setzen, wenn eine 1, eine 2 und eine 3 daneben steht.
5. Als "daneben stehen" gilt horizontale (rechts, links) und vertikale (oben, unten) Nachbarschaft. Nein, diagonal ist nicht.

Ziel ist es, die Summe der Ziffern möglichst gross zu bekommen. Ein fix zusammengeklicktes Beispiel hängt an, die Summe ist dort 52.

Sheep has attached the following file:

rätsel.png (984 Byte - 706 times downloaded - latest: Nov 16th 2023, 4:38pm)

Go to the top of the page

GEC|Napo

Sage

Posts: 8,654

Location: Köln

Occupation: GER

2

Sunday, October 19th 2008, 2:45am

58 im ersten Versuch

1 3 4 1 3
3 2 2 4 2
4 1 1 3 1
2 4 3 2 3
1 3 2 1 2

Go to the top of the page

GEC|Napo

Sage

Posts: 8,654

Location: Köln

Occupation: GER

3

Sunday, October 19th 2008, 2:53am

59 mit System, ist glaub ich schon das Maximum

2 4 1 4 2
1 3 2 3 1
2 4 1 4 2
1 3 2 3 1
2 4 1 4 2

Go to the top of the page

Sheep

Sage

Posts: 4,172

Occupation: GER

4

Sunday, October 19th 2008, 12:12pm

Wir kamen gestern auch nur auf 59, wobei es da auch nichtsymmetrische Varianten gibt. 64 ist auf jeden Fall eine Grenze, wenn man die Anzahl der notwendigen 1en, 2en und 3en anschaut...

Go to the top of the page

pitt82

Master

Posts: 2,114

5

Thursday, November 13th 2008, 1:40am

Nachdem ich jetz ein paar Wochen immer mal wieder rumprogrammiert und Leute mit C2Q Rechnern geärgert hab, hatte ich eben wohl den richtigen Einfall für mein Lösungsprogramm:

2 4 1 3 1
1 3 4 2 4
4 2 4 1 3
3 1 3 3 2
2 1 2 4 1

=61

Wer n Fehler findet darf sich gerne melden

Vielleicht geht auch noch mehr *deutlich betagten athlon64 3200+ mit C0-stepping streichel*

Go to the top of the page

MaxPower

Sage

Posts: 7,452

6

Thursday, November 13th 2008, 9:57am

Sind doch "nur" 25 hoch 4 Möglichkeiten, oder? Sollte man mit Brute Force ja knacken können.

Sind knapp unter 400.000 Möglichkeiten. DIe Gültigkeitsprüfung und die bewertung müssen effiyient programmiert sein, ich denke mal in reinem C is das deutlich unter einer Stunde zu schaffe, dass maximum zu finden

ma schauen, vielleicht hab ich Lust später das auszuprobieren, falls ich dazu zeit finde -.-

und dann nochmal in python und dann vergleichen ^^

Go to the top of the page

Erg_Raider

Master

Posts: 1,823

Location: GER

7

Thursday, November 13th 2008, 10:42am

hab ich grad nen denkfehler oder sollten es eher 4 hoch 25 möglichkeiten sein? (wenn man die randbedingungen erstmal ignoriert)

Go to the top of the page

GEC|Napo

Sage

Posts: 8,654

Location: Köln

Occupation: GER

8

Thursday, November 13th 2008, 12:02pm

Nein kein Denkfehler, du hast recht. 4^25 ist ne Menge! man könnte es verringern indem man anfängt mindestens 7 Einsen zu setzen.

Go to the top of the page

AtroX_Worf

Sage

Posts: 11,465

Location: Hamburg

Occupation: GER

9

Thursday, November 13th 2008, 12:29pm

selbst 4^15 = 2^30 wären noch enorm.
Glaube brute force ist nicht so das wahre. Algebraiker (??) oder jemand in optimization, diskrete Mathematik müsste da recht schnell auskunft geben können. Schätze mal wird nen NP hartes Problem sein.

Go to the top of the page

GWC|lazy

Sage

Posts: 6,260

10

Thursday, November 13th 2008, 12:38pm

hm also firebirds brute force programm was ich gestern auf meinem quadcore laufen lassen hab hätte noch ~2800 stunden gebraucht, so überzeugt bin ich davon jetzt nicht ^^

Go to the top of the page

Yezariael

Sage

Posts: 5,157

Location: ... da wars dunkel und kalt...

11

Thursday, November 13th 2008, 12:49pm

Quoted

Original von GWC|lazy
hm also firebirds brute force programm was ich gestern auf meinem quadcore laufen lassen hab hätte noch ~2800 stunden gebraucht, so überzeugt bin ich davon jetzt nicht ^^

hier heisst er doch Pitt82

Go to the top of the page

MaxPower

Sage

Posts: 7,452

12

Thursday, November 13th 2008, 12:50pm

Quoted

Original von Erg_Raider
hab ich grad nen denkfehler oder sollten es eher 4 hoch 25 möglichkeiten sein? (wenn man die randbedingungen erstmal ignoriert)

nein ich hatte den Denkfehler (und noch keinen Kaffee zu diesem Zeitpunkt)

4 hoch 25 is natuerlich was anderes ^^

Das sind 1.125.899.906.842.624 Faelle

also 1.125 Trillionen wenn ich mich nicht verzaehlt habe

Der Quadcore wuerde gegenueber nem singlecore nur was bringen, wenn man 4 threads oder 4 prozesse fuer die berechnung benuzten wuerde

welche sprache war das denn?

Go to the top of the page

AtroX_Worf

Sage

Posts: 11,465

Location: Hamburg

Occupation: GER

13

Thursday, November 13th 2008, 1:01pm

Dieses Problem lässt sich doch super parallelisieren.

Wenn ihr den entscheidenden Teil eures Codes postet, kann ich vielleicht noch ein paar Tipps geben, wie man noch durch die richtige Programmiertechnik Geschwindigkeit rausholen kann.

Go to the top of the page

pitt82

Master

Posts: 2,114

14

Thursday, November 13th 2008, 1:30pm

Quoted

Original von GWC|lazy
hm also firebirds brute force programm was ich gestern auf meinem quadcore laufen lassen hab hätte noch ~2800 stunden gebraucht, so überzeugt bin ich davon jetzt nicht ^^

Ja ich sollte das mit Stunden einfach weglassen .. das is mittlerweile eigentlich nur noch ne Art normierter Geschwindigkeitsindex (er berücksichtigt nämlich nich wenn das Programm ungültige Kombinationen überspringt). Ich würd die verbleibende Zeit ja gern genauer angeben, aber das is die performanceeinbußen die ich dafür hab nich wert.

Go to the top of the page

pitt82

Master

Posts: 2,114

15

Thursday, November 13th 2008, 2:27pm

Quoted

Original von MaxPower
welche sprache war das denn?

C (Win32) - Threads sind es atm 12 (11 und 12 werden schnell verworfen, weil sie am Start ungültige Kombinationen haben) auf Dauer sind also noch 10 Threads - genug für einen Quadcore

Wenn du nix zutun hast Worf:

Hmpf .. beim durchlesen hier den Fehler gefunden

This post has been edited 4 times, last edit by "pitt82" (Nov 13th 2008, 2:40pm)

Go to the top of the page

AtroX_Worf

Sage

Posts: 11,465

Location: Hamburg

Occupation: GER

16

Thursday, November 13th 2008, 2:56pm

Naja, ging mr eher um allgemeine Rezepte. Poste mal nen kurzen Ausschnitt, einfach nur die Schleifen.

Go to the top of the page

pitt82

Master

Posts: 2,114

17

Thursday, November 13th 2008, 3:12pm

Sowas?

	Source code
1 2	for(j=0;j<25;j++) neu.feld[j]=1;

Go to the top of the page

sylence

Administrator

Posts: 1,863

Location: Dresden

Occupation: GER

18

Thursday, November 13th 2008, 3:15pm

Her mit dem Code. Wenn er sich auch unter nem GNU/Linux kompilieren lässt und nicht zu lange rechnet, würd ichs mal auf nem aktuellen System mit 2 Xeon Quadcores austesten.

Go to the top of the page

GWC|lazy

Sage

Posts: 6,260

19

Thursday, November 13th 2008, 3:32pm

Quoted

Original von Yezariael

Quoted

Original von GWC|lazy
hm also firebirds brute force programm was ich gestern auf meinem quadcore laufen lassen hab hätte noch ~2800 stunden gebraucht, so überzeugt bin ich davon jetzt nicht ^^

hier heisst er doch Pitt82

lol echt? das wusst ich gar nich

Go to the top of the page

pitt82

Master

Posts: 2,114

20

Thursday, November 13th 2008, 3:49pm

Quoted

Original von sylence
.. Wenn er sich auch unter nem GNU/Linux kompilieren lässt ..

Lässt er sich leider nicht. (process.h, pthread.h)

Go to the top of the page

AtroX_Worf

Sage

Posts: 11,465

Location: Hamburg

Occupation: GER

21

Thursday, November 13th 2008, 3:50pm

Quoted
Original von pitt82
Sowas?
Source code
1
2
	for(j=0;j<25;j++)
		neu.feld[j]=1;

Genau.
Natürlich noch vorher was mit nem kleinen Kommentar, was die Funktionsweise des programms deutlich macht. Letzlich hat man ja nur einige Schleifen und Bedingungen und merkt sich die maximale Kombination sowie die maximale Summe.
Denke bei der Art wie man die Schleifen setzt bzw. die Komination aus Schleifen und Abfragen macht kann man sicher 1-2, wenn nicht mehr, Größenordnungen rausholen.

Weiß aber sicher jeder Informatiker besser, was da zu machen ist - kann man ja aber hier drin diskutieren.

Go to the top of the page

pitt82

Master

Posts: 2,114

22

Thursday, November 13th 2008, 8:38pm

Hat sich imho erledigt - is jetz in <4h durchgelaufen und hat nix größeres als 61 gefunden

Go to the top of the page

MaxPower

Sage

Posts: 7,452

23

Thursday, November 13th 2008, 9:13pm

Kannst du den Quellcode ma posten?

Nach welche Strategie hast du die Threads aufgeteilt?

Go to the top of the page

pitt82

Master

Posts: 2,114

24

Thursday, November 13th 2008, 9:41pm

Hab die komplette Visual Studio Solution mal gepackt ..

Für die die das nich haben:
main() findet man in der \59_new\59_new\59_new.cpp

Die wichtigsten Dateien daneben sind:
threads.cpp
error_check.cpp

Threads hab ich so eingeteilt, dass jeder einen Teil der Kombinationen bekommt. Wenn man die 25 Felder wie Stellen einer Zahl betrachtet, dann ist oben links a^0;a^1;.. bis unten rechts a^23;a^24. Die Start/Zielwerte der Threads unterscheiden sich dann auf den stellen 23 und 24.
Hatte zuerst versucht die Threads bei der Überprüfung des arrays einzusetzen, aber das war wahnsinnig langsam und ich hätte - damit es wirklich effektiv gewesen wäre - Threads auf gleicher Augenhöhe sich gegenseitig abschießen lassen müssen.

Da es kein Gemeinschaftsprojekt ist musst du auf ausführliche Kommentierung aber leider verzichten

pitt82 has attached the following file: