Skip to content

Stringa di uscita dal labirinto universale più breve

Ti consigliamo di testare questa soluzione in un ambiente controllato prima di inviarla alla produzione, saluti.

Soluzione:

C++, 9795939186838281 79 caratteri

NNWSWNNSENESESWSSWNSEENWWNESESEN TRAWSWNWSSENESENESENESESWESEWWNENWNEES

La mia strategia è abbastanza semplice: un algoritmo di evoluzione che può crescere, restringersi, scambiare elementi e mutare sequenze valide. La mia logica di evoluzione è ora quasi uguale a quella di @Sp3000, dato che la sua è stata un miglioramento rispetto alla mia.

Tuttavia, la mia implementazione della logica del labirinto è piuttosto ingegnosa. Questo mi permette di controllare se le stringhe sono valide a una velocità impressionante. Cercate di capirlo guardando il commento, do_move e il commento Maze del costruttore.

#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 caratteri

SWWNNSENESESWSSWSEENWNWSWSEWNWNENENWWSESSEWSWNWSENWEENWWNNESENESSWNWSESESWWNNESE

Ho esitato a pubblicare questa risposta perché ho fondamentalmente preso l'approccio di orlp e ci ho messo del mio. Questa stringa è stata trovata partendo da una soluzione pseudorandom di lunghezza 500 - sono stati provati diversi semi prima di riuscire a battere il record attuale.

L'unica nuova ottimizzazione di rilievo è che considero solo un terzo dei labirinti. Due categorie di labirinti sono escluse dalla ricerca:

  • Labirinti in cui <= 7 quadrati sono raggiungibili
  • Labirinti in cui tutte le caselle raggiungibili sono su un unico percorso e la partenza e l'arrivo non sono a entrambe le estremità

L'idea è che qualsiasi stringa che risolva il resto dei labirinti dovrebbe risolvere automaticamente anche quelli di cui sopra. Sono convinto che questo sia vero per il secondo tipo, ma non lo è sicuramente per il primo, quindi l'output conterrà alcuni falsi positivi che devono essere controllati separatamente. Questi falsi positivi, però, di solito mancano solo una ventina di labirinti, quindi ho pensato che fosse un buon compromesso tra velocità e accuratezza, oltre a dare alle stringhe un po' più di respiro per mutare.

Inizialmente ho esaminato una lunga lista di euristiche di ricerca, ma terribilmente nessuna di esse ha prodotto qualcosa di meglio di 140 o giù di lì.

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++ e la libreria di lingeling

Sommario: Un nuovo approccio, nessuna nuova soluzione un bel programma con cui giocare
e alcuni interessanti risultati di non migliorabilità locale delle soluzioni conosciute.
soluzioni note. Oh, e alcune osservazioni generalmente utili.

Utilizzando un approccio basato su SAT
sono riuscito a risolvere completamente
risolvere
il problema simile per labirinti 4x4 con celle bloccate invece di pareti sottili
e posizioni di partenza e di uscita fisse agli angoli opposti.
Speravo quindi di poter utilizzare le stesse idee per questo problema.
Tuttavia, anche se per l'altro problema ho utilizzato solo 2423 labirinti
(nel frattempo è stato osservato che ne bastano 2083) e abbia una soluzione di lunghezza
una soluzione di lunghezza 29, la codifica SAT utilizzava milioni di variabili
e la soluzione ha richiesto giorni.

Ho quindi deciso di cambiare l'approccio in due modi importanti:

  • Non insistere nel cercare una soluzione da zero, ma permettere di fissare
    una parte della stringa della soluzione. (Questo è facile da fare in ogni caso aggiungendo clausole di unità
    ma il mio programma lo rende comodo da fare).
  • Non utilizzare tutti i labirinti dall'inizio. Invece, aggiungete in modo incrementale un
    un labirinto irrisolto alla volta. Alcuni labirinti possono essere risolti per caso, oppure sono
    sempre risolti quando quelli già considerati sono stati risolti. In quest'ultimo caso
    caso, non verrà mai aggiunto, senza che sia necessario conoscerne l'implicazione.

Ho fatto anche alcune ottimizzazioni per usare meno variabili e clausole unitarie.

