IngoAlthoefer
20.06.2016, 16:35

+19Puzzle mit 4x4 Teilen

Hallo,

aus den 1950er Jahren stammt ein Puzzle, wo 4 x 4 Teile
so aneinander zu legen sind, dass alle Übergänge passen.
Der Schöpfer (Hans Bouwmeester aus den Niederlanden?!)
beschrieb es mit 16 Pappkärtchen, wo auf jedem ein bestimmtes
Muster aus vier Nullen/Einsen abgebildet war. Jede der
2 hoch 4 Möglichkeiten kam genau einmal vor.

Schon vor einiger Zeit habe ich dieses Puzzle mit LEGO-Steinen
realisiert:

[image]


Die 16 Teile in zufälliger Anordnung. 0 und 1 sind durch die Farben rot und blau ersetzt.



[image]


Meine einfache Konstruktion mit schwarzen Steinen als Unterschicht.



[image]


Links eine Teillösung aus sieben Elementen. Am Ende müssen an allen Übergangsstellen
alle Farben zueinander passen.

Viel Spaß beim Nachbauen und Probieren. Es gibt mehr als 400 Lösungen.

Ingo.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


Mitglieder, denen dieses MOC gefällt:

doktorjoerg , Custer , Cran , Seeteddy , Legomichel , Dirk1313 , renrew , Legobecker , Plastik , MARPSCH , fannie1981 , Lukutus , cimddwc , doe , uefchen , Titus , naseneis , nvneuss , JuL (19 Mitglieder)

36 vorhergehende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen Beitragsbaum

drdwo
04.07.2016, 16:25

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Permalink

1000steine-Code

BBCode

HTML


Noch ein paar Ergänzungen/Hinweise:

1) Warum ist es gut, möglichst früh starke Constraints zu haben?

Stärkere Constraints versursachen einen kleineren Suchbaum. Um so früher, um so kleiner.
Beispiel: Stellen wir uns einen Baum der Höhe 10 mit zwei Kindern an der Wurzel vor,
die Knoten der anderen Ebenen haben je ein Kind. Das sind 19 Knoten. Ist die Verzweigung erst auf der neunten Ebene,
sind es 11 Knoten. Es ist also besser, die Suche möglichst früh einzuschränken.

2) Abbruch der Suche

Wir erzeugen viele zufällige 3-Farben Lösungen und zählen jeweils die Versuche bis wir Tiefe 78 erreicht haben, um ein Gefühl
dafür zu bekommen, wann es sich lohnt bei dieser Suchtiefe die Suche abzubrechen.

Die Zahl der Versuche in einer Suchtiefe variiert sehr stark von Lösung zu Lösung.
Stellen wir zum Beispiel fest, das sich bei 10% der Lösungen bei Suchtiefe 78 die Zahl der Versuche weniger als 2% der durchschnittlichen
Versuchszahl an dieser Tiefe ergibt, dann erhalten wir schneller Lösungen, wenn wir nach 2% der durchschnittlichen Versuche bei Tiefe 78 abbrechen. Nämlich durchnittlich 5 mal so viele bei vorgegebener Suchzeit. Diese Methode lässt sich auf andere Suchtiefen übertragen.

Beim 4-Farben Problem haben wir zunächst nur Versuchszahlen bei Tiefe <= 254. Trotzdem können wir versuchen, die Ergebnisse aus dem 3-Farben Problem (mit vollständigen Lösungen) zu übertragen um abzuschätzen, wann wir eine Suche abbrechen sollten.

3) Variation der Suche

Das Abbrechen funktioniert natürlich nur, wenn jede Suche jedesmal anders verläuft. Man kann z.B. die Reihenfolge der Steine ändern.
Arbeitet man mit einer vorgegebenen 3-Farben Lösung die man erweitert, so sollte man darauf achten viele 3-er Lösungen mit verschiedenen
Aussenkanten zu verwenden (ich selbst hatte ca. 16000 3er Lösungen generiert).

4) Lösung

Inzwischen habe ich eine (potentielle) Lösung gefunden, vielleicht kann jemand anderes versuchen, sie zu verifizieren?
Die 256 Teile sind folgendermassen numeriert (beginnend bei 0, die Farben sind von 0-3 kodiert):

