La plus courte chaîne de sortie du labyrinthe universel

48

Un labyrinthe sur une grille N par N de cellules carrées est défini en spécifiant si chaque bord est un mur ou non. Tous les bords extérieurs sont des murs. Une cellule est définie en tant que début et une cellule en tant que sortie et la sortie est accessible depuis le début. Le début et la sortie ne sont jamais la même cellule.

Notez que ni le début ni la sortie ne doivent se trouver sur la bordure extérieure du labyrinthe. Il s’agit donc d’un labyrinthe valide:

Un labyrinthe 3 par 3 avec la sortie sur la cellule centrale

Une chaîne de caractères 'N', 'E', 'S' et 'W' indique une tentative de déplacement vers le nord, l'est, le sud et l'ouest. Un mouvement bloqué par un mur est ignoré sans mouvement. Une chaîne quitte un labyrinthe si l'application de cette chaîne depuis le début a pour résultat que la sortie est atteinte (que la chaîne continue ou non après avoir atteint la sortie).

Inspiré par cette question énigmatique.SE pour laquelle xnor a fourni une méthode éprouvée de résolution avec une très longue chaîne, écrivez du code capable de trouver une chaîne unique sortant d'un labyrinthe 3 par 3.

Si vous excluez les labyrinthes non valides (démarrage et sortie de la même cellule ou sortie inaccessible au début), il existe 138 172 labyrinthes valides et la chaîne doit quitter chacun d'eux.

Validité

La chaîne doit satisfaire les critères suivants:

  • Il est composé uniquement des caractères "N", "E", "S" et "W".
  • Il quitte tous les labyrinthes auxquels il est appliqué, s'il a été démarré au début.

Étant donné que l'ensemble de tous les labyrinthes possibles inclut chaque labyrinthe possible avec chaque point de départ valide, cela signifie automatiquement que la chaîne quittera tout labyrinthe de tout point de départ valide. C'est-à-dire à partir de n'importe quel point de départ à partir duquel la sortie est accessible.

Gagnant

Le gagnant est la réponse qui fournit la chaîne valide la plus courte et inclut le code utilisé pour la produire. Si plus d'une réponse fournit une chaîne de cette longueur la plus courte, le premier à poster cette longueur de chaîne l'emporte.

Exemple

Voici un exemple de chaîne de 500 caractères, pour vous donner quelque chose à battre:

SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE

Merci à orlp pour ce don.


Classement

Classement

Les scores égaux sont listés dans l'ordre d'affichage de ce score. Ce n'est pas nécessairement l'ordre dans lequel les réponses ont été postées car le score d'une réponse donnée peut être mis à jour au fil du temps.


Juge

Voici un validateur Python 3 qui prend une chaîne de NESW comme argument de ligne de commande ou via STDIN.

Pour une chaîne non valide, cela vous donnera un exemple visuel d'un labyrinthe pour lequel il échoue.

trichoplax
la source
3
C'est une très belle question. Y at-il une chaîne la plus courte (ou un nombre de chaînes et une preuve qu'il ne peut y avoir de réponses plus courtes)? Et si oui, le savez-vous?
Alex Van Liew
1
@AlexReinking Oui, le début peut être n'importe laquelle des 9 cellules et la sortie peut être n'importe laquelle des 9 cellules, tant qu'elles ne sont pas la même cellule et que la sortie est accessible depuis le début.
trichoplax
1
Un peu similaire à cette question stackoverflow: stackoverflow.com/questions/26910401/… - mais les cellules de début et de fin sont en haut à gauche et en bas à droite dans celle-ci, ce qui réduit le nombre possible de labyrinthe à 2423.
schnaader
1
@proudhaskeller de toute façon serait une question valable. Le cas général, noté n = 3, nécessiterait un code plus généralisé. Ce cas spécifique permet des optimisations qui ne s’appliquent pas au général n, c’est ce que j’ai choisi de lui demander.
Trichoplax
2
Quelqu'un a-t-il envisagé de résoudre ce problème en recherchant la chaîne acceptée la plus courte en expression régulière? Cela nécessiterait BEAUCOUP de réduction du nombre de problèmes avant de convertir en regex, mais pourrait théoriquement trouver une solution vérifiable optimale.
Kyle McCormick

Réponses:

37

C ++, 97 95 93 91 86 83 82 81 79 caractères

NNWSWNNSENESESWSSWNSEENWWWWWENWENENWEENWWWENENWWENNESENESESWNWENENWNEEN

Ma stratégie est assez simple: un algorithme d'évolution capable de croître, de réduire, d'échanger des éléments et de muter des séquences valides. Ma logique d'évolution est maintenant presque identique à celle de @ Sp3000, car c'était une amélioration par rapport à la mienne.

