Is it possible to form a shape with all the Carcassonne tiles?

Posted July 3rd, 2018, Standalone archive

TL;DR

No, it’s mathematically impossible.

Problem

Recently my brother became very interested in the game Carcassonne and while playing, he asked me a question:

Is it possible to create a 9×8 rectangle using all 72 Carcassonne tiles?

Carcassonne tiles Carcassonne tiles, from graphics.cs.cmu.edu

These are all the tiles used in the game. Let’s get started!

First approach: frickin brute force

My initial reaction was along the lines of:

Yea, of course possible, and if not a rectangle, there should be at least one formation of tiles that use all 72.

So I wanted to figure out all of the possible combinations to pave a rectangle. Here was my approach for a brute force algorithm.

1. Categorizing the tiles

Label all the tiles with what they contain, going clockwise from the north position.

  • V indicates village wall
  • R a road
  • P plains

For instance, the tile below will be labeled VRPR.

This is labeled VRPR This is labeled VRPR

To take into account that the tiles can be rotated, we can shift letters in the label. The last tile rotated 90° clockwise makes it RVRP.

The previous tile rotated 90° clockwise VRPR rotated 90° clockwise

2. Following the rules

The base rule of the game is that tiles placed next to one another need to have similar sides. For instance, the formation above is valid, but below isn’t.

Valid formation Valid formation

Invalid formation Invalid formation

In terms of labels, two tiles can be placed next to each other if the letters corresponding to opposite sides are equal. To get the letter of a label corresponding to an orientation, we can assign each direction to a number to lineup with the order in which we labeled the sides. North is 0, East is 1, South is 2, and West 3. This way, the index of the letter in the label corresponds to its orientation. In our example, "VRPR"[1] yields R, because there is a road on the East side of the tile.

The PPRR tile The PPRR tile

If we want to place PPRR on the east side of the VRPR, we need to check if the west side is also a road. And sure enough, "PPRR"[3] yields "R", so the placement of PPRR on the east of VRPR is valid.

We see that adding two to the direction gives the opposite direction, as long as you keep the value between 0 and 3. This you do using the modulo function: 2+2=4 becomes 0 (North), 3+2=5 becomes 1 (East), etc. So generally, this condition needs to be true for a placement to be correct: tileA[direction] === tileB[(direction+2)%4], being the modulo operator.

The brute force algorithm will need to check if a placement is valid using this function:

function isValidPlacement(tileA, tileB, direction) {
    if (tileA[direction] === tileB[(direction+2)%4]) {
        return true;
    } else {
        return false;
    }
}

Or, simplified,

function isValidPlacement(tileA, tileB, direction) {
    return tileA[direction] === tileB[(direction+2)%4]
}

3. Brute force, baby

The time has come to tackle the brute force algorithm. After thinking for a bit, here is what I came up with.

  1. Create a list of length 72 containing all the tiles (even if the same tile gets repeated)
  2. Create an empty 2-dimentional array. This is a grid which tracks the progress of the algorithm
  3. For every cell in the grid (starting from the upper left side), try to place a tile of the list
    • If it is possible
      1. Remove the tile from the list of tiles
      2. Add the tile to the grid
      3. Move to the next cell: neighbor right if possible, next row left if not
    • If it is not, rotate the tile and try again
    • If the list of usable tiles has been depleted, it means that the current combination is not a possible solution
      • Go back one step
      • Remove possible tile at that spot
      • Try next tile on the list
    • For cells located at the edge of the grid, you can suppose the outer wall of the rectangle is composed of plains only
  4. When you arrive at the last cell and a possible tile has been found, display the grid and act as if the tile is not valid

I’ve not yet implemented this algorithm in JavaScript, but I reckon it should be straightforward.

4. Wait, how many iterations?

I had done all of this without asking a crucial question: how many iterations will the brute force algorithm have to go through?

Well, you start with 72 tiles. Once you place the first tile, you’ll be left with 71 tiles to choose from for your next move. Then you’ll be left with 70, then 69, and so on until 1. So the number of possible combinations is 72×71×…×1=72!=6×10103, that’s 6 and 103 zero’s behind it, which is 1021 times as many atoms as there are estimated to be in the universe[1]. And that’s not even taking rotation into account[2]!

