Combien de résultats uniques peuvent être obtenus à partir des 12 tuiles de la rivière de Carcassonne ?

Question

Je réfléchis à cette question depuis un certain temps déjà et je ne suis pas en mesure de la résoudre. Je suis curieux de savoir combien d'aménagements sont possibles pour l'extension River 1 de Carcassonne.

Les règles pour jouer la rivière sont les suivantes : La tuile source est jouée en premier, La tuile lac est jouée en dernier, et Si deux courbes de la rivière sont dessinées en séquence, elles doivent avoir une orientation opposée.

Je comprends ce qui suit : La première et la dernière tuile jouée ne seront pas prises en compte dans le décompte, donc nous ne considérons que les 10 tuiles intermédiaires. Chaque tuile a 2 orientations et il y a 8 tuiles uniques, 1 coin répété, et une droite répétée. Nous devons également exclure les possibilités qui deviennent injouables lorsque la rivière s'incurve sur elle-même.

J'ai posté une image de toutes les tuiles de l'expansion de la rivière.

Mon estimation préliminaire du décompte est la suivante

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

Mon raisonnement 10!/2!2 ! Parce que l'ordre de sélection importe et que les tuiles de repêchage sont exclues en divisant par 2 !

2^8 Parce que chaque tuile peut être placée de 2 façons (les 2 tuiles droites ne sont pas incluses car elles ne sont pas uniques).

Je sais que c'est mal. Ce n'est que ma première hypothèse, et je n'ai pas exclu la possibilité que la rivière se courbe sur elle-même et crée un jeu injouable. Toute aide serait très appréciée, merci !

Answer 1

Comme mentionné dans les commentaires, je pense que les demi-tours de la rivière dans votre exemple de tableau sont invalides ; voir (cette version de) la règles . Si, comme vous le dites "Nous devons également exclure les possibilités qui deviennent injouables lorsque la rivière s'incurve sur elle-même", le programme Java en bas de page calculera tous les tableaux possibles, avec la réserve qu'il fait la distinction entre les deux lignes droites avec deux bordures d'herbe et entre les deux coudes avec deux bordures d'herbe (nous pourrons les corriger plus tard). Voici un exemple de tableau qu'il génère :

Le total est un énorme 1 715 761 152 tableaux, où j'ai déjà supposé que la source coule toujours vers la droite (sinon, vous obtiendriez juste une version tournée du tableau complet). Mais certaines de ces cartes sont équivalentes selon votre définition :

• On peut toujours remplacer les deux virages par deux bordures de gazon.
• On peut toujours échanger les deux lignes droites avec deux bordures d'herbe.
• On peut toujours faire pivoter la première de ces lignes droites de 180 degrés.
• On peut toujours faire pivoter la deuxième de ces lignes droites de 180 degrés.
• Nous pouvons toujours faire pivoter la ligne droite avec deux frontières de ville de 180 degrés.
• Nous pouvons toujours faire pivoter la droite avec deux bordures de route de 180 degrés.

Cela signifie que nous devons diviser le total par 2. 6 donc il y a 1,715,761,152 / 64 = 26,808,768 soit près de 27 millions de cartes (complètes) différentes selon votre définition.

Le programme Java est le suivant :

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