Cependant, mon implémentation de la logique du labyrinthe est plutôt astucieuse. Cela me permet de vérifier si les chaînes sont valides à une vitesse fulgurante. Essayez de comprendre en regardant le commentaire do_moveet le Mazeconstructeur.

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <vector>

/*
    Positions:

        8, 10, 12
        16, 18, 20
        24, 26, 28

    By defining as enum respectively N, W, E, S as 0, 1, 2, 3 we get:

        N: -8, E: 2, S: 8, W: -2
        0: -8, 1: -2, 2: 2, 3: 8

    To get the indices for the walls, average the numbers of the positions it
    would be blocking. This gives the following indices:

        9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27

    We'll construct a wall mask with a 1 bit for every position that does not
    have a wall. Then if a 1 shifted by the average of the positions AND'd with
    the wall mask is zero, we have hit a wall.
*/

enum { N = -8, W = -2, E = 2, S = 8 };
static const int encoded_pos[] = {8, 10, 12, 16, 18, 20, 24, 26, 28};
static const int wall_idx[] = {9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27};
static const int move_offsets[] = { N, W, E, S };

int do_move(uint32_t walls, int pos, int move) {
    int idx = pos + move / 2;
    return walls & (1ull << idx) ? pos + move : pos;
}

struct Maze {
    uint32_t walls;
    int start, end;

    Maze(uint32_t maze_id, int start, int end) {
        walls = 0;
        for (int i = 0; i < 12; ++i) {
            if (maze_id & (1 << i)) walls |= 1 << wall_idx[i];
        }
        this->start = encoded_pos[start];
        this->end = encoded_pos[end];
    }

    uint32_t reachable() {
        if (start == end) return false;

        uint32_t reached = 0;
        std::vector<int> fill; fill.reserve(8); fill.push_back(start);
        while (fill.size()) {
            int pos = fill.back(); fill.pop_back();
            if (reached & (1 << pos)) continue;
            reached |= 1 << pos;
            for (int m : move_offsets) fill.push_back(do_move(walls, pos, m));
        }

        return reached;
    }

    bool interesting() {
        uint32_t reached = reachable();
        if (!(reached & (1 << end))) return false;
        if (std::bitset<32>(reached).count() <= 4) return false;

        int max_deg = 0;
        uint32_t ends = 0;
        for (int p = 0; p < 9; ++p) {
            int pos = encoded_pos[p];
            if (reached & (1 << pos)) {
                int deg = 0;
                for (int m : move_offsets) {
                    if (pos != do_move(walls, pos, m)) ++deg;
                }
                if (deg == 1) ends |= 1 << pos;
                max_deg = std::max(deg, max_deg);
            }
        }

        if (max_deg <= 2 && ends != ((1u << start) | (1u << end))) return false;

        return true;
    }
};

std::vector<Maze> gen_valid_mazes() {
    std::vector<Maze> mazes;
    for (int maze_id = 0; maze_id < (1 << 12); maze_id++) {
        for (int points = 0; points < 9*9; ++points) {
            Maze maze(maze_id, points % 9, points / 9);
            if (!maze.interesting()) continue;
            mazes.push_back(maze);
        }
    }

    return mazes;
}

bool is_solution(const std::vector<int>& moves, Maze maze) {
    int pos = maze.start;
    for (auto move : moves) {
        pos = do_move(maze.walls, pos, move);
        if (pos == maze.end) return true;
    }

    return false;
}

std::vector<int> str_to_moves(std::string str) {
    std::vector<int> moves;
    for (auto c : str) {
        switch (c) {
        case 'N': moves.push_back(N); break;
        case 'E': moves.push_back(E); break;
        case 'S': moves.push_back(S); break;
        case 'W': moves.push_back(W); break;
        }
    }

    return moves;
}

std::string moves_to_str(const std::vector<int>& moves) {
    std::string result;
    for (auto move : moves) {
             if (move == N) result += "N";
        else if (move == E) result += "E";
        else if (move == S) result += "S";
        else if (move == W) result += "W";
    }
    return result;
}

bool solves_all(const std::vector<int>& moves, std::vector<Maze>& mazes) {
    for (size_t i = 0; i < mazes.size(); ++i) {
        if (!is_solution(moves, mazes[i])) {
            // Bring failing maze closer to begin.
            std::swap(mazes[i], mazes[i / 2]);
            return false;
        }
    }
    return true;
}

template<class Gen>
int randint(int lo, int hi, Gen& gen) {
    return std::uniform_int_distribution<int>(lo, hi)(gen);
}

template<class Gen>
int randmove(Gen& gen) { return move_offsets[randint(0, 3, gen)]; }

constexpr double mutation_p = 0.35; // Chance to mutate.
constexpr double grow_p = 0.1; // Chance to grow.
constexpr double swap_p = 0.2; // Chance to swap.