0: [0, 0, 0, 0]; 1: [1, 0, 0, 0]; 2: [2, 0, 0, 0]; 3: [3, 0, 0, 0]; 4: [0, 1, 0, 0]; 5: [1, 1, 0, 0]; 6: [2, 1, 0, 0]; 7: [3, 1, 0, 0]; 8: [0, 2, 0, 0]; 9: [1, 2, 0, 0]; 10: [2, 2, 0, 0]; 11: [3, 2, 0, 0]; 12: [0, 3, 0, 0]; 13: [1, 3, 0, 0]; 14: [2, 3, 0, 0]; 15: [3, 3, 0, 0]; 16: [0, 0, 1, 0]; 17: [1, 0, 1, 0]; 18: [2, 0, 1, 0]; 19: [3, 0, 1, 0]; 20: [0, 1, 1, 0]; 21: [1, 1, 1, 0]; 22: [2, 1, 1, 0]; 23: [3, 1, 1, 0]; 24: [0, 2, 1, 0]; 25: [1, 2, 1, 0]; 26: [2, 2, 1, 0]; 27: [3, 2, 1, 0]; 28: [0, 3, 1, 0]; 29: [1, 3, 1, 0]; 30: [2, 3, 1, 0]; 31: [3, 3, 1, 0]; 32: [0, 0, 2, 0]; 33: [1, 0, 2, 0]; 34: [2, 0, 2, 0]; 35: [3, 0, 2, 0]; 36: [0, 1, 2, 0]; 37: [1, 1, 2, 0]; 38: [2, 1, 2, 0]; 39: [3, 1, 2, 0]; 40: [0, 2, 2, 0]; 41: [1, 2, 2, 0]; 42: [2, 2, 2, 0]; 43: [3, 2, 2, 0]; 44: [0, 3, 2, 0]; 45: [1, 3, 2, 0]; 46: [2, 3, 2, 0]; 47: [3, 3, 2, 0]; 48: [0, 0, 3, 0]; 49: [1, 0, 3, 0]; 50: [2, 0, 3, 0]; 51: [3, 0, 3, 0]; 52: [0, 1, 3, 0]; 53: [1, 1, 3, 0]; 54: [2, 1, 3, 0]; 55: [3, 1, 3, 0]; 56: [0, 2, 3, 0]; 57: [1, 2, 3, 0]; 58: [2, 2, 3, 0]; 59: [3, 2, 3, 0]; 60: [0, 3, 3, 0]; 61: [1, 3, 3, 0]; 62: [2, 3, 3, 0]; 63: [3, 3, 3, 0]; 64: [0, 0, 0, 1]; 65: [1, 0, 0, 1]; 66: [2, 0, 0, 1]; 67: [3, 0, 0, 1]; 68: [0, 1, 0, 1]; 69: [1, 1, 0, 1]; 70: [2, 1, 0, 1]; 71: [3, 1, 0, 1]; 72: [0, 2, 0, 1]; 73: [1, 2, 0, 1]; 74: [2, 2, 0, 1]; 75: [3, 2, 0, 1]; 76: [0, 3, 0, 1]; 77: [1, 3, 0, 1]; 78: [2, 3, 0, 1]; 79: [3, 3, 0, 1]; 80: [0, 0, 1, 1]; 81: [1, 0, 1, 1]; 82: [2, 0, 1, 1]; 83: [3, 0, 1, 1]; 84: [0, 1, 1, 1]; 85: [1, 1, 1, 1]; 86: [2, 1, 1, 1]; 87: [3, 1, 1, 1]; 88: [0, 2, 1, 1]; 89: [1, 2, 1, 1]; 90: [2, 2, 1, 1]; 91: [3, 2, 1, 1]; 92: [0, 3, 1, 1]; 93: [1, 3, 1, 1]; 94: [2, 3, 1, 1]; 95: [3, 3, 1, 1]; 96: [0, 0, 2, 1]; 97: [1, 0, 2, 1]; 98: [2, 0, 2, 1]; 99: [3, 0, 2, 1]; 100: [0, 1, 2, 1]; 101: [1, 1, 2, 1]; 102: [2, 1, 2, 1]; 103: [3, 1, 2, 1]; 104: [0, 2, 2, 1]; 105: [1, 2, 2, 1]; 106: [2, 2, 2, 1]; 107: [3, 2, 2, 1]; 108: [0, 3, 2, 1]; 109: [1, 3, 2, 1]; 110: [2, 3, 2, 1]; 111: [3, 3, 2, 1]; 112: [0, 0, 3, 1]; 113: [1, 0, 3, 1]; 114: [2, 0, 3, 1]; 115: [3, 0, 3, 1]; 116: [0, 1, 3, 1]; 117: [1, 1, 3, 1]; 118: [2, 1, 3, 1]; 119: [3, 1, 3, 1]; 120: [0, 2, 3, 1]; 121: [1, 2, 3, 1]; 122: [2, 2, 3, 1]; 123: [3, 2, 3, 1]; 124: [0, 3, 3, 1]; 125: [1, 3, 3, 1]; 126: [2, 3, 3, 1]; 127: [3, 3, 3, 1]; 128: [0, 0, 0, 2]; 129: [1, 0, 0, 2]; 130: [2, 0, 0, 2]; 131: [3, 0, 0, 2]; 132: [0, 1, 0, 2]; 133: [1, 1, 0, 2]; 134: [2, 1, 0, 2]; 135: [3, 1, 0, 2]; 136: [0, 2, 0, 2]; 137: [1, 2, 0, 2]; 138: [2, 2, 0, 2]; 139: [3, 2, 0, 2]; 140: [0, 3, 0, 2]; 141: [1, 3, 0, 2]; 142: [2, 3, 0, 2]; 143: [3, 3, 0, 2]; 144: [0, 0, 1, 2]; 145: [1, 0, 1, 2]; 146: [2, 0, 1, 2]; 147: [3, 0, 1, 2]; 148: [0, 1, 1, 2]; 149: [1, 1, 1, 2]; 150: [2, 1, 1, 2]; 151: [3, 1, 1, 2]; 152: [0, 2, 1, 2]; 153: [1, 2, 1, 2]; 154: [2, 2, 1, 2]; 155: [3, 2, 1, 2]; 156: [0, 3, 1, 2]; 157: [1, 3, 1, 2]; 158: [2, 3, 1, 2]; 159: [3, 3, 1, 2]; 160: [0, 0, 2, 2]; 161: [1, 0, 2, 2]; 162: [2, 0, 2, 2]; 163: [3, 0, 2, 2]; 164: [0, 1, 2, 2]; 165: [1, 1, 2, 2]; 166: [2, 1, 2, 2]; 167: [3, 1, 2, 2]; 168: [0, 2, 2, 2]; 169: [1, 2, 2, 2]; 170: [2, 2, 2, 2]; 171: [3, 2, 2, 2]; 172: [0, 3, 2, 2]; 173: [1, 3, 2, 2]; 174: [2, 3, 2, 2]; 175: [3, 3, 2, 2]; 176: [0, 0, 3, 2]; 177: [1, 0, 3, 2]; 178: [2, 0, 3, 2]; 179: [3, 0, 3, 2]; 180: [0, 1, 3, 2]; 181: [1, 1, 3, 2]; 182: [2, 1, 3, 2]; 183: [3, 1, 3, 2]; 184: [0, 2, 3, 2]; 185: [1, 2, 3, 2]; 186: [2, 2, 3, 2]; 187: [3, 2, 3, 2]; 188: [0, 3, 3, 2]; 189: [1, 3, 3, 2]; 190: [2, 3, 3, 2]; 191: [3, 3, 3, 2]; 192: [0, 0, 0, 3]; 193: [1, 0, 0, 3]; 194: [2, 0, 0, 3]; 195: [3, 0, 0, 3]; 196: [0, 1, 0, 3]; 197: [1, 1, 0, 3]; 198: [2, 1, 0, 3]; 199: [3, 1, 0, 3]; 200: [0, 2, 0, 3]; 201: [1, 2, 0, 3]; 202: [2, 2, 0, 3]; 203: [3, 2, 0, 3]; 204: [0, 3, 0, 3]; 205: [1, 3, 0, 3]; 206: [2, 3, 0, 3]; 207: [3, 3, 0, 3]; 208: [0, 0, 1, 3]; 209: [1, 0, 1, 3]; 210: [2, 0, 1, 3]; 211: [3, 0, 1, 3]; 212: [0, 1, 1, 3]; 213: [1, 1, 1, 3]; 214: [2, 1, 1, 3]; 215: [3, 1, 1, 3]; 216: [0, 2, 1, 3]; 217: [1, 2, 1, 3]; 218: [2, 2, 1, 3]; 219: [3, 2, 1, 3]; 220: [0, 3, 1, 3]; 221: [1, 3, 1, 3]; 222: [2, 3, 1, 3]; 223: [3, 3, 1, 3]; 224: [0, 0, 2, 3]; 225: [1, 0, 2, 3]; 226: [2, 0, 2, 3]; 227: [3, 0, 2, 3]; 228: [0, 1, 2, 3]; 229: [1, 1, 2, 3]; 230: [2, 1, 2, 3]; 231: [3, 1, 2, 3]; 232: [0, 2, 2, 3]; 233: [1, 2, 2, 3]; 234: [2, 2, 2, 3]; 235: [3, 2, 2, 3]; 236: [0, 3, 2, 3]; 237: [1, 3, 2, 3]; 238: [2, 3, 2, 3]; 239: [3, 3, 2, 3]; 240: [0, 0, 3, 3]; 241: [1, 0, 3, 3]; 242: [2, 0, 3, 3]; 243: [3, 0, 3, 3]; 244: [0, 1, 3, 3]; 245: [1, 1, 3, 3]; 246: [2, 1, 3, 3]; 247: [3, 1, 3, 3]; 248: [0, 2, 3, 3]; 249: [1, 2, 3, 3]; 250: [2, 2, 3, 3]; 251: [3, 2, 3, 3]; 252: [0, 3, 3, 3]; 253: [1, 3, 3, 3]; 254: [2, 3, 3, 3]; 255: [3, 3, 3, 3];