Mind = blown Mind = blown

Bad news for me but good for my CPU, the brute force algorithm wasn’t going to work.

Proof by disproof

I was pretty bummed, but then it dawned on me that in science, it’s often much easier to prove something is false than to prove it is true. The new question then is: how do we prove that you can’t pave a surface with all the Carcassonne tiles?

What could possibly make the challenge impossible? Well, let’s look at villages. When you create a village, you have to start with a wall. To close said village, you also need a wall, and to extend it, you need walls on both sides perpendicular to the direction of the extension. Altogether, all villages in Carcassonne have an even number of walls.

Examples of villages A perfectly fine village has an even number of walls

And because you can’t just leave a village open (even on the border of the grid, otherwise it would be too easy), the challenge is only possible if the total number of walls is even.

Carcassonne tiles Let’s count the walls!

There are a grand total of 63 walls in the basic Carcassonne tiles, and we all know what that means…

Conclusion

It is impossible to use all the Carcassonne tiles to construct a rectangle or any figure, really.

However hard you might try and be close to succeeding the challenge, you’ll always be left with one open village.

That’s about it, thank you for reading!


  1. Universe today, How Many Atoms Are There in the Universe? ↩︎

  2. Most of the pieces can be rotated 4 times (with the exceptions of the RPRP pieces, which present one axis of symmetry), so the total number of iterations is just about (72×4)!=7×10584 ↩︎


Exporting pens made easy

Posted April 21, 2017 on Codepen, Standalone archive

Demo GIF

Update 1 (06/2017)

Support added for list view

Update 2 (07/2018)

Fix for Firefox and added dialog boxes to help the user

Added iframe utilities to the post, showing the process

Added help GIF

var links = [], titles, data, accept, link;

// Get all the pen IDs on the page
if (window.location.href.indexOf('?grid_type=list') === -1) {
    titles = document.getElementsByClassName('cover-link');
    for (var i = 0; i < titles.length; i++) {
        links.push(titles[i].href);
    }
} else {
    titles = document.getElementsByClassName('title');
    for (var i = 0; i < titles.length; i++) {
        links.push(titles[i].firstElementChild.href);
    }
}

