9

I have been pondering this question for some time now and it's a bit out of my scope to solve it. I am curious to know how many possible arrangements are possible for the river 1 expansion for Carcassonne.

The rules for playing the river are as follows: The source tile is played first, The lake tile is played last, and If two river bends are drawn in sequence they must have opposing orientation.

I understand the following: The first and last tile played will not factor into the counting so we just look at the 10 tiles inbetween. Each tile has 2 orientations and there are 8 unique tiles, 1 repeated corner, and one repeated straight. We must also exclude possibilities that become unplayable when the river curves in onto itself.

I posted an image of all the tiles from the river expansion.

My preliminary guesswork at counting is

(2^8)10!/2!2!

My rationale 10!/2!2! Because order of selection matters and repition tiles are excluded by dividing by 2!

2^8 Because each tile can be place in 2 ways( the 2 straight tile are not included because they are not unique)

I know this is wrong. It's just my first guess at it, and it has not excluded possibilities where the river curves into itself and creates an unplayable game. Any assistance would be much appreciated, thanks!

enter image description here

  • 2
    Are you counting artistic uniqueness, or mechanical uniqueness? (ie would reversing the double city river in the upper left count as a new setup? Would swapping the two plain straights?) – Arcanist Lupus Sep 20 '18 at 5:48
  • It seems this configuration is invalid, since it has two U-turns: modernjive.com/carcassonne/carcassonnetheriver.pdf – Glorfindel Sep 20 '18 at 10:30
  • Arcanist Lupus, I was more curious about mechanical uniqness. So, as you mention rotating the double city would would not create a unique playable board and neither would swapping the plane straights. – Ryan Sep 20 '18 at 14:36
  • Glorfindel, you raise a very good point. I wanted to post a picture to show an example of all the tiles available in the river expansion (1), but I realise this is a bad example as it demonstrates a board which breaks the rules. Thanks for pointing that out! – Ryan Sep 20 '18 at 14:38
11

As mentioned in the comments, I think the U-turns of the river in your example board are invalid; see (this version of) the rules. If, as you say "We must also exclude possibilities that become unplayable when the river curves in onto itself.", the Java program at the bottom will calculate all possible boards, with the caveat that it distinguishes between the two straights with two grass borders and between the two bends with two grass borders (we can correct for those later). Here's an example board it generates:

enter image description here

The total is a whopping 1,715,761,152 boards, where I've already assumed the source always flows to the right (otherwise, you'd just get a rotated version of the full board). But some of those are equivalent according to your definition:

  • We can always swap the two bends with two grass borders
  • We can always swap the two straights with two grass borders
  • We can always rotate the first of those straights 180 degrees
  • We can always rotate the second of those straights 180 degrees
  • We can always rotate the straight with two town borders 180 degrees
  • We can always rotate the straight with two road borders 180 degrees

This means that we have to divide the total by 26, so there are 1,715,761,152 / 64 = 26,808,768, almost 27 million different (full) boards according to your definition.

The Java program is as follows:

package com.stackexchange.boardgames;

public class CarcassonneRiverSimulator {
    private static Tile endTile;
    private static Tile[] tiles;
    private static int numberOfBoards;

    public static void main(String[] args) {
        // as shown in https://boardgames.stackexchange.com/q/43479, North -> East -> South -> West
        Tile startTile = new Tile(new Border[] { Border.Grass, Border.River, Border.Grass, Border.Grass }, false);
        tiles = new Tile[] { startTile,
                new Tile(new Border[] { Border.Town, Border.River, Border.Town, Border.River }, false),
                new Tile(new Border[] { Border.Grass, Border.River, Border.Grass, Border.River }, false),
                new Tile(new Border[] { Border.Road, Border.Road, Border.River, Border.River }, true),
                new Tile(new Border[] { Border.River, Border.Grass, Border.Grass, Border.River }, true),
                new Tile(new Border[] { Border.Grass, Border.River, Border.Grass, Border.River }, false),
                new Tile(new Border[] { Border.Town, Border.River, Border.Road, Border.River }, false),
                new Tile(new Border[] { Border.Grass, Border.River, Border.River, Border.Grass }, true),
                new Tile(new Border[] { Border.River, Border.River, Border.Town, Border.Town }, true),
                new Tile(new Border[] { Border.Road, Border.River, Border.Road, Border.River }, false),
                new Tile(new Border[] { Border.Grass, Border.River, Border.Road, Border.River }, false) };
        endTile = new Tile(new Border[] { Border.Grass, Border.Grass, Border.Grass, Border.River }, false);

        // Start with the start tile @ 0,0 in the indicated direction
        // x increases to the East, y increases to the South
        startTile.position = new Position(0, 0, North);
        Position nextRiver = new Position(1, 0, West); // i.e. the next tile needs to be at (1, 0) and needs to have a
                                                        // river in
        // the West position

        // Check next tile (recursively)
        nextTile(nextRiver, null);

        System.out.println(numberOfBoards + " valid boards found.");
    }