Dann ist eine (potentielle) Lösung - p:t bedeutet Teil t ist an Position p, wobei die Positionen Reihe für Reihe durchnumeriert sind:

|0:4|1:17|2:64|3:16|4:17|5:37|6:137|7:38|8:149|9:77|10:47|11:163|12:140|13:35|14:184|15:218|16:80|17:84|18:81|19:17|20:33|21:34|22:18|23:72|24:6|25:49|26:216|27:122|28:210|29:120|30:187|31:135|32:5|33:21|34:85|35:65|36:8|37:34|38:164|39:161|40:128|41:12|42:55|43:205|44:23|45:93|46:75|47:50|48:0|49:20|50:69|51:1|52:32|53:168|54:170|55:138|56:2|57:48|58:252|59:243|60:244|61:245|62:193|63:60|64:160|65:148|66:97|67:144|68:88|69:90|70:106|71:146|72:96|73:156|74:79|75:31|76:111|77:143|78:3|79:44|80:154|81:102|82:169|83:166|84:165|85:133|86:41|87:150|88:105|89:182|90:241|91:196|92:57|93:226|94:176|95:232|96:86|97:73|98:26|99:74|100:42|101:130|102:40|103:134|104:25|105:94|106:127|107:211|108:124|109:203|110:14|111:59|112:101|113:129|114:36|115:145|116:104|117:162|118:152|119:98|120:132|121:53|122:237|123:183|124:119|125:115|126:240|127:236|128:102|129:66|130:24|131:70|132:9|133:10|134:22|135:89|136:82|137:108|138:171|139:190|140:215|141:109|142:175|143:155|144:246|145:209|146:100|147:177|148:208|149:112|150:212|151:117|152:229|153:185|154:234|155:174|156:151|157:121|158:250|159:214|160:95|161:119|162:233|163:158|164:71|165:45|166:167|167:189|168:235|169:142|170:43|171:186|172:198|173:61|174:255|175:231|176:197|177:29|178:91|179:118|180:225|181:34|182:58|183:222|184:107|185:178|186:200|187:30|188:83|189:76|190:15|191:27|192:51|193:228|194:181|195:253|196:251|197:194|198:28|199:103|200:102|201:110|202:147|203:116|204:213|205:113|206:224|207:180|208:51|209:11|210:46|211:191|212:239|213:131|214:52|215:201|216:54|217:249|218:230|219:141|220:39|221:173|222:187|223:206|224:179|225:192|226:56|227:254|228:219|229:114|230:220|231:99|232:188|233:223|234:123|235:242|236:248|237:202|238:62|239:195|240:126|241:227|242:172|243:159|244:87|245:125|246:247|247:217|248:78|249:7|250:13|251:63|252:207|253:19|254:92|255:67



