Skip to content

La chaîne de sortie du labyrinthe universel la plus courte

Nos programmeurs vedettes ont épuisé leurs réserves de café, dans leur recherche quotidienne de la résolution, jusqu'à ce qu'Andrea trouve la solution à Gitea, alors en ce moment nous la partageons avec vous.

Solution :

C++, 9795939186838281 79 caractères

NNWSWNNSENESESWSSWNSEENWWNWSSEWWNENWEENWSWNWSSENWNESENESESWNWSESEWWNENWNEES

Ma stratégie est assez simple - un algorithme d'évolution qui peut croître, rétrécir, échanger des éléments de séquences valides et les faire muter. Ma logique d'évolution est maintenant presque la même que celle de @Sp3000, car la sienne était une amélioration de 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 le comprendre en regardant le commentaire, do_move et le Maze constructeur.

#include 
#include 
#include 
#include 
#include 
#include 
#include 

/*
    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 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[randint(0, 3, gen)](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 gen_valid_mazes() {
    std::vector 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& 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 str_to_moves(std::string str) {
    std::vector 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& 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& moves, std::vector& 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
int randint(int lo, int hi, Gen& gen) {
    return std::uniform_int_distribution(lo, hi)(gen);
}

template
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 real;
    std::exponential_distribution exp_big(0.5);
    std::exponential_distribution exp_small(2);

    std::vector mazes = gen_valid_mazes();

    std::vector 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> printed;
    while (true) {
        std::vector 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(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(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(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;
}

Python 3 + PyPy, 82 80 caractères

SWWNNSENESESWSSWSEENWNWSWSEWNWNENENWWSESSEWSWNWSENWEENWWNNESENESSWNWSESESWWNNESE

J'ai hésité à poster cette réponse parce que j'ai essentiellement pris l'approche d'orlp et mis mon propre spin sur elle. Cette chaîne a été trouvée en commençant par une solution pseudo-aléatoire de longueur 500 - un assez 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 :

  • Les labyrinthes où <= 7 carrés sont atteignables
  • Labyrinthes où tous les carrés atteignables sont sur un seul chemin, et où le départ et l'arrivée ne sont pas aux deux extrémités.

L'idée est que toute chaîne qui résout le reste des labyrinthes devrait aussi résoudre automatiquement les labyrinthes ci-dessus. Je suis convaincu que c'est vrai pour le deuxième type, mais ce n'est certainement pas vrai pour le premier, donc la sortie contiendra quelques faux positifs qui doivent être vérifiés séparément. Ces faux positifs ne manquent généralement qu'environ 20 labyrinthes cependant, donc j'ai pensé que ce serait un bon compromis entre la vitesse et la précision, et cela donnerait également aux cordes un peu plus d'espace de respiration pour muter.

Initialement, j'ai parcouru une longue liste d'heuristiques de recherche, mais horriblement, aucune d'entre elles n'a abouti à quelque chose de mieux que 140 environ.

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="nn")

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

C++ et la bibliothèque de lingeling

Résumé : une nouvelle approche, pas de nouvelles solutions, un programme sympa pour jouer
avec, et quelques résultats intéressants de non-improvabilité locale des
solutions connues. Oh, et quelques observations généralement utiles.

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

J'ai donc décidé de changer l'approche de deux façons importantes :

  • Ne pas insister sur la recherche d'une solution à partir de zéro, mais permettre de fixer
    une partie de la chaîne de solution. (C'est facile à faire de toute façon en ajoutant des clauses unitaires.
    clauses, mais mon programme le rend confortable à faire).
  • N'utilisez pas tous les labyrinthes dès 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à considérés sont résolus. Dans ce dernier cas
    cas, il ne sera jamais ajouté, sans que nous ayons besoin d'en connaître l'implication.

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

Le programme est basé sur celui de @orlp.
Un changement important a été la sélection des labyrinthes :

  • Tout d'abord, les labyrinthes sont donnés par la structure de leurs murs et la
    position de départ uniquement. (Ils stockent également les positions atteignables).
    La fonction is_solution vérifie si toutes les positions atteignables sont atteintes.
  • (Inchangé : toujours pas d'utilisation des labyrinthes avec seulement 4 positions atteignables ou moins.
    Mais la plupart d'entre eux seraient de toute façon jetés par les observations suivantes).
  • Si un labyrinthe n'utilise aucune des trois cellules supérieures, il est équivalent à un
    labyrinthe qui est décalé vers le haut. On peut donc le laisser tomber. De même pour un labyrinthe qui n'utilise
    n'utilise aucune des trois cellules de gauche.
  • Il n'est pas important que les parties inaccessibles soient connectées, donc nous insistons pour que
    chaque cellule inaccessible soit complètement entourée de murs.
  • Un labyrinthe à chemin unique qui est un sous labyrinthe d'un plus grand labyrinthe à chemin unique est toujours
    résolu quand le plus grand est résolu, donc nous n'en avons pas besoin. Chaque labyrinthe à chemin unique
    de taille 7 au maximum fait partie d'un plus grand (qui tient toujours dans 3x3), mais il y a des labyrinthes à chemin unique de taille 8.
    il existe des labyrinthes à chemin unique de taille 8 qui n'en font pas partie. Pour simplifier, nous allons simplement
    les labyrinthes à chemin unique de taille inférieure à 8.
    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 n'a d'importance que pour la partie SAT du programme).
    du programme).

De cette façon, j'obtiens un total de 10772 labyrinthes avec des positions de départ.

Voici le programme :

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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[randint(0, 3, gen)](reach).count();
  }

  std::size_t simplicity() const{  // how many potential walls aren't there?
    return std::bitset[randint(0, 3, gen)](walls).count();
  }

};

bool cmp(const Maze& a, const Maze& b){
  auto asz = a.size();
  auto bsz = b.size();
  if (asz>bsz) return true;
  if (asz1){
      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[randint(0, 3, gen)](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& 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[randint(0, 3, gen)](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 gen_valid_mazes() {
  std::vector 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& 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 str_to_moves(std::string str) {
  std::vector 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& moves, std::vector& 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::max();
constexpr int FALSELIT = -TRUELIT;

int new_var(){
  static int next_var = 1;
  assert(next_var0 ? 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& 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& 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 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 lits){
  return lit_op(lits,1);
}

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

using A4 = std::array;

void add_maze_conditions(Maze m, std::vector 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 posn {};
    for(int p=0; p<9; ++p){
      int ep = encoded_pos[p];
      if((1ull << ep) & m.reach){
        std::set 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 <<
    " n   where  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 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 dirs;
  for(int i=0; i 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

Premier configure.sh et make le lingeling solveur, puis compilez le
programme avec quelque chose comme
g++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl... est le
chemin où lglib.h resp. liblgl.a sont, donc les deux pourraient par exemple être
../lingeling-.
Ou simplement les mettre dans le même répertoire et faire
sans le -I et -L options.

Le programme prend un argument de ligne de commande obligatoire, une chaîne composée de
de N, E, S, W (pour les directions fixes) ou *. On peut donc rechercher
une solution générale de taille 78 en donnant une chaîne de 78 *(entre guillemets),
ou rechercher une solution commençant par NEWS en utilisant NEWS suivi de
autant de *que vous voulez pour les étapes supplémentaires. Comme premier test, prenez votre
solution préférée et remplacez certaines des lettres par *.
Cela permet de trouver une solution rapidement pour une valeur étonnamment élevée de "certaines".

Le programme dira quel labyrinthe il ajoute, décrit par la structure des murs et la
position de départ, et donne également le nombre de positions et de murs atteignables.
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.
lettres adjacentes, j'ai essayé de les remplacer par n'importe quelles 25 lettres. J'ai aussi essayé d'enlever
13 lettres du début et de la fin, et de les remplacer par 13 lettres au début et 12 à la fin.
par 13 au début et 12 à la fin, et vice versa. Malheureusement, tout cela est
insatisfaisant. Donc, pouvons-nous considérer cela comme un indicateur que la longueur 79 est
optimale ? Non, j'ai également essayé d'améliorer la solution de la longueur 80 à la longueur 79,
et ça n'a pas marché non plus.

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

Nous vous invitons à ajouter de la valeur à notre contenu informatif en apportant votre expérience dans les notes.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.