Ho fatto alcuni problemi con il programma di programmazione, e ho notato che molti di essi riguardano qualcosa del tipo "ottenere il numero minimo di passaggi necessari per raggiungere un determinato obiettivo".
Esempi:
- Data la posizione di un cavaliere e di alcune pedine in una scacchiera, qual è il numero minimo di salti che il cavaliere deve fare per uccidere tutte le pedine?
- Dato un parcheggio con auto disordinate etichettate in ordine alfabetico, una "mossa" è il processo di prendere una macchina e inserirla altrove. Qual è il numero minimo di mosse per ottenere questo parcheggio ordinato?
Quindi molti puzzle sembrano condividere questa struttura: dato uno scenario, alcune regole e un insieme di "operazioni", determina la quantità minima di operazioni per raggiungere un obiettivo specifico.
Tuttavia, alcuni di questi rompicapo hanno una svolta: a volte i puzzle chiedono anche se è impossibile raggiungerli.
Ho scoperto che sono particolarmente terribile con questo tipo di enigmi. In effetti, non penso di averli mai risolti in un modo elegante.
Non sono sicuro di come "testare tutti i casi", "scegliere il più breve" o "determinare che sia impossibile". Puoi consigliarmi qui?
Per amore della domanda, possiamo basarci sul puzzle degli scacchi:
Esempio di problema
Abbiamo una scacchiera. Ogni quadrato è etichettato con un numero (che rappresenta la posizione), da 1 a 64.
(Possibile) Input
2 8 31 13
Questo significa "due pedoni, sulle posizioni 8 e 31. Il cavaliere è in posizione 13".
Output
2
Due passaggi. Dalla posizione 13 , il cavaliere può saltare a 8 , e da 8 , può saltare a 31 .
La domanda
Come posso affrontare questo tipo di problema? Ho risolto il problema degli scacchi generando un elenco di tutti i passaggi possibili e quindi ho scelto quello più breve. Ma è stato molto lento.