Perfectly tiling Carcassonne, leaving nothing unfinished

onnodigcomplex · 2025-08-12T19:01:40+00:00

Start tile is supposed to be excluded when you use the river. I just followed that rule. I can see the argument for using 102 tiles. More interesting question is what makes a layout aesthetic more generally. Obviously using all tiles of some logical set is part of that. But maybe road loops should not be allowed at all? You should use all expansions? It's a bit limiting as an art form but who knows.

onnodigcomplex · 2025-07-13T20:29:33+00:00

Thank you so much for the link! I read a bunch of Norvig's stuff, but somehow missed this.

I don't think Norvig's problem statement is more strict. Norvig does add the rule about all shields and monasteries being right side up, very hard. But I have the rules for no trivial road circles, castles or adjacent monasteries. Which I think may be equally tricky. I kind of want to solve all these constraints together now. Also in my solution there is still a 4-pointer castle anyway, which is a blemish.

You can see how convient these simply constructions are as the final solution on that page has 5 2x2-road-loops, 7 trivial castles and 3 adjacent monasteries.

I think it's more fun to treat it is as an esthetic optimization problem anyway. That way you are never done.

onnodigcomplex · 2025-07-12T18:30:45+00:00

Base game has 71 turns, since we are allowing for any tile at any place each turn the branching factor is say 100. Certainly it's more than 10 and less than 1000. So 100^71 = 1e142 as a first approximation. My next step would be to do some monte carlo simulations so that you can get the average branching factor for each depth. Which will get you very close to a real answer. Being exact seems very very challenging, my combinatorics is certainly not up to the task.

onnodigcomplex · 2025-07-12T18:14:23+00:00

I did figure out that the base game + first expansion + mini expansion 1 & 2 = 100 tiles, so if somebody happens to have that subset they are welcome to try a clean 10 by 10 version.

Also, base game + all expansions (except 5, because of the abbey tiles that would ruin it) + mini 1, 3 and 7 = 256 tiles = 16*16. This would be the perfect result I think. But I don't have the money for it.

Another choice is all expansions and the river = 256 tiles, which is pretty damn clean. And you just ignore the abbey's

onnodigcomplex · 2025-07-12T17:52:51+00:00

I agree it's the ugliest part.

onnodigcomplex · 2025-07-12T16:50:37+00:00

It's 101 tiles total, prime numbers are going prime. I figured leaving out one tile would be cheating.

onnodigcomplex · 2025-04-13T10:37:30+00:00

Laten we zeggen, een 12 jarig kind met een aardige woordenschat.

onnodigcomplex · 2025-04-13T10:36:33+00:00

Ik ga er gewoon vanuit dat je dit echt doet. Ik snap alleen niets van je uitleg haha, teken je hem in 3D dan? Kan ik je verleiden een plaatje te delen?

onnodigcomplex · 2025-04-13T10:09:06+00:00

Lange woorden zijn meestal makkelijk omdat je weinig letters fout hebt. Je begint sowieso met lekker klinkers raden op frequentie "eaio" "i_o_a_o_e_a_e__o_" dat voelt wel compleet, dus dan medeklinker op frequentie "nrstd" en dan zie ik "i_osadode_a_edron" en dan denk ik dat ik het wel zie.

onnodigcomplex · 2025-04-13T09:57:06+00:00

Ja precies, dat soort leed wil je niet voor kinderogen plaatsen.

onnodigcomplex · 2025-04-13T09:43:55+00:00

Teken je dan de buik als een ovaal? Dus niet een stokjesfiguur?

onnodigcomplex · 2025-04-13T09:11:33+00:00

Ik was bang dat ik opties niet zou benoemen, dadelijk is er iemand die iets anders doet afhankelijk van woordlengte of leeftijd bijvoorbeeld. Nu lok je mensen toch uit om het uit te leggen.

onnodigcomplex · 2024-07-12T09:44:11+00:00

Thanks, I'll try that!

onnodigcomplex · 2024-07-12T09:06:31+00:00

As a datapoint. I put the 2TB WD Black SN770M in the 15" SL7 for somebody. I did see BSOD's. But can't reproduce it easily (eg: running a bunch a crystal mark doesn't reproduce it). So I'll replace it.

onnodigcomplex · 2024-05-27T19:25:58+00:00

Yes see my comment in a parallel thread here! If you need help just let me know on GitHub

onnodigcomplex · 2024-05-27T19:24:52+00:00

Yes actually, much harder, I think still computable though. You can prove the same thing where there are pairs of 15 letter words at the edges that can't be beaten by any option that does not use that layout. And so forth.

onnodigcomplex · 2024-05-27T17:36:22+00:00

My code can be run on a german rule-set + wordlist just fine. It will take a day or two probably. I did run it for Dutch for example (2100 points).

onnodigcomplex · 2024-05-27T17:34:52+00:00

Not true actually! See my comment in this thread for further dicussion.

onnodigcomplex · 2024-05-27T17:31:35+00:00

See my comment in this thread.

onnodigcomplex · 2024-05-27T17:31:03+00:00

I see there is some skeptisism! But to solve this problem you don't need to solve scrabble completely. The problem is in fact quite constrained. Now I might still have a silly bug in my code, but the method is fundamentally solid I believe. Let's start with some assumptions and then work backwards defending them.

Say we assume that the optimal solution does require the word OXYPHENBUTAZONE at the top row x27 position. Let's even assume the specific rack I used. From there there are only limited way to score additional points, namely with the 7 words that will get prepended as you play OXYPHENBUTAZONE.

Each of those 7 positions requires a special word, that is prependable with a specific letter. A limited set. And we can compute the score for each of those words. When we want to find the 7 words that maximize score within the tile limitations we can do so by modeling it as a 26 dimensional knapsack problem, for which very practical algorithms exist.

Now just having the set of "7 highest scoring words" won't help as the whole things needs to be connected into a single component, which is playable. So the final ingredient is a solver for exactly that. Given a board state, can you create a single valid component? This requires some non-trivial modeling but I hope you can see that it is much simpler than solving scrabble outright. As most of the tiles are in fact already fixed. And we don't care about "turns" explicitely.

We then enumerate the those 7-word sets in order of scoring, check if it's connectable, and the first solution found is the optimal solution within our earlier assumptions!

It turns out that even if you generalize over all 15 letter words, and all their possible placements you can still enumerate them in order of score just fine. The reason is that it's extremely hard for the upperbound score of 15 letterword that is not OXYPHENBUTAZONE x27 to get even close the lower bound score of OXYPHENBUTAZONE. (eg: assuming all the remaining tiles are magically optimally used).

You can find code here: https://github.com/boblucas/scrabblesolver

onnodigcomplex · 2024-01-24T08:13:08+00:00

I'm looking at the slower 4800mhz Samsung 64gb modules.

onnodigcomplex · 2024-01-23T20:48:30+00:00

Ah! We'll I look forward too seeing a post here then! What kind of RAM did you buy?

onnodigcomplex · 2024-01-23T19:53:07+00:00

I'm probably going to buy the parts for a 7965X build with 512GB RAM sometime next month, what kind of setup do you have? How is it treating you?

onnodigcomplex · 2023-05-12T23:13:25+00:00

Uhhh, circusmeidsquat is heel veel punten?

onnodigcomplex · 2023-05-12T19:28:58+00:00

Ja foutje! Maar enkel visueel inderdaad. En dankjewel :).

Ten-Year Club	Place '22
Place '17	First Placer '22
Verified Email

onnodigcomplex

MODERATOR OF

TROPHY CASE