Come risolvere questo puzzle Loopy in modo efficiente con poco backtracking?

Nov 07 2020

Vorrei risolvere questo puzzle di Loopy (Il Cairo) :

Ma vorrei farlo con il minor numero di passi indietro possibile. Con questo intendo che voglio avere al massimo un'ipotesi in sospeso alla volta; Non voglio fare ulteriori ipotesi se ne ho già fatta una che non è stata ancora smentita. Credo che sia possibile utilizzare alcuni modelli locali, ma o non ho trovato abbastanza modelli locali per aiutarmi, o in realtà è più difficile farlo che indovinare di più e fare più backtracking. Sono riuscito a risolvere questo enigma, ma mi ci è voluto molto tempo per trovare percorsi di ricerca adatti che avevano solo un'ipotesi in sospeso in qualsiasi momento.

Per porre la mia domanda in un altro modo, qual è la soluzione puramente logica più breve che puoi trovare per trovare la soluzione a questo puzzle e dimostrare che è unico?

Ecco un punto in cui non ho potuto procedere localmente:

Ho quindi utilizzato il backtracking di 1 ipotesi per ottenere quanto segue (ovvero in ciascuno dei 3 punti la rimozione di quei bordi porterebbe a una contraddizione):

Risposte

9 bobble Nov 07 2020 at 11:49

Ok, quindi ho risolto l'intero puzzle :) Userò questo puzzle specifico per mostrare diverse deduzioni interessanti. Ogni immagine mostrerà una deduzione che considero non banale, e tra le immagini farò deduzioni banali. In questo post, le detrazioni "banali" sono:

se una cella ha tutti i suoi bordi parlati (ad esempio un 3 che ha un bordo ombreggiato), rimuovo tutti gli altri bordi
se una cella ha solo il numero minimo di bordi rimasti (ad esempio un 3 che ha 2 bordi rimossi), contrassegno tutti gli altri bordi come usati
se una linea ha solo un'altra linea a cui potrebbe estendersi, la estendo
se un bordo creerebbe un fork nel loop, lo rimuovo
se un bordo chiudesse il ciclo, lo rimuovo

Ogni detrazione avrà la sua area cerchiata. Alcuni hanno anche frecce che puntano a linee importanti. Se vuoi calcolare da solo le detrazioni, fai clic solo sul primo spoiler di ogni coppia per vedere dove sarà la detrazione. Nelle mie spiegazioni, una cifra si riferisce a un numero di indizio e un numero scritto si riferisce a una quantità . Qualche terminologia che uso qui:

"lati" e "bordi" sono usati in modo intercambiabile per riferirsi ai bordi di una singola cella-indizio
"muri" e "linee" sono termini generici per una sezione confermata di loop
"corner" è un punto in cui si incontrano più confini possibili
I lati "nudi" sono quelli che devono essere usati insieme per scopi di connettività, ad esempio uno qualsiasi dei lati del confine esterno

Sulle detrazioni!

La detrazione:

I 4 possono avere solo 1 bordo inutilizzato. Quel confine deve essere uno di quelli adiacenti alla linea proveniente dal 3; se vengono utilizzati entrambi i bordi adiacenti, viene creato un fork nel ciclo. Pertanto deve essere utilizzato ogni bordo non adiacente alla linea del 3

La detrazione:

Questo è simile alla detrazione precedente. Il 3 deve usare uno, e solo uno, dei suoi lati rimanenti. Indipendentemente da quale lato viene utilizzato, il lato dei 3 agirà come la dimensione fondamentale dalla detrazione precedente. Pertanto devono essere utilizzati tutti i lati del 4 che non sono adiacenti al 3.

La detrazione:

Qui la stessa detrazione può essere utilizzata due volte. Entrambi questi 2 devono utilizzare esattamente uno dei due lati rimanenti. Entrambi i lati useranno l'angolo "centrale". La linea non confinante con il 2, ma collegata all'angolo "centrale", deve essere utilizzata per evitare di utilizzare entrambi i bordi rimanenti del 2.

La detrazione:

Questa è una deduzione simile a quella precedente. Deve essere utilizzato uno, e solo uno, dei lati rimanenti dell'1, quindi deve essere utilizzato il lato esterno che si collega all '"angolo" centrale. L'ho contrassegnato con una freccia per chiarezza. Dal momento che viene utilizzato, possiamo applicare il contrario di questa detrazione al 3. Uno, e solo uno, dei lati rimanenti dei 3 deve essere utilizzato - e il lato che abbiamo colorato deve essere il connettore "angolare" esterno, poiché solo può essere utilizzato un lato esterno. (Se vengono utilizzati entrambi, i lati dei 3 creerebbero una forchetta)

Le detrazioni (due correlate):

Ci sono due pareti "nude" su un lato delle 3 che devono essere usate insieme, e poi altre tre. Se i muri "nudi" non vengono utilizzati, viene creata una biforcazione con gli altri tre muri e la linea da 1. Pertanto vengono utilizzati i muri "nudi". Ora è possibile utilizzare solo un muro in più. Se viene utilizzato il muro verso cui punta la freccia, la linea dall'1 non può essere estesa. Quindi quel muro non viene utilizzato.

Le detrazioni (due correlate):

Ci sono due linee che conducono al 2. Se si estendono, si utilizzerà uno dei due lati assegnati. Questi sono tutti i lati che possono essere utilizzati, quindi la linea con una freccia che punta ad esso non può essere utilizzata. Dato che quel lato non viene utilizzato, i due bordi per il vicino 2 sono ora "nudi" e devono essere usati insieme. Tranne che non possono essere, dal momento che un lato di quel 2 è già utilizzato. Quindi nessuno di questi bordi può essere utilizzato.

La detrazione:

Il 3 cerchiato ha due lati "nudi". Se non vengono utilizzati, rimangono solo due lati, che sono troppo pochi. Pertanto vengono utilizzati i lati "nudi".

Le detrazioni (due correlate):

Il lato sinistro cerchiato con 1 ha due lati "nudi". Non possono essere utilizzati, poiché due lati sono troppi per un 1 da usare. Il lato destro cerchiato con 1 ha una linea che lo conduce. Se viene utilizzato uno qualsiasi dei lati non adiacenti a quella linea, la linea non può estendersi da nessuna parte. Quindi tutti i lati non adiacenti sono inutilizzati.

Le detrazioni (due correlate):

Il 3 di sinistra cerchiato ha solo due modi per usare esattamente tre lati: i due "nudi" in alto e il lato più a destra, o i due "nudi" in basso e il lato più a destra. Da questo è chiaro che deve essere usato il lato più a destra, e deve essere usato il lato che porta ad entrambi quelli "nudi" da sinistra. Il lato destro cerchiato 4 ha una linea che porta in alto e in basso (perché almeno uno dei due lati rimanenti per il 3 inferiore deve essere utilizzato). È possibile utilizzare solo uno di ciascun bordo adiacente a quelle linee di entrata, per evitare un fork nel loop. Per utilizzare tre bordi, quindi, deve essere utilizzato l'unico lato non adiacente.

La detrazione:

La linea che porta a questa sezione inferiore (freccia nera) deve salire ad un certo punto per connettersi al resto del loop. Per salire è necessario utilizzare la linea puntata dalla freccia rossa.

Per il completamento, la soluzione:

In risposta ai commenti:

Sembra che tu stia chiedendo una soluzione logica dalla tua seconda immagine, non dalla tua terza immagine. Di seguito presento una tale soluzione. Questa volta salto tutte le deduzioni banali, così come le detrazioni che ho trattato nelle immagini sopra.