Kirk
04.07.2016, 17:32

Als Antwort auf den Beitrag von drdwo

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo Dietmar,

ich kann Deine Lösung bislang nur teilweise bestätigen: Die 256 Bauteilesind zumindest schon einmal eindeutig (aber das war ja auch der einfache Teil).
Die Lösung als solche kann ich leider bislang noch nicht bestätigen, da mir nicht ganz klar ist, wie Du die Teile anordnen möchtest.

Sehe ich das Richtig: Das Spielfeld sieht wie folgt aus:
0 | 1 | 2 | 3 ...
16 | 17 | 18 | 19 ...
32 | 33 | 34 | 35 ...

Wenn ich jetzt das erste Teil legen möchte, sieht das nach Deiner Lösung wie folgt aus:

Teil: 4: [0, 1, 0, 0]
Position: |0:4|

Die obere linke Ecke müßte daher wie folgt aussehen:
0 1
0 0

Daran schließt dann das nächste Teil an:
Teil: 17: [1, 0, 1, 0]
Position: 1:17

0 1 | 1 0
0 0 | 1 0

Schon beim 2. Teil klappt's also nicht. Oder verwendest Du eine andere Anordnung?

Gruß

Thomas


\\//_ Build long and ℘rosper!


IngoAlthoefer
04.07.2016, 18:12

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo Dietmar, hallo Thomas,
ich habe noch etwas mehr Probleme beim Nachvollziehen:
Die Liste hat 1:17 und etwas später 4:17 ...
Das würde bedeuten, dass das Teil 17 (mindestens) zwei Mal vorkäme.