int main(int argc, char** argv) {
    std::random_device rnd;
    std::mt19937 rng(rnd());
    std::uniform_real_distribution<double> real;
    std::exponential_distribution<double> exp_big(0.5);
    std::exponential_distribution<double> exp_small(2);

    std::vector<Maze> mazes = gen_valid_mazes();

    std::vector<int> moves;
    while (!solves_all(moves, mazes)) {
        moves.clear();
        for (int m = 0; m < 500; m++) moves.push_back(randmove(rng));
    }

    size_t best_seen = moves.size();
    std::set<std::vector<int>> printed;
    while (true) {
        std::vector<int> new_moves(moves);
        double p = real(rng);

        if (p < grow_p && moves.size() < best_seen + 10) {
            int idx = randint(0, new_moves.size() - 1, rng);
            new_moves.insert(new_moves.begin() + idx, randmove(rng));
        } else if (p < swap_p) {
            int num_swap = std::min<int>(1 + exp_big(rng), new_moves.size()/2);
            for (int i = 0; i < num_swap; ++i) {
                int a = randint(0, new_moves.size() - 1, rng);
                int b = randint(0, new_moves.size() - 1, rng);
                std::swap(new_moves[a], new_moves[b]);
            }
        } else if (p < mutation_p) {
            int num_mut = std::min<int>(1 + exp_big(rng), new_moves.size());
            for (int i = 0; i < num_mut; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves[idx] = randmove(rng);
            }
        } else {
            int num_shrink = std::min<int>(1 + exp_small(rng), new_moves.size());
            for (int i = 0; i < num_shrink; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves.erase(new_moves.begin() + idx);
            }
        }

        if (solves_all(new_moves, mazes)) {
            moves = new_moves;

            if (moves.size() <= best_seen && !printed.count(moves)) {
                std::cout << moves.size() << " " << moves_to_str(moves) << "\n";
                if (moves.size() < best_seen) {
                    printed.clear(); best_seen = moves.size();
                }
                printed.insert(moves);
            }
        }
    }

    return 0;
}
orlp
la source
5
Confirmé valide. Je suis impressionné - je ne m'attendais pas à voir des chaînes aussi courtes.
trichoplax
2
J'ai finalement réussi à installer gcc et à l'exécuter moi-même. C'est hypnotique de regarder les cordes muter et se rétrécir lentement ...
trichoplax
1
@trichoplax Je vous ai dit que c'était amusant :)
orlp
2
@AlexReinking J'ai mis à jour ma réponse avec ladite implémentation. Si vous regardez le démontage, vous verrez qu'il ne s'agit que d'une douzaine d'instructions sans branche ni charge: coliru.stacked-crooked.com/a/3b09d36db85ce793 .
Orlp
2
@ AlexReinking Fait. do_moveest maintenant incroyablement rapide.
Orlp
16

Python 3 + PyPy, 82 à 80 caractères

SWWNNSENESESWSSWSEENWNWSWSEWNWNENENWWSESSEWSWNWSENWEENWWNNESENESSWNWSESESWWNNESE

J’ai hésité à poster cette réponse car j’ai en gros adopté l’approche d’orlp et j’ai fait mes propres commentaires. Cette chaîne a été trouvée en commençant par une solution de longueur pseudo-aléatoire 500 - un grand nombre de graines ont été essayées avant que je puisse battre le record actuel.

La seule nouvelle optimisation majeure est que je ne regarde qu'un tiers des labyrinthes. Deux catégories de labyrinthes sont exclues de la recherche:

  • Labyrinthes où les <= 7places sont accessibles
  • Des labyrinthes où toutes les cases accessibles sont sur un seul chemin et où le début / la fin ne se fait pas aux deux extrémités

L'idée est que toute corde qui résout le reste des labyrinthes devrait également résoudre ce qui précède automatiquement. Je suis convaincu que cela est vrai pour le second type, mais ce n'est certainement pas le cas pour le premier. Le résultat contiendra donc des faux positifs qui doivent être vérifiés séparément. Ces faux positifs manquent généralement environ 20 labyrinthes, alors j'ai pensé que ce serait un bon compromis entre vitesse et précision, et que cela donnerait également aux cordes un peu plus de temps pour respirer.

Au départ, j'ai passé en revue une longue liste d'heuristiques de recherche, mais, horriblement, aucune d'entre elles n'a proposé quelque chose de meilleur que 140 ou plus.

import random

N, M = 3, 3

W = 2*N-1
H = 2*M-1

random.seed(142857)


