How many unique outcomes can be made from the 12 river tiles in Carcassonne?

Question

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!

Answer 1

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:

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 2⁶, 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 + ")");
        }
    }
}