Hmm, Ingo.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


drdwo
04.07.2016, 18:51

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Das ist richtig, es gibt ein Problem mit der Lösung. Teil 17 wird zweimal angezeigt. Da gibt es noch ein Problem mit dem Verfahren. Beim 2-Farben Problem bekomme ich auch 800 Lösungen, also hat es mit den Verbesserungen zu tun. Das vorher berechnete 9x9er, das ich als Basis verwende, wurde anscheinend falsch eingetragen. Ein 256er sollte aber trotzdem möglich sein, werde den Fehler beheben und es dann weiter versuchen.



Kirk
04.07.2016, 19:47

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

IngoAlthoefer hat geschrieben:

Die Liste hat 1:17 und etwas später 4:17 ...


Ups... das hatte ich bei meiner Prüfung ganz übersehen. Tatsächlich kommt das Teil 17 sogar 3x vor (genau so wie die Teile 34 und 102), wohingegen diverse andere Teile fehlen. Ich habe dies jetzt bei meiner Gegenprobe berücksichtigt und bin schon gespannt, wann Dietmars Computer die nächste Lösung ausspuckt.


\\//_ Build long and ℘rosper!


drdwo
04.07.2016, 22:41

Als Antwort auf den Beitrag von Kirk

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Vielen Dank für die Unterstützung. Wie auch Ingo schon bemerkt hat, gab es noch einen Bug der jetzt hoffentlich gefixed ist. Das nächste Mal gibt es noch eine Ausgabe in der Form (hier für das 9x9er):

00 01 10 01 12 20 02 22 20
00 00 00 01 10 00 02 22 20