def move(c, cell, walls):
    global W, H

    if c == "N":
        if cell > W and not (1<<(cell-W)//2 & walls):
            cell = cell - W*2

    elif c == "S":
        if cell < W*(H-1) and not (1<<(cell+W)//2 & walls):
            cell = cell + W*2

    elif c == "E":
        if cell % W < W-1 and not (1<<(cell+1)//2 & walls):
            cell = cell + 2

    elif c == "W":
        if cell % W > 0 and not (1<<(cell-1)//2 & walls):
            cell = cell - 2

    return cell


def valid_maze(start, finish, walls):
    global adjacent

    if start == finish:
        return False

    visited = set()
    cells = [start]

    while cells:
        curr_cell = cells.pop()

        if curr_cell == finish:
            return True

        if curr_cell in visited:
            continue

        visited.add(curr_cell)

        for c in "NSEW":
            cells.append(move(c, curr_cell, walls))

    return False


def print_maze(maze):
    start, finish, walls = maze
    print_str = "".join(" #"[walls & (1 << i//2) != 0] if i%2 == 1
                        else " SF"[2*(i==finish) + (i==start)]
                        for i in range(W*H))

    print("#"*(H+2))

    for i in range(H):
        print("#" + print_str[i*W:(i+1)*W] + "#")

    print("#"*(H+2), end="\n\n")

all_cells = [W*y+x for y in range(0, H, 2) for x in range(0, W, 2)]
mazes = []

for start in all_cells:
    for finish in all_cells:
        for walls in range(1<<(N*(M-1) + M*(N-1))):
            if valid_maze(start, finish, walls):
                mazes.append((start, finish, walls))

num_mazes = len(mazes)
print(num_mazes, "mazes generated")

to_remove = set()

for i, maze in enumerate(mazes):
    start, finish, walls = maze

    reachable = set()
    cells = [start]

    while cells:
        cell = cells.pop()

        if cell in reachable:
            continue

        reachable.add(cell)

        if cell == finish:
            continue

        for c in "NSEW":
            new_cell = move(c, cell, walls)
            cells.append(new_cell)

    max_deg = 0
    sf = set()

    for cell in reachable:
        deg = 0

        for c in "NSEW":
            if move(c, cell, walls) != cell:
                deg += 1

        max_deg = max(deg, max_deg)

        if deg == 1:
            sf.add(cell)

    if max_deg <= 2 and len(sf) == 2 and sf != {start, finish}:
        # Single path subset
        to_remove.add(i)

    elif len(reachable) <= (N*M*4)//5:
        # Low reachability maze, above ratio is adjustable
        to_remove.add(i)

mazes = [maze for i,maze in enumerate(mazes) if i not in to_remove]
print(num_mazes - len(mazes), "mazes removed,", len(mazes), "remaining")
num_mazes = len(mazes)


def check(string, cache = set()):
    global mazes

    if string in cache:
        return True

    for i, maze in enumerate(mazes):
        start, finish, walls = maze
        cell = start

        for c in string:
            cell = move(c, cell, walls)

            if cell == finish:
                break

        else:
            # Swap maze to front
            mazes[i//2], mazes[i] = mazes[i], mazes[i//2]
            return False

    cache.add(string)
    return True


while True:
    string = "".join(random.choice("NSEW") for _ in range(500))

    if check(string):
        break

# string = "NWWSSESNESESNNWNNSWNWSSENESWSWNENENWNWESESENNESWSESWNWSWNNEWSESWSEEWNENWWSSNNEESS"

best = len(string)
seen = set()

while True:
    action = random.random()

    if action < 0.1:
        # Grow
        num_grow = int(random.expovariate(lambd=3)) + 1
        new_string = string

        for _ in range(num_grow):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + random.choice("NSEW") + new_string[i:]

    elif action < 0.2:
        # Swap
        num_swap = int(random.expovariate(lambd=1)) + 1
        new_string = string

        for _ in range(num_swap):
            i,j = sorted(random.sample(range(len(new_string)), 2))
            new_string = new_string[:i] + new_string[j] + new_string[i+1:j] + new_string[i] + new_string[j+1:]

    elif action < 0.35:
        # Mutate
        num_mutate = int(random.expovariate(lambd=1)) + 1
        new_string = string

        for _ in range(num_mutate):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + random.choice("NSEW") + new_string[i+1:]

    else:
        # Shrink
        num_shrink = int(random.expovariate(lambd=3)) + 1
        new_string = string

        for _ in range(num_shrink):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + new_string[i+1:]


    if check(new_string):
        string = new_string

    if len(string) <= best and string not in seen:
        while True:
            if len(string) < best:
                seen = set()

            seen.add(string)
            best = len(string)
            print(string, len(string))

            # Force removals on new record strings
            for i in range(len(string)):
                new_string = string[:i] + string[i+1:]

                if check(new_string):
                    string = new_string
                    break

            else:
                break
Sp3000
la source
Confirmé valide.
Belles
J'aime votre idée de réaliser que certains labyrinthes n'ont pas besoin d'être vérifiés. Pourriez-vous en quelque sorte automatiser le processus de détermination des labyrinthes qui sont des contrôles redondants? Je suis curieux de savoir si cela ferait apparaître plus de labyrinthes que ceux que l'on peut déduire intuitivement ...
trichoplax
Quel est votre raisonnement pour ne pas avoir besoin de vérifier les graphes de chemins où le début n'est pas à une extrémité? Le cas où la finition n'est pas à une extrémité est facile à justifier et peut être renforcé pour ne pas avoir à vérifier les cas où la finition est un sommet coupé, mais je ne vois pas comment justifier l'élimination des sommets de départ.
Peter Taylor
@PeterTaylor Après réflexion, en théorie, vous avez raison, il y a des labyrinthes que vous ne pouvez pas éliminer comme ça. Cependant, il semble que sur 3x3, peu importe la longueur des chaînes.
orlp
2
@orlp, Sp3000 a esquissé une preuve en discussion. Les graphes de chemin sont un cas particulier. Renumérotez les cellules 0le nlong du chemin et supposez que cette chaîne Svous mène de 0à n. Ensuite, Svous obtenez également de n'importe quelle cellule intermédiaire cà n. Supposons le contraire. Soit a(i)la position après les iétapes commençant à 0et b(i)commençant à c. Ensuite a(0) = 0 < b(0), chaque étape change aet bd’au plus 1, et a(|S|) = n > b(|S|). Prenez le plus petit ttel que a(t) >= b(t). Clairement a(t) != b(t)ou ils seraient synchronisés, ils doivent donc changer de place à pas ten se déplaçant dans la même direction.
Peter Taylor
3

C ++ et la bibliothèque de Lingeling

Résumé: Une nouvelle approche, pas de nouvelles solutions , un programme agréable à jouer et quelques résultats intéressants de la non-amélioration locale des solutions connues. Oh, et quelques observations généralement utiles.

En utilisant une approche SAT , je pourrais résoudre complètement le problème similaire des labyrinthes 4x4 avec des cellules bloquées au lieu de parois minces et de positions de départ et de sortie fixes aux angles opposés. J'espérais donc pouvoir utiliser les mêmes idées pour résoudre ce problème. Cependant, même si pour l'autre problème, je n'ai utilisé que 2423 labyrinthes (entre-temps, 2083 suffisent) et qu'il a une solution de longueur 29, le codage SAT a utilisé des millions de variables et sa résolution a pris des jours.

J'ai donc décidé de modifier l'approche de deux manières importantes:

  • N'insistez pas pour chercher une solution à partir de zéro, mais permettez de réparer une partie de la chaîne de la solution. (C'est quand même facile à faire en ajoutant des clauses d'unités, mais mon programme me permet de le faire facilement.)
  • N'utilisez pas tous les labyrinthes depuis le début. Au lieu de cela, ajoutez progressivement un labyrinthe non résolu à la fois. Certains labyrinthes peuvent être résolus par hasard, ou ils sont toujours résolus lorsque ceux déjà pris en compte sont résolus. Dans ce dernier cas, il ne sera jamais ajouté, sans que nous ayons besoin de connaître l’implication.

J'ai également fait quelques optimisations pour utiliser moins de variables et de clauses unitaires.

Le programme est basé sur @ orlp. Un choix important a été le choix des labyrinthes:

  • Tout d'abord, les labyrinthes sont donnés par leur structure murale et leur position de départ uniquement. (Ils stockent également les positions accessibles.) La fonction is_solutionvérifie si toutes les positions accessibles sont atteintes.
  • (Inchangé: n'utilise toujours pas de labyrinthes avec seulement 4 positions ou moins. Mais la plupart d'entre elles seraient de toute façon rejetées par les observations suivantes.)
  • Si un labyrinthe n'utilise aucune des trois cellules du haut, cela équivaut à un labyrinthe décalé. Alors on peut le laisser tomber. De même pour un labyrinthe qui n'utilise aucune des trois cellules de gauche.
  • Peu importe que les parties inaccessibles soient connectées, nous insistons donc pour que chaque cellule inaccessible soit complètement entourée de murs.
  • Un labyrinthe à un seul chemin, qui est un sous-sol d'un plus grand labyrinthe à un seul chemin, est toujours résolu lorsque le plus grand est résolu, nous n'en avons donc pas besoin. Chaque labyrinthe avec un chemin de taille maximale de 7 fait partie d’un grand labyrinthe (qui convient toujours au format 3x3), mais il existe des labyrinthes de taille 8 qui ne le sont pas. Simplement, supprimons les labyrinthes à un seul chemin dont la taille est inférieure à 8. (J'utilise toujours le principe selon lequel seuls les points extrêmes doivent être considérés comme des positions de départ. Toutes les positions sont utilisées comme positions de sortie, ce qui compte uniquement pour la partie SAT. du programme.)

De cette façon, je reçois un total de 10772 labyrinthes avec des positions de départ.

Voici le programme:

#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
#include <limits>
#include <cassert>

extern "C"{
#include "lglib.h"
}

// reusing a lot of @orlp's ideas and code

enum { N = -8, W = -2, E = 2, S = 8 };
static const int encoded_pos[] = {8, 10, 12, 16, 18, 20, 24, 26, 28};
static const int wall_idx[] = {9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27};
static const int move_offsets[] = { N, E, S, W };
static const uint32_t toppos = 1ull << 8 | 1ull << 10 | 1ull << 12;
static const uint32_t leftpos = 1ull << 8 | 1ull << 16 | 1ull << 24;
static const int unencoded_pos[] = {0,0,0,0,0,0,0,0,0,0,1,0,2,0,0,0,3,
                                    0,4,0,5,0,0,0,6,0,7,0,8};

int do_move(uint32_t walls, int pos, int move) {
  int idx = pos + move / 2;
  return walls & (1ull << idx) ? pos + move : pos;
}

struct Maze {
  uint32_t walls, reach;
  int start;

  Maze(uint32_t walls=0, uint32_t reach=0, int start=0):
    walls(walls),reach(reach),start(start) {}

  bool is_dummy() const {
    return (walls==0);
  }

  std::size_t size() const{
    return std::bitset<32>(reach).count();
  }

  std::size_t simplicity() const{  // how many potential walls aren't there?
    return std::bitset<32>(walls).count();
  }

};

bool cmp(const Maze& a, const Maze& b){
  auto asz = a.size();
  auto bsz = b.size();
  if (asz>bsz) return true;
  if (asz<bsz) return false;
  return a.simplicity()<b.simplicity();
}

uint32_t reachable(uint32_t walls) {
  static int fill[9];
  uint32_t reached = 0;
  uint32_t reached_relevant = 0;
  for (int start : encoded_pos){
    if ((1ull << start) & reached) continue;
    uint32_t reached_component = (1ull << start);
    fill[0]=start;
    int count=1;
    for(int i=0; i<count; ++i)
      for(int m : move_offsets) {
        int newpos = do_move(walls, fill[i], m);
        if (reached_component & (1ull << newpos)) continue;
        reached_component |= 1ull << newpos;
        fill[count++] = newpos;
      }
    if (count>1){
      if (reached_relevant)
        return 0;  // more than one nonsingular component
      if (!(reached_component & toppos) || !(reached_component & leftpos))
        return 0;  // equivalent to shifted version
      if (std::bitset<32>(reached_component).count() <= 4)
        return 0;  
      reached_relevant = reached_component;
    }
    reached |= reached_component;
  }
  return reached_relevant;
}

void enterMazes(uint32_t walls, uint32_t reached, std::vector<Maze>& mazes){
  int max_deg = 0;
  uint32_t ends = 0;
  for (int pos : encoded_pos)
    if (reached & (1ull << pos)) {
      int deg = 0;
      for (int m : move_offsets) {
        if (pos != do_move(walls, pos, m))
          ++deg;
      }
      if (deg == 1)
        ends |= 1ull << pos;
      max_deg = std::max(deg, max_deg);
    }
  uint32_t starts = reached;
  if (max_deg == 2){
    if (std::bitset<32>(reached).count() <= 7)
      return; // small paths are redundant
    starts = ends; // need only start at extremal points
  }
  for (int pos : encoded_pos)
    if ( starts & (1ull << pos))
      mazes.emplace_back(walls, reached, pos);
}

std::vector<Maze> gen_valid_mazes() {
  std::vector<Maze> mazes;
  for (int maze_id = 0; maze_id < (1 << 12); maze_id++) {
    uint32_t walls = 0;
    for (int i = 0; i < 12; ++i) 
      if (maze_id & (1 << i))
    walls |= 1ull << wall_idx[i];
    uint32_t reached=reachable(walls);
    if (!reached) continue;
    enterMazes(walls, reached, mazes);
  }
  std::sort(mazes.begin(),mazes.end(),cmp);
  return mazes;
};

bool is_solution(const std::vector<int>& moves, Maze& maze) {
  int pos = maze.start;
  uint32_t reached = 1ull << pos;
  for (auto move : moves) {
    pos = do_move(maze.walls, pos, move);
    reached |= 1ull << pos;
    if (reached == maze.reach) return true;
  }
  return false;
}

std::vector<int> str_to_moves(std::string str) {
  std::vector<int> moves;
  for (auto c : str) {
    switch (c) {
    case 'N': moves.push_back(N); break;
    case 'E': moves.push_back(E); break;
    case 'S': moves.push_back(S); break;
    case 'W': moves.push_back(W); break;
    }
  }
  return moves;
}

Maze unsolved(const std::vector<int>& moves, std::vector<Maze>& mazes) {
  int unsolved_count = 0;
  Maze problem{};
  for (Maze m : mazes)
    if (!is_solution(moves, m))
      if(!(unsolved_count++))
    problem=m;
  if (unsolved_count)
    std::cout << "unsolved: " << unsolved_count << "\n";
  return problem;
}

LGL * lgl;

constexpr int TRUELIT = std::numeric_limits<int>::max();
constexpr int FALSELIT = -TRUELIT;

int new_var(){
  static int next_var = 1;
  assert(next_var<TRUELIT);
  return next_var++;
}

bool lit_is_true(int lit){
  int abslit = lit>0 ? lit : -lit;
  bool res = (abslit==TRUELIT) || (lglderef(lgl,abslit)>0);
  return lit>0 ? res : !res;
}

void unsat(){
  std::cout << "Unsatisfiable!\n";
  std::exit(1);
}

void clause(const std::set<int>& lits){
  if (lits.find(TRUELIT) != lits.end())
    return;
  for (int lit : lits)
    if (lits.find(-lit) != lits.end())
      return;
  int found=0;
  for (int lit : lits)
    if (lit != FALSELIT){
      lgladd(lgl, lit);
      found=1;
    }
  lgladd(lgl, 0);
  if (!found)
    unsat();
}

void at_most_one(const std::set<int>& lits){
  if (lits.size()<2)
    return;
  for(auto it1=lits.cbegin(); it1!=lits.cend(); ++it1){
    auto it2=it1;
    ++it2;
    for(  ; it2!=lits.cend(); ++it2)
      clause( {- *it1, - *it2} );
  }
}

/* Usually, lit_op(lits,sgn) creates a new variable which it returns,
   and adds clauses that ensure that the variable is equivalent to the
   disjunction (if sgn==1) or the conjunction (if sgn==-1) of the literals
   in lits. However, if this disjunction or conjunction is constant True
   or False or simplifies to a single literal, that is returned without
   creating a new variable and without adding clauses.                    */ 

int lit_op(std::set<int> lits, int sgn){
  if (lits.find(sgn*TRUELIT) != lits.end())
    return sgn*TRUELIT;
  lits.erase(sgn*FALSELIT);
  if (!lits.size())
    return sgn*FALSELIT;
  if (lits.size()==1)
    return *lits.begin();
  int res=new_var();
  for(int lit : lits)
    clause({sgn*res,-sgn*lit});
  for(int lit : lits)
    lgladd(lgl,sgn*lit);
  lgladd(lgl,-sgn*res);
  lgladd(lgl,0);
  return res;
}

int lit_or(std::set<int> lits){
  return lit_op(lits,1);
}

int lit_and(std::set<int> lits){
  return lit_op(lits,-1);
}

using A4 = std::array<int,4>;

void add_maze_conditions(Maze m, std::vector<A4> dirs, int len){
  int mp[9][2];
  int rp[9];
  for(int p=0; p<9; ++p)
    if((1ull << encoded_pos[p]) & m.reach)
      rp[p] = mp[p][0] = encoded_pos[p]==m.start ? TRUELIT : FALSELIT;
  int t=0;
  for(int i=0; i<len; ++i){
    std::set<int> posn {};
    for(int p=0; p<9; ++p){
      int ep = encoded_pos[p];
      if((1ull << ep) & m.reach){
        std::set<int> reach_pos {};
        for(int d=0; d<4; ++d){
          int np = do_move(m.walls, ep, move_offsets[d]);
          reach_pos.insert( lit_and({mp[unencoded_pos[np]][t],
                                  dirs[i][d ^ ((np==ep)?0:2)]    }));
        }
        int pl = lit_or(reach_pos);
        mp[p][!t] = pl;
        rp[p] = lit_or({rp[p], pl});
        posn.insert(pl);
      }
    }
    at_most_one(posn);
    t=!t;
  }
  for(int p=0; p<9; ++p)
    if((1ull << encoded_pos[p]) & m.reach)
      clause({rp[p]});
}

void usage(char* argv0){
  std::cout << "usage: " << argv0 <<
    " <string>\n   where <string> consists of 'N', 'E', 'S', 'W' and '*'.\n" ;
  std::exit(2);
}

const std::string nesw{"NESW"};

int main(int argc, char** argv) {
  if (argc!=2)
    usage(argv[0]);
  std::vector<Maze> mazes = gen_valid_mazes();
  std::cout << "Mazes with start positions: " << mazes.size() << "\n" ;
  lgl = lglinit();
  int len = std::strlen(argv[1]);
  std::cout << argv[1] << "\n   with length " << len << "\n";

  std::vector<A4> dirs;
  for(int i=0; i<len; ++i){
    switch(argv[1][i]){
    case 'N':
      dirs.emplace_back(A4{TRUELIT,FALSELIT,FALSELIT,FALSELIT});
      break;
    case 'E':
      dirs.emplace_back(A4{FALSELIT,TRUELIT,FALSELIT,FALSELIT});
      break;
    case 'S':
      dirs.emplace_back(A4{FALSELIT,FALSELIT,TRUELIT,FALSELIT});
      break;
    case 'W':
      dirs.emplace_back(A4{FALSELIT,FALSELIT,FALSELIT,TRUELIT});
      break;
    case '*': {
      dirs.emplace_back();
      std::generate_n(dirs[i].begin(),4,new_var);
      std::set<int> dirs_here { dirs[i].begin(), dirs[i].end() };
      at_most_one(dirs_here);
      clause(dirs_here);
      for(int l : dirs_here)
        lglfreeze(lgl,l);
      break;
      }
    default:
      usage(argv[0]);
    }
  }

  int maze_nr=0;
  for(;;) {
    std::cout << "Solving...\n";
    int res=lglsat(lgl);
    if(res==LGL_UNSATISFIABLE)
      unsat();
    assert(res==LGL_SATISFIABLE);
    std::string sol(len,' ');
    for(int i=0; i<len; ++i)
      for(int d=0; d<4; ++d)
        if (lit_is_true(dirs[i][d])){
          sol[i]=nesw[d];
          break;
    }
    std::cout << sol << "\n";

    Maze m=unsolved(str_to_moves(sol),mazes);
    if (m.is_dummy()){
      std::cout << "That solves all!\n";
      return 0;
    }
    std::cout << "Adding maze " << ++maze_nr << ": " << 
      m.walls << "/" << m.start <<
      " (" << m.size() << "/" << 12-m.simplicity() << ")\n";
    add_maze_conditions(m,dirs,len);
  }
}  

Tout d’abord, configure.shpuis makele lingelingrésolveur, compilez le programme avec quelque chose comme g++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl, où ...est le chemin où lglib.hresp. liblgl.asont, de sorte que les deux pourraient par exemple être ../lingeling-<version>. Ou tout simplement les mettre dans le même répertoire et se passer des options -Iet -L.

Le programme prend un argument de ligne de commande obligatoire, une chaîne constituée de N, E, S, W(pour les directions fixes) ou *. Vous pouvez donc rechercher une solution générale de taille 78 en donnant une chaîne de 78 *s (entre guillemets), ou rechercher une solution en commençant par NEWSen utilisant NEWSsuivi de autant de *s que vous le souhaitez pour des étapes supplémentaires. Comme premier test, prenez votre solution préférée et remplacez certaines des lettres par *. Cela trouve une solution rapide pour une valeur étonnamment élevée de "certains".

Le programme indiquera le labyrinthe ajouté, décrit par la structure du mur et la position de départ, ainsi que le nombre de positions et de murs accessibles. Les labyrinthes sont triés selon ces critères et le premier non résolu est ajouté. Par conséquent, la plupart des labyrinthes ajoutés ont (9/4), mais parfois d'autres apparaissent également.

J'ai pris la solution connue de longueur 79 et, pour chaque groupe de 26 lettres adjacentes, j'ai essayé de les remplacer par 25 lettres. J'ai également essayé de supprimer 13 lettres du début et de la fin et de les remplacer par 13 au début et 12 à la fin, et inversement. Malheureusement, tout est sorti insatisfiable. Alors, pouvons-nous prendre cela comme indicateur que la longueur 79 est optimale? Non, j'ai également essayé d'améliorer la solution de longueur 80 à longueur 79, et cela n'a pas non plus abouti.

Enfin, j'ai essayé de combiner le début d'une solution avec la fin de l'autre et également avec une solution transformée par l'une des symétries. Maintenant que je manque d’idées intéressantes, j’ai décidé de vous montrer ce que j’avais, même si cela n’a pas débouché sur de nouvelles solutions.

Christian Sievers
la source
C'était une lecture vraiment intéressante. La nouvelle approche et les différentes façons de réduire le nombre de labyrinthes à vérifier. Pour être une réponse valide, vous devez inclure une chaîne valide. Il n'est pas nécessaire que ce soit la nouvelle chaîne la plus courte, mais simplement une chaîne valide de longueur quelconque pour donner le score actuel de cette approche. Je le mentionne car sans score, la réponse risquerait d'être supprimée et j'aimerais vraiment qu'elle reste en place.
Trichoplax
Nous avons également fait du bon travail pour trouver la solution de longueur optimale pour le défi le plus ancien !
Trichoplax