Enigma:Il puzzle quadrato
https://stackoverflow.com/questions/767912
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Negli ultimi due giorni mi sono trattenuto dagli studi del master e mi sono concentrato su questo puzzle (apparentemente semplice):
C'è questa griglia 10*10 che costituisce un quadrato di 100 posti disponibili dove andare.Lo scopo è partire da un angolo e attraversare tutti i luoghi rispettando alcune semplici "regole di attraversamento" e raggiungere il numero 100 (o 99 se sei un programmatore e inizi invece da 0 :)
Le regole per l'attraversamento sono:
1.Due spazi saltano lungo l'asse verticale e orizzontale
2.Salta di uno spazio lungo le diagonali
3.Puoi visitare ogni piazza una sola volta
Per visualizzare meglio, ecco un esempio valido di traversata (fino all'ottavo passo):
Esempio di attraversamento http://img525.imageshack.us/img525/280/squarepuzzle.png
Manualmente, ho lavorato su questo puzzle per noia.Per anni ho provato di tanto in tanto a risolverlo a mano, ma non sono mai andato oltre i 96.Sembra facile?Prova tu stesso e guarda tu stesso :)
Pertanto, per risolvere il problema, ho sviluppato un breve programma (circa 100 righe di codice) in Python.Sono un principiante in questa lingua, volevo vedere cosa posso fare.
Il programma applica semplicemente una tecnica esaustiva di prova e risoluzione degli errori.In altre parole:Prima ricerca della profondità della forza bruta.
La mia domanda nasce da qui in poi:Il programma purtroppo non riesce a risolvere il problema perché lo spazio degli stati è così grande che la ricerca non finisce mai senza trovare una soluzione.Può arrivare fino al numero 98 (e stamparlo) senza troppe difficoltà, tuttavia non è una soluzione completa.
Il programma stampa anche la lunghezza dell'albero di ricerca coperto finora.In un paio di minuti, l'elenco delle traverse, ad esempio, dal 65° elemento è coperto fino alla fine, per un solo percorso.Questo numero diminuisce in periodi di tempo che aumentano esponenzialmente.Ho eseguito il codice per un bel po' di tempo e non sono riuscito a superare la barriera di 50 e ora ne sono convinto.
Sembra che questo semplice approccio non sarà sufficiente a meno che non lo utilizzi per sempre.Quindi, come posso migliorare il mio codice per renderlo più veloce ed efficiente in modo da trovare soluzioni?
Fondamentalmente, non vedo l'ora di vedere idee su come:
- Catturare e sfruttare conoscenza del dominio specifico per questo problema
Fare domanda a tecniche/trucchi di programmazione per superare l'esaurimento
..e finalmente concretizzarsi in una soluzione sostanziale.
Grazie in anticipo.
Revisione
Grazie a Dave Webb per aver correlato il problema al dominio di appartenenza:
Questo è molto simile al problema del tour del cavaliere che mette in relazione lo spostamento di un cavaliere attorno a una scacchiera senza rivisitare la stessa piazza.Fondamentalmente è lo stesso problema ma con diverse "regole di traversa".
Soluzione 3
Alla fine, ho creato il codice Python modificato per superare il problema.Ho messo a punto il codice per un paio d'ore e in un paio d'ore ha già trovato mezzo milione di soluzioni.
L'insieme completo delle soluzioni richiede ancora una ricerca esaustiva totale, vale a direper far funzionare il programma finché non termina con tutte le combinazioni.Tuttavia, il raggiungimento di “una” soluzione legittima può essere ridotto al “tempo lineare”.
Innanzitutto, le cose che ho imparato:
Grazie a La risposta di Dave Webb E La risposta di ammoQ.Il problema è infatti un'estensione del problema del Cammino Hamiltoniano in quanto è NP-Difficile.Non esiste una soluzione “facile” per cominciare.C'è un famoso indovinello Giro del Cavaliere che è semplicemente lo stesso problema con una diversa dimensione della tavola/griglia e diverse regole trasversali.Sono state dette e fatte molte cose per elaborare il problema e sono state ideate metodologie e algoritmi.
Grazie a La risposta di Joe.Il problema può essere affrontato dal basso verso l’alto e può essere suddiviso in sottoproblemi risolvibili.I sottoproblemi risolti possono essere collegati in una nozione di punto di ingresso-uscita (il proprio punto di uscita può essere collegato al punto di ingresso di un altro) in modo che il problema principale possa essere risolto come costituzione di problemi su scala più piccola.Questo approccio è valido e pratico ma non completo, tuttavia.Non può garantire di trovare una risposta se esiste.
Dopo un'esaustiva ricerca a forza bruta, ecco i punti chiave che ho sviluppato sul codice:
Algoritmo di Warnsdorff:Questo algoritmo è il punto chiave per raggiungere un numero utile di soluzioni in modo rapido.Afferma semplicemente che dovresti scegliere la tua prossima mossa nel luogo "meno accessibile" e popolare l'elenco "andare" con ordine ascendente o accessibilità.Posto meno accessibile indica il luogo con il minor numero di possibili mosse seguenti.
Di seguito è riportato lo pseudocodice (da Wikipedia):
Alcune definizioni:
- Una posizione Q è accessibile da una posizione P se P può spostarsi a Q con una singola mossa del cavaliere e Q non è stata ancora visitata.
- L'accessibilità di una posizione P è il numero di posizioni accessibili da P.
Algoritmo:
Impostare P su una posizione iniziale casuale sul segnali di scheda la scheda in p con il numero di spostamento "1" per ciascun numero di sposta Imposta p su una posizione in s con l'accessibilità minima contrassegnare la scheda in P con il numero di mossa corrente restituire la scheda contrassegnata: ogni quadrato sarà contrassegnato con il numero di spostamento su cui viene visitato.
- Controllo delle isole:Un bel exploit della conoscenza del dominio qui si è rivelato utile.Se una mossa (a meno che non sia l'ultima) causerebbe Qualunque dei suoi vicini a diventare un'isola, cioènon accessibile da nessun altro, quel ramo non viene più indagato.Risparmia una notevole quantità di tempo (circa il 25%) combinato con l'algoritmo di Warnsdorff.
Ed ecco il mio codice in Python che risolve l'enigma (in misura accettabile considerando che il problema è NP-Hard).Il codice è facile da capire poiché mi considero a livello principiante in Python.I commenti sono semplici nello spiegare l'implementazione.Le soluzioni possono essere visualizzate su una semplice griglia tramite una GUI di base (linee guida nel codice).
# Solve square puzzle
import operator
class Node:
# Here is how the squares are defined
def __init__(self, ID, base):
self.posx = ID % base
self.posy = ID / base
self.base = base
def isValidNode(self, posx, posy):
return (0<=posx<self.base and 0<=posy<self.base)
def getNeighbors(self):
neighbors = []
if self.isValidNode(self.posx + 3, self.posy): neighbors.append(self.posx + 3 + self.posy*self.base)
if self.isValidNode(self.posx + 2, self.posy + 2): neighbors.append(self.posx + 2 + (self.posy+2)*self.base)
if self.isValidNode(self.posx, self.posy + 3): neighbors.append(self.posx + (self.posy+3)*self.base)
if self.isValidNode(self.posx - 2, self.posy + 2): neighbors.append(self.posx - 2 + (self.posy+2)*self.base)
if self.isValidNode(self.posx - 3, self.posy): neighbors.append(self.posx - 3 + self.posy*self.base)
if self.isValidNode(self.posx - 2, self.posy - 2): neighbors.append(self.posx - 2 + (self.posy-2)*self.base)
if self.isValidNode(self.posx, self.posy - 3): neighbors.append(self.posx + (self.posy-3)*self.base)
if self.isValidNode(self.posx + 2, self.posy - 2): neighbors.append(self.posx + 2 + (self.posy-2)*self.base)
return neighbors
# the nodes go like this:
# 0 => bottom left
# (base-1) => bottom right
# base*(base-1) => top left
# base**2 -1 => top right
def solve(start_nodeID, base):
all_nodes = []
#Traverse list is the list to keep track of which moves are made (the id numbers of nodes in a list)
traverse_list = [start_nodeID]
for i in range(0, base**2): all_nodes.append(Node(i, base))
togo = dict()
#Togo is a dictionary with (nodeID:[list of neighbors]) tuples
togo[start_nodeID] = all_nodes[start_nodeID].getNeighbors()
solution_count = 0
while(True):
# The search is exhausted
if not traverse_list:
print "Somehow, the search tree is exhausted and you have reached the divine salvation."
print "Number of solutions:" + str(solution_count)
break
# Get the next node to hop
try:
current_node_ID = togo[traverse_list[-1]].pop(0)
except IndexError:
del togo[traverse_list.pop()]
continue
# end condition check
traverse_list.append(current_node_ID)
if(len(traverse_list) == base**2):
#OMG, a solution is found
#print traverse_list
solution_count += 1
#Print solution count at a steady rate
if(solution_count%100 == 0):
print solution_count
# The solution list can be returned (to visualize the solution in a simple GUI)
#return traverse_list
# get valid neighbors
valid_neighbor_IDs = []
candidate_neighbor_IDs = all_nodes[current_node_ID].getNeighbors()
valid_neighbor_IDs = filter(lambda id: not id in traverse_list, candidate_neighbor_IDs)
# if no valid neighbors, take a step back
if not valid_neighbor_IDs:
traverse_list.pop()
continue
# if there exists a neighbor which is accessible only through the current node (island)
# and it is not the last one to go, the situation is not promising; so just eliminate that
stuck_check = True
if len(traverse_list) != base**2-1 and any(not filter(lambda id: not id in traverse_list, all_nodes[n].getNeighbors()) for n in valid_neighbor_IDs): stuck_check = False
# if stuck
if not stuck_check:
traverse_list.pop()
continue
# sort the neighbors according to accessibility (the least accessible first)
neighbors_ncount = []
for neighbor in valid_neighbor_IDs:
candidate_nn = all_nodes[neighbor].getNeighbors()
valid_nn = [id for id in candidate_nn if not id in traverse_list]
neighbors_ncount.append(len(valid_nn))
n_dic = dict(zip(valid_neighbor_IDs, neighbors_ncount))
sorted_ndic = sorted(n_dic.items(), key=operator.itemgetter(1))
sorted_valid_neighbor_IDs = []
for (node, ncount) in sorted_ndic: sorted_valid_neighbor_IDs.append(node)
# if current node does have valid neighbors, add them to the front of togo list
# in a sorted way
togo[current_node_ID] = sorted_valid_neighbor_IDs
# To display a solution simply
def drawGUI(size, solution):
# GUI Code (If you can call it a GUI, though)
import Tkinter
root = Tkinter.Tk()
canvas = Tkinter.Canvas(root, width=size*20, height=size*20)
#canvas.create_rectangle(0, 0, size*20, size*20)
canvas.pack()
for x in range(0, size*20, 20):
canvas.create_line(x, 0, x, size*20)
canvas.create_line(0, x, size*20, x)
cnt = 1
for el in solution:
canvas.create_text((el % size)*20 + 4,(el / size)*20 + 4,text=str(cnt), anchor=Tkinter.NW)
cnt += 1
root.mainloop()
print('Start of run')
# it is the moment
solve(0, 10)
#Optional, to draw a returned solution
#drawGUI(10, solve(0, 10))
raw_input('End of Run...')
Grazie a tutti coloro che condividono le loro conoscenze e idee.
Altri suggerimenti
Questo è molto simile al Giro del Cavaliere problema che riguarda lo spostamento di un cavallo su una scacchiera senza rivisitare la stessa casa.Fondamentalmente è lo stesso problema ma con "Regole di traversata" diverse.
L'ottimizzazione chiave che ricordo di aver affrontato ricorsivamente il Knights Tour è di eseguire le mosse successive in ordine crescente rispetto al numero di mosse disponibili nella casella di destinazione.Ciò incoraggia la ricerca a provare a spostarsi densamente in un'area e a riempirla piuttosto che ingrandire tutto il tabellone e lasciare piccoli quadrati di isole che non potranno mai essere visitati.(Questo è Algoritmo di Warnsdorff.)
Assicurati anche di aver considerato la simmetria dove puoi.Ad esempio, al livello più semplice, xey della casella iniziale devono solo arrivare a 5 poiché (10,10) è uguale a (1,1) con la tavola ruotata.
Ho deciso di esaminare il problema e vedere se potevo suddividerlo in soluzioni 5x5 con la fine di una soluzione a un salto dall'angolo di un'altra.
Il primo presupposto era che 5x5 fosse risolvibile.Lo è e velocemente.
Quindi ho eseguitosolve(0,5) e ho guardato i risultati.Ho disegnato una griglia numerata 10x10 in Excel con una griglia numerata 5x5 per la traduzione.Quindi ho semplicemente cercato i risultati per #] (celle finali) che sarebbe un salto di distanza dall'inizio del prossimo 5x5.(ex.per il primo quadrato ho cercato "13]".)
Per riferimento:
10 x 10 grid 5 x 5 grid
0 1 2 3 4 | 5 6 7 8 9 0 1 2 3 4
10 11 12 13 14 | 15 16 17 18 19 5 6 7 8 9
20 21 22 23 24 | 25 26 27 28 29 10 11 12 13 14
30 31 32 33 34 | 35 36 37 38 39 15 16 17 18 19
40 41 42 43 44 | 45 46 47 48 49 20 21 22 23 24
---------------+---------------
50 51 52 53 54 | 55 56 57 58 59
60 61 62 63 64 | 65 66 67 68 69
70 71 72 73 74 | 75 76 77 78 79
80 81 82 83 84 | 85 86 87 88 89
90 91 92 93 94 | 95 96 97 98 99
Ecco una possibile soluzione:
Primo quadrato:[0, 15, 7, 19, 16, 1, 4, 12, 20, 23, 8, 5, 17, 2, 10, 22, 14, 11, 3, 18, 6, 9, 24, 21, 13 ] inserisce un salto diagonale fino a 5 (in 10x10) il primo angolo del successivo 5 x 5.
Secondo quadrato:[0, 12, 24, 21, 6, 9, 17, 2, 14, 22, 7, 15, 18, 3, 11, 23, 20, 5, 8, 16, 19, 4, 1, 13, 10 ] lo inserisce con l'ultimo quadrato di 25 nel 10x10, che è a due salti di distanza da 55.
Terza piazza:[0, 12, 24, 21, 6, 9, 17, 5, 20, 23, 8, 16, 19, 4, 1, 13, 10, 2, 14, 11, 3, 18, 15, 7, 22 ] lo colloca con l'ultimo quadrato di 97 nel 10x10, che è a due salti di distanza da 94.
Fourth Square può essere qualsiasi soluzione valida, perché il punto finale non ha importanza.Tuttavia, la mappatura della soluzione da 5x5 a 10x10 è più difficile, poiché il quadrato inizia dall'angolo opposto.Invece di tradurre, ho eseguito solve(24,5) e ne ho scelto uno a caso:[24, 9, 6, 21, 13, 10, 2, 17, 5, 20, 23, 8, 16, 1, 4, 12, 0, 15, 18, 3, 11, 14, 22, 7, 19 ]
Questo dovrebbe essere possibile per tutti in modo programmatico, ora che si sa che le soluzioni 5x5 sono valide con le mosse legali degli endpoint al successivo angolo 5x5.Il numero di soluzioni 5x5 era 552, il che significa che memorizzare le soluzioni per ulteriori calcoli e rimappatura è piuttosto semplice.
A meno che non abbia sbagliato, questo ti dà una possibile soluzione (definite sopra le soluzioni 5x5 rispettivamente da una a quattro):
def trans5(i, col5, row5):
if i < 5: return 5 * col5 + 50 * row5 + i
if i < 10: return 5 + 5 * col5 + 50 * row5 + i
if i < 15: return 10 + 5 * col5 + 50 * row5 + i
if i < 20: return 15 + 5 * col5 + 50 * row5 + i
if i < 25: return 20 + 5 * col5 + 50 * row5 + i
>>> [trans5(i, 0, 0) for i in one] + [trans5(i, 1, 0) for i in two] + [trans5(i, 0, 1) for i in three] + [trans5(i, 1, 1) for i in four]
[0, 30, 12, 34, 31, 1, 4, 22, 40, 43, 13, 10, 32, 2, 20, 42, 24, 21, 3, 33, 11, 14, 44, 41, 23, 5, 27, 49, 46, 16, 19, 37, 7, 29, 47, 17, 35, 38, 8, 26, 48, 45, 15, 18, 36, 39, 9, 6, 28, 25, 50, 72, 94, 91, 61, 64, 82, 60, 90, 93, 63, 81, 84, 54, 51, 73, 70, 52, 74, 71, 53, 83, 80, 62, 92, 99, 69, 66, 96, 78, 75, 57, 87, 65, 95, 98, 68, 86, 56, 59, 77, 55, 85, 88, 58, 76, 79, 97, 67, 89]
Qualcuno può ricontrollare la metodologia?Penso che questa sia una soluzione valida e un metodo per risolvere il problema.
Questo è solo un esempio di http://en.wikipedia.org/wiki/Hamiltonian_path problema.Wikipedia tedesca afferma che è NP-difficile.
È possibile eseguire un'ottimizzazione per verificare la presenza di isole (ad es.spazi non visitati senza vicini validi.) e uscire dalla traversata finché l'isola non viene eliminata.Ciò accadrebbe vicino al lato "economico" di un certo attraversamento di alberi.Immagino che la domanda sia se la riduzione vale la spesa.
Volevo vedere se potevo scrivere un programma che fornisse tutte le soluzioni possibili.
#! /usr/bin/env perl
use Modern::Perl;
{
package Grid;
use Scalar::Util qw'reftype';
sub new{
my($class,$width,$height) = @_;
$width ||= 10;
$height ||= $width;
my $self = bless [], $class;
for( my $x = 0; $x < $width; $x++ ){
for( my $y = 0; $y < $height; $y++ ){
$self->[$x][$y] = undef;
}
}
for( my $x = 0; $x < $width; $x++ ){
for( my $y = 0; $y < $height; $y++ ){
$self->[$x][$y] = Grid::Elem->new($self,$x,$y);;
}
}
return $self;
}
sub elem{
my($self,$x,$y) = @_;
no warnings 'uninitialized';
if( @_ == 2 and reftype($x) eq 'ARRAY' ){
($x,$y) = (@$x);
}
die "Attempted to use undefined var" unless defined $x and defined $y;
my $return = $self->[$x][$y];
die unless $return;
return $return;
}
sub done{
my($self) = @_;
for my $col (@$self){
for my $item (@$col){
return 0 unless $item->visit(undef);
}
}
return 1;
}
sub reset{
my($self) = @_;
for my $col (@$self){
for my $item (@$col){
$item->reset;
}
}
}
sub width{
my($self) = @_;
return scalar @$self;
}
sub height{
my($self) = @_;
return scalar @{$self->[0]};
}
}{
package Grid::Elem;
use Scalar::Util 'weaken';
use overload qw(
"" stringify
eq equal
== equal
);
my %dir = (
# x, y
n => [ 0, 2],
s => [ 0,-2],
e => [ 2, 0],
w => [-2, 0],
ne => [ 1, 1],
nw => [-1, 1],
se => [ 1,-1],
sw => [-1,-1],
);
sub new{
my($class,$parent,$x,$y) = @_;
weaken $parent;
my $self = bless {
parent => $parent,
pos => [$x,$y]
}, $class;
$self->_init_possible;
return $self;
}
sub _init_possible{
my($self) = @_;
my $parent = $self->parent;
my $width = $parent->width;
my $height = $parent->height;
my($x,$y) = $self->pos;
my @return;
for my $dir ( keys %dir ){
my($xd,$yd) = @{$dir{$dir}};
my $x = $x + $xd;
my $y = $y + $yd;
next if $y < 0 or $height <= $y;
next if $x < 0 or $width <= $x;
push @return, $dir;
$self->{$dir} = [$x,$y];
}
return @return if wantarray;
return \@return;
}
sub list_possible{
my($self) = @_;
return unless defined wantarray;
# only return keys which are
my @return = grep {
$dir{$_} and defined $self->{$_}
} keys %$self;
return @return if wantarray;
return \@return;
}
sub parent{
my($self) = @_;
return $self->{parent};
}
sub pos{
my($self) = @_;
my @pos = @{$self->{pos}};
return @pos if wantarray;
return \@pos;
}
sub visit{
my($self,$v) = @_;
my $return = $self->{visit} || 0;
$v = 1 if @_ == 1;
$self->{visit} = $v?1:0 if defined $v;
return $return;
}
sub all_neighbors{
my($self) = @_;
return $self->neighbor( $self->list_possible );
}
sub neighbor{
my($self,@n) = @_;
return unless defined wantarray;
return unless @n;
@n = map { exists $dir{$_} ? $_ : undef } @n;
my $parent = $self->parent;
my @return = map {
$parent->elem($self->{$_}) if defined $_
} @n;
if( @n == 1){
my($return) = @return;
#die unless defined $return;
return $return;
}
return @return if wantarray;
return \@return;
}
BEGIN{
for my $dir ( qw'n ne e se s sw w nw' ){
no strict 'refs';
*$dir = sub{
my($self) = @_;
my($return) = $self->neighbor($dir);
die unless $return;
return $return;
}
}
}
sub stringify{
my($self) = @_;
my($x,$y) = $self->pos;
return "($x,$y)";
}
sub equal{
my($l,$r) = @_;
"$l" eq "$r";
}
sub reset{
my($self) = @_;
delete $self->{visit};
return $self;
}
}
# Main code block
{
my $grid = Grid->new();
my $start = $grid->elem(0,0);
my $dest = $grid->elem(-1,-1);
my @all = solve($start,$dest);
#say @$_ for @all;
say STDERR scalar @all;
}
sub solve{
my($current,$dest,$return,@stack) = @_;
$return = [] unless $return;
my %visit;
$visit{$_} = 1 for @stack;
die if $visit{$current};
push @stack, $current->stringify;
if( $dest == $current ){
say @stack;
push @$return, [@stack];
}
my @possible = $current->all_neighbors;
@possible = grep{
! $visit{$_}
} @possible;
for my $next ( @possible ){
solve($next,$dest,$return,@stack);
}
return @$return if wantarray;
return $return;
}
Questo programma ha fornito più di 100.000 possibili soluzioni prima di essere terminato.Ho inviato STDOUT in un file ed era più di 200 MB.
Potresti contare esattamente il numero di soluzioni con un algoritmo di programmazione dinamica a linee di scansione.