00 00 00 01 10 00 02 22 20
10 01 11 10 02 20 01 11 10

10 01 11 10 02 20 01 11 10
11 11 11 10 00 01 12 22 21

11 11 11 10 00 01 12 22 21
01 10 00 01 12 21 11 10 02

01 10 00 01 12 21 11 10 02
02 20 02 20 00 00 02 22 21

02 20 02 20 00 00 02 22 21
11 11 10 02 22 21 12 21 11

11 11 10 02 22 21 12 21 11
12 21 12 20 02 21 12 22 20

12 21 12 20 02 21 12 22 20
21 12 22 22 22 20 01 12 21

21 12 22 22 22 20 01 12 21
10 02 20 00 01 12 22 20 01

da sieht man schneller was Sache ist. Die Performance der Suche scheint unverändert - alle paar Minuten einen 253er. Morgen oder ünermorgen haben wir dann hoffentlich einen korrekten 256er.



IngoAlthoefer
05.07.2016, 08:47

Als Antwort auf den Beitrag von drdwo

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Hallo Dietmar,

danke für die sehr schön formatierte 3er-Lösung.
In der Ecke links oben (4x4 Teile) sieht man sehr
gut, wie Du mit einer 0-1-Lösung begonnen hast.

Gruss, Ingo.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


drdwo
05.07.2016, 10:13

Als Antwort auf den Beitrag von IngoAlthoefer

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

Also war die 3er korrekt? Hoffentlich keine doppelten Teile mehr. Es gibt schlechte Nachrichten - der korrigierte Algorithmus ist jetzt doch erheblich langsamer, heute Nacht haben meine Rechner nur 4 254er gefunden, obwohl ich neben meinen 3 Hauptrechnern noch 2 Reserve-Maschinen aktiviert hatte. Zusammen schaffen sie auf insgesamt 52 parallelen Threads knapp 1E9 Versuche pro Sekunde. Da der Sprung 253->254 jetzt viel schwerer ist, vermute ich das auch für die zwei verbleibenden Sprünge. Hier ein 254er

10 00 00 01 12 20 02 22 21 12 22 22 23 30 03 31
11 11 10 00 00 01 12 21 10 03 32 23 32 20 01 11

11 11 10 00 00 01 12 21 10 03 32 23 32 20 01 11
01 11 10 01 12 22 21 12 22 21 12 23 31 13 33 30

01 11 10 01 12 22 21 12 22 21 12 23 31 13 33 30
10 00 01 11 11 12 22 20 02 23 30 03 31 10 02 22

10 00 01 11 11 12 22 20 02 23 30 03 31 10 02 22
00 00 01 10 02 22 20 02 20 00 00 00 03 33 33 33

00 00 01 10 02 22 20 02 20 00 00 00 03 33 33 33
20 02 21 12 21 11 10 02 22 23 30 03 33 33 31 11

20 02 21 12 21 11 10 02 22 23 30 03 33 33 31 11
21 11 11 12 21 12 20 01 10 02 21 13 32 21 12 23

21 11 11 12 21 12 20 01 10 02 21 13 32 21 12 23
02 22 20 02 20 01 11 12 21 13 30 00 00 03 32 20

02 22 20 02 20 01 11 12 21 13 30 00 00 03 32 20
22 22 20 00 00 02 21 10 01 11 11 13 33 31 13 32

22 22 20 00 00 02 21 10 01 11 11 13 33 31 13 32
00 01 12 22 21 10 00 02 20 03 33 32 20 01 12 22

00 01 12 22 21 10 00 02 20 03 33 32 20 01 12 22
31 13 31 13 31 13 32 23 31 11 10 02 23 32 23 30

31 13 31 13 31 13 32 23 31 11 10 02 23 32 23 30
20 01 10 02 22 23 32 21 13 32 23 31 11 10 01 13

20 01 10 02 22 23 32 21 13 32 23 31 11 10 01 13
30 03 30 03 31 10 03 32 21 11 12 21 13 32 23 31

30 03 30 03 31 10 03 32 21 11 12 21 13 32 23 31
12 20 02 22 23 31 10 01 13 31 13 33 33 33 30 02