// Alert the user if getting pen IDs failed
if (links.length === 0) {
    alert('Download pens: No pens found on this page :(')
} else {
    // Warn the user about lag, if user accepts launch download
    accept = confirm('Starting download...\nIf not all pens start downloading, please check if you have allowed codepen.io to display pop-ups\n\nTabs will fly open and close, THIS MAY LAG YOUR COMPUTER. Do you want to continue?')
    if (accept) {
        // Generate download links and click them
        for (var i = 0; i < links.length; i++) {
            links[i] = links[i].replace(/http:\/\/codepen.io\/|https:\/\/codepen.io\//, '');
            data = links[i].split('/pen/');
            link = document.createElement('a');
            link.href = '//codepen.io/' + data[0] + '/share/zip/' + data[1];
            link.target = '_blank';
            // Need to add the link to the body for Firefox
            document.body.appendChild(link);
            link.setAttribute("type", "hidden");
            link.click();
        }
    }
}

Updated complete script

The problem

So you’ve been on Codepen for a while and you’ve created quite a lot of pens. Being very proud of said pens, you’ve surely been thinking

Gosh, I would really like to save all of my work to my local drive, but going through my pens one by one is reaaaaaally tiring!

Fear not, valorous programmer! I have made a way to make exporting pens great again!

TL;DR

Drag this link to your bookmark bar. Go to your Codepen profile, and click the link. All the pens on the page will start downloading. If they don’t, allow Codepen to display pop-ups

Codepen export plugin

Nice.

The solution

The export link

First, let’s take a look at how Codepen manages pen exports. I clicked the Export button and got the link adress of Export .zip

https://codepen.io/ninivert/share/zip/PmqOMp/

Hmmm, very interesting! So I entered the link in my adress bar and sure enough, my pen started downloading!

Getting pen adresses

So we need two components to generate our export links

  • the username (here it was ninivert)
  • the pen hash (here it was PmqOMp)

Now how do we get these components? Let’s look at a classic pen URL

https://codepen.io/ninivert/pen/PmqOMp

It’s very easy to get these components from the pen URL

var url = 'https://codepen.io/ninivert/pen/PmqOMp'
url = url.replace(/http:\/\/codepen.io\/|https:\/\/codepen.io\//, '')
url     // ninivert/pen/PmqOMp
var data = url.split('/pen/')
data[0] // ninivert
data[1] // PmqOMp

Now, let’s recompose the export URL

var export = 'https://codepen.io/' + data[0] + '/share/zip/' + data[1]
export // https://codepen.io/ninivert/share/zip/PmqOMp

Upon entering the URL in my adress bar, the pen starts downloading!

Getting ALL pens

Now, how do we get ALL of a user’s pens? Since the pens have a random hash, it is impossible to loop through all of them. Let’s then use the pen display on one’s Codepen profile page. Upon inspecting the page HTML source code, I see a very easy solution

<a href="http://codepen.io/ninivert/pen/PmqOMp" class="cover-link"></a>

Awww yeah, this means I can use the getElementsByClassName method to get all pens URLs

var links = document.getElementsByClassName('cover-link')
links // [a.cover-link, a.cover-link, ... a.cover-link]
var urls = []
for (var i = 0; i < links.length; i++) {
  urls.push(links[i].href)
}
urls // ['http://codepen.io/ninivert/pen/PmqOMp', ...]

Sidenote: this is only possible in Grid View, as the link with the class only exists there. I’ve considered trying out List View, but it would be more complicated and would cause problems with simultaneous downloads on potato PC’s

Edit: the link in the embedded pen now works on both Grid and List view :)

Aaand the downloads

Let’s generate links and assign each of them to a URL

var a = document.createElement('a')
a.href = '//codepen.io/' + data[0] + '/share/zip/' + data[1]
a.target = '_blank'
a.click()

Sidenote: I intentionally left out https://, otherwise the link would go to a Codepen 404

Script injection

When we assemble everything, we get this script

var links = document.getElementsByClassName('cover-link')
for (var i = 0; i < links.length; i++) {
  var url = links[i].href
  url = str.replace(/http:\/\/codepen.io\/|https:\/\/codepen.io\//, '')
  var data = url.split('/pen/')
  var a = document.createElement('a')
  a.href = '//codepen.io/' + data[0] + '/share/zip/' + data[1]
  a.target = '_blank'
  a.click()
}

Very nice! Now we just need to convert the script to an encoded URI component. To the encoded script, we add javascript:(function(){/* script */})() for it to be actually recognized and executed as a script. Below are the tilities used to minify the code, encode, and generate the link.

var script = /* script above */
var uri = encodeURIComponent(script)
var href = 'javascript:(function()%7B' + uri + '%7D)()%3B'

Tiny JavaScript Minifier

JS to link

Final code

We finally set the last href variable as the link href

<a href="javascript:(function()%7Bvar%20links%20%3D%20document.getElementsByClassName('cover-link')%3B%0Afor%20(var%20i%20%3D%200%3B%20i%20%3C%20links.length%3B%20i%2B%2B)%20%7B%0A%20%20var%20url%20%3D%20links%5Bi%5D.href%3B%0A%20%20url%20%3D%20url.replace(%2Fhttp%3A%5C%2F%5C%2Fcodepen.io%5C%2F%7Chttps%3A%5C%2F%5C%2Fcodepen.io%5C%2F%2F%2C%20'')%3B%0A%20%20var%20data%20%3D%20url.split('%2Fpen%2F')%3B%0A%20%20var%20a%20%3D%20document.createElement('a')%3B%0A%20%20a.href%20%3D%20'%2F%2Fcodepen.io%2F'%20%2B%20data%5B0%5D%20%2B%20'%2Fshare%2Fzip%2F'%20%2B%20data%5B1%5D%3B%0A%20%20a.target%20%3D%20'_blank'%3B%0A%20%20a.click()%3B%0A%7D%7D)()%3B">Export pens</a>

Improvements

The link might not work at first try, because your browser (Chrome 57 for me) is automatically blocking new tabs from being opened. I’d need authorisations only a browser plugin could get to open more than 2 tabs simultaneously. If you’ve got any thoughts on this problem, please let me know in the comments!

Also, the script targets unwanted links on the homepage, but eh.

Thanks a lot for reading!