Il programma è basato su quello di @orlp.
Una modifica importante è stata la selezione dei labirinti:

  • Prima di tutto, i labirinti sono dati dalla struttura delle pareti e dalla posizione di partenza.
    posizione di partenza. (Vengono memorizzate anche le posizioni raggiungibili).
    La funzione is_solution controlla se tutte le posizioni raggiungibili sono state raggiunte.
  • (Invariato: non si usano ancora i labirinti con solo 4 o meno posizioni raggiungibili.
    Ma la maggior parte di essi verrebbe comunque eliminata dalle osservazioni seguenti).
  • Se un labirinto non utilizza nessuna delle tre celle superiori, è equivalente a un
    labirinto spostato verso l'alto. Quindi possiamo eliminarlo. Allo stesso modo, un labirinto che non
    non utilizza nessuna delle tre celle di sinistra.
  • Non importa se le parti irraggiungibili sono collegate, quindi insistiamo sul fatto che
    ogni cella irraggiungibile sia completamente circondata da pareti.
  • Un labirinto a percorso singolo che è un sottomaschera di un labirinto a percorso singolo più grande è sempre
    risolto quando viene risolto quello più grande, quindi non ne abbiamo bisogno. Ogni labirinto a percorso singolo
    di dimensione massima 7 fa parte di un labirinto più grande (che rientra comunque in 3x3), ma ci sono labirinti a percorso singolo di dimensione
    ci sono labirinti a percorso singolo di dimensione 8 che non lo sono. Per semplicità, lasciamo
    di labirinti a percorso singolo di dimensione inferiore a 8. (E sto ancora usando che solo
    solo i punti estremi devono essere considerati come posizioni di partenza.
    Tutte le posizioni sono usate come posizioni di uscita, il che è importante solo per la parte SAT del programma).
    del programma).

In questo modo, ottengo un totale di 10772 labirinti con posizioni iniziali.

Ecco il programma:

#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

Primo configure.sh e make il lingeling solutore, quindi compilare il programma
con qualcosa di simile a
g++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgldove ... è il
percorso in cui lglib.h risp. liblgl.a quindi, ad esempio, entrambi potrebbero essere
../lingeling-.
Oppure si possono mettere nella stessa cartella e fare
senza l'opzione -I e -L e -L.

Il programma accetta un argomento obbligatorio da riga di comando, una stringa composta da
di N, E, S, W (per direzioni fisse) o *. Quindi si può cercare
una soluzione generale di dimensione 78 dando una stringa di 78 *(tra virgolette),
oppure cercare una soluzione che inizi con NEWS utilizzando NEWS seguito da
come tanti *per i passi aggiuntivi. Come prima prova, prendete la vostra
soluzione preferita e sostituite alcune lettere con *.
In questo modo si trova una soluzione veloce per un valore sorprendentemente alto di "alcuni".

Il programma dirà quale labirinto aggiunge, descritto dalla struttura delle pareti e dalla posizione di partenza.
e la posizione di partenza, oltre a fornire il numero di posizioni e pareti raggiungibili.
I labirinti vengono ordinati in base a questi criteri e viene aggiunto il primo non risolto.
Pertanto, la maggior parte dei labirinti aggiunti ha (9/4)ma a volte ne compaiono anche altri.

Ho preso la soluzione nota di lunghezza 79 e, per ogni gruppo di 26 lettere adiacenti, ho cercato di sostituirle con 25 lettere qualsiasi.
lettere adiacenti, ho provato a sostituirle con 25 lettere qualsiasi. Ho anche provato a rimuovere
13 lettere dall'inizio e dalla fine e sostituirle con 13 lettere qualsiasi all'inizio e 12 qualsiasi alla fine.
all'inizio e 12 alla fine, e viceversa. Sfortunatamente, tutti i risultati
non soddisfacenti. Quindi, possiamo considerare questo come un indicatore che la lunghezza 79 è
ottimale? No, ho provato a migliorare anche la soluzione di lunghezza 80 in lunghezza 79, ma anche questo non ha avuto successo,
e anche questo non ha avuto successo.

Infine, ho provato a combinare l'inizio di una soluzione con la fine dell'altra, e anche con una soluzione trasformata per
e anche con una soluzione trasformata da una delle simmetrie.
Ora sto esaurendo le idee interessanti, così ho deciso di mostrarvi quello che ho
anche se non ha portato a nuove soluzioni.

Recensioni e valutazioni della guida

Apprezziamo che desideri aggiungere valore alle nostre informazioni fornendo la tua esperienza nelle dimensioni.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.