    private static void nextTile(Position nextRiver, Integer invalidNextRiverDirection) {
        boolean nonPositionedTileFound = false;
        for (Tile tile : tiles) {
            if (tile.position != null)
                continue;
            nonPositionedTileFound = true;
            tryToPlaceTile(nextRiver, tile, invalidNextRiverDirection);
        }
        if (nonPositionedTileFound)
            return;
        // Place end tile (this can fail because one of its grass borders blocks a town or road)
        tryToPlaceTile(nextRiver, endTile, invalidNextRiverDirection);
    }

    private static void tryToPlaceTile(Position nextRiver, Tile tile, Integer invalidNextRiverDirection) {
        // Try to add this tile to the mouth of the river in any of the directions
        // (North = don't rotate, East = rotate 90 degrees clockwise, etc.)
        for (int rotate = North; rotate <= West; rotate++) {
            int riverDirection = (4 + nextRiver.direction - rotate) % 4;
            if (tile.borders[riverDirection] != Border.River)
                continue;

            // Check other borders
            boolean valid = true;
            for (int border = 0; border < 4; border++) {
                if (border == riverDirection)
                    continue;
                int direction = (border + rotate) % 4;
                int x = nextRiver.x + getDx(direction);
                int y = nextRiver.y + getDy(direction);
                for (Tile otherTile : tiles) {
                    if (otherTile.position == null || otherTile.position.x != x || otherTile.position.y != y)
                        continue;
                    if (otherTile.borders[(6 + direction - otherTile.position.direction) % 4] == tile.borders[border])
                        continue;
                    valid = false;
                    break;
                }
                if (!valid)
                    break;
            }
            if (!valid)
                continue;

            // Find next river position
            Position nextNextRiver = null;
            for (int border = 0; border < 4; border++) {
                if (border == riverDirection)
                    continue;
                if (tile.borders[border] != Border.River)
                    continue;
                int nextRiverDirection = (border + rotate + 2) % 4;
                if (invalidNextRiverDirection != null && invalidNextRiverDirection == nextRiverDirection)
                    break;
                tile.position = new Position(nextRiver.x, nextRiver.y, rotate);
                nextNextRiver = new Position(tile.position.x - getDx(nextRiverDirection),
                        tile.position.y - getDy(nextRiverDirection), nextRiverDirection);
                break;
            }

            if (tile == endTile) {
                // Valid board found
                numberOfBoards++;
            } else if (tile.position != null) {
                // Check next tile (recursively)
                nextTile(nextNextRiver, tile.isBend ? (nextRiver.direction + 2) % 4 : null);
            }

            // Reset position
            tile.position = null;
        }
    }

    private static enum Border {
        Grass, River, Road, Town
    }

    private static final int North = 0, East = 1, South = 2, West = 3;

    private static int getDx(int direction) {
        return direction == West ? -1 : direction == East ? 1 : 0;
    }

    private static int getDy(int direction) {
        return direction == North ? -1 : direction == South ? 1 : 0;
    }

    private static class Position {
        public Position(int x, int y, int direction) {
            this.x = x;
            this.y = y;
            this.direction = direction;
        }

        public final int x, y, direction;
    }

    private static class Tile {
        public Tile(Border[] borders, boolean isBend) {
            this.borders = borders;
            this.isBend = isBend;
        }

        public final Border[] borders;
        public final boolean isBend;
        public Position position;

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            int direction = position == null ? 0 : position.direction;
            for (int border = 0; border < 4; border++) {
                if (builder.length() > 0)
                    builder.append(", ");
                builder.append(borders[(4 + border - direction) % 4].toString());
            }
            builder.insert(0, "[");
            builder.append("]");
            return builder.toString() + (position == null ? "" : " @ (" + position.x + ", " + position.y + ")");
        }
    }
}
  • Wow, that is awesome! Thanks for all the work you put into your solution! I really appreciate it. My wife and I are big fans of the game and have played many times now, and I began wondering what the probability would be of laying the same unique river twice or more. I am seeing now with a number that big there is a high chance we will never play the same river twice! – Ryan Sep 20 '18 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.