12 20 02 22 23 31 10 01 13 31 13 33 33 33 30 02
33 33 30 03 33 30 03 31 13 33 30 01 13 30 03 32

33 33 30 03 33 30 03 31 13 33 30 01 13 30 03 32
12 22 23 32 23 30 03 32 20 03 33 30 03 32 23 30

xx xx 23 32 23 30 03 32 20 03 33 30 03 32 23 30
xx xx 22 23 31 10 02 20 03 30 00 01 12 21 13 31

Vielleicht inspiriert die jemand zu einer Verbesserungsidee. Womöglich schafft man es irgendwie, Teile die am Schluss mit einer höheren Wahrscheinlichkeit zusammenpassen vorher mit einer geringeren Wahrscheinlichkeit zu legen. Das vordefinierte 9x9er geht in diese Richtung, vielleicht geht aber noch mehr.



cimddwc
05.07.2016, 11:08

Als Antwort auf den Beitrag von drdwo

Re: Puzzle mit 4x4 Teilen (etwas offtopic)

drdwo hat geschrieben:

Es gibt schlechte Nachrichten - der korrigierte Algorithmus ist jetzt doch erheblich langsamer, heute Nacht haben meine Rechner nur 4 254er gefunden, obwohl ich neben meinen 3 Hauptrechnern noch 2 Reserve-Maschinen aktiviert hatte. Zusammen schaffen sie auf insgesamt 52 parallelen Threads knapp 1E9 Versuche pro Sekunde.

Dann bin ich ja beruhigt, dass mein simples Programm nach einer Woche Mo.-Fr. tagsüber single-threaded in einer virtuellen Maschine immer noch nicht mehr als 253 Steine verbaut hat.

Die 3x3-Variante meint übrigens, derzeit 23,6 Mio. Lösungen gefunden zu haben, im Sekundentakt kommen immer noch einige bis ein paar Dutzend dazu.

Grüße,
Andreas



IngoAlthoefer
05.07.2016, 15:03

Als Antwort auf den Beitrag von drdwo

Puzzle mit 9x9 Teilen (kompakte Darstellung)

Hallo Dietmar,

Deine 9x9-Lösung habe ich jetzt auf Korrektheit geprüft - sie ist
tatsächlich eine. Und ich habe sie als kompaktes Mosaik realisiert.
Wegen des Overlaps braucht man tatsächlich nur die 10x10 Einzel-Einträge,
statt der 9x9 Vierer.

drdwo hat geschrieben:

00 01 10 01 12 20 02 22 20
00 00 00 01 10 00 02 22 20

00 00 00 01 10 00 02 22 20
10 01 11 10 02 20 01 11 10

10 01 11 10 02 20 01 11 10
11 11 11 10 00 01 12 22 21

11 11 11 10 00 01 12 22 21
01 10 00 01 12 21 11 10 02

01 10 00 01 12 21 11 10 02
02 20 02 20 00 00 02 22 21

02 20 02 20 00 00 02 22 21
11 11 10 02 22 21 12 21 11

11 11 10 02 22 21 12 21 11
12 21 12 20 02 21 12 22 20

12 21 12 20 02 21 12 22 20
21 12 22 22 22 20 01 12 21

21 12 22 22 22 20 01 12 21
10 02 20 00 01 12 22 20 01

Die Bedeutung der Farben ist
schwarz=0, orange=1, rot=2.

[image]


Das Mosaik ohne Markierungen.

[image]


Markiert ist die
0 1
0 0
links oben.


[image]


Markiert ist die
1 0
0 0
links oben.


[image]


Markiert ist die
0 2
0 2
rechts oben.

In dem 10x10-Mosaik kommt jedes dreifarbige 2x2-Muster genau einmal vor!

Analog wird man eine hoffentlich bald kommende 16x16-Lösung für das 4-Farben-Muster
durch ein kompaktes 17x17-Gitter darstellen können.

Ingo.


Mein MoC ist fertig, wenn ich
nichts mehr wegnehmen mag.


32 nachfolgende Beiträge sind ausgeblendet

Alle anzeigen Immer alle anzeigen

Gesamter Thread: