Algoritmo per ospitare Zoombini sul traghetto del Capitano Cajun?

Question

Algoritmo per ospitare Zoombini sul traghetto del Capitano Cajun?

#1 da (8 voti)

12

Recentemente ho suonato di nuovo in The Logical Journey of the Zoombinis e ho cercato di implementare alcuni algoritmi informatici in grado di risolvere i vari enigmi. Sono bloccato su come affrontare il rompicapo del capitano Cajun.

Per chi non ha familiarità, uno Zoombini è una creatura con 4 attributi: capelli, occhi, naso e piedi. Ognuno di questi attributi ha 5 possibili valori; per esempio, i piedi di un Zoombini possono essere ruote, pattini a rotelle, scarpe da ginnastica, una molla o un'elica. Ecco un esempio di Zoombini con capelli disordinati, occhiali, un naso verde e scarpe da ginnastica:

Nel puzzle del traghetto, il compito è di organizzare una collezione di 16 Zoombinis sui sedici posti di un traghetto. L'accordo deve obbedire alla regola secondo la quale qualsiasi due posti confinanti ortogonalmente deve essere occupato da Zoombinis che condividono almeno una caratteristica. Se due Zoombinis hanno capelli diversi, occhi diversi, nasi diversi, e piedi diversi l'uno dall'altro, potrebbero non sedersi uno accanto all'altro.

La disposizione dei posti cambia per livello; per la concretezza, concentriamoci sul livello "Molto difficile", in cui i 16 posti sono disposti in una griglia 4 per 4. Ecco un esempio in cui 15 Zoombinis sono stati legalmente seduti, ma l'ultimo Zoombini in piedi sul banco degli imputati non può essere collocato sull'ultimo posto vuoto, perché non condividerebbe alcuna funzionalità con Zoombini alla sua destra:

Ce ne sono 16! ≈ 21 trilioni di incarichi possibili di Zoombini ai posti. Quindi, semplicemente, eseguire tutti i compiti possibili per vedere se è legale non sarà pratico. Quali sono alcune euristiche che potrei impiegare per affrontare sensibilmente questo problema?

algorithms

posta thecommexokid 23.07.2016 - 05:48

fonte

1 risposta

Leggi altre domande sui tag algorithms

Qualcuno ha avuto successo con la vendita di codice sorgente, in siti come code canyon? [chiuso] Quando dovremmo usare entità deboli durante la modellazione di un database?

score 8 · Answer 1

Grazie a @mattecapu per l'utile termine di ricerca di Google di "algoritmo di backtracking". Questo mi ha dato lo spunto di riflessione di cui avevo bisogno.

La mia attuale intuizione è che potrebbe essere meglio riempire i posti centrali, che hanno 4 vicini di casa, e salvare i sedili d'angolo, che hanno solo 2 vicini, per ultimi. Quindi sistemo i 16 posti vuoti in una lista concatenata in questo ordine:

13   5   6  14

 7   1   2   9

 8   3   4  10

15  11  12  16

Ecco alcuni pseudocodici che descrivono la funzione che ho finito per scrivere. Gli fornisci un elenco contenente i 16 Zoombini e un puntatore al primo posto nella lista concatenata.

function recursively_assign_seat(zoombini_list, seat):

    if zoombini_list is empty:
        return True

    else:
        for each z in zoombini_list:

            for each n in seat.neighbors:
                if not allowed_as_neighbors(z, n):
                    next z

            seat.occupant ← z
            if recursively_assign_seat(zoombini_list.remove(z), seat.next):
                return True
            else:
                seat.occupant ← None

        return False

In realtà funziona sorprendentemente rapidamente! Mi ha fatto molto piacere.

Non sono ancora del tutto convinto di aver organizzato l'elenco dei posti nel miglior ordine possibile. Ci sono 24 vincoli totali sul problema, e l'ordine ideale di riempimento del sedile dovrebbe affrontare ciascuno di questi vincoli il prima possibile nel processo di riempimento del sedile, in modo che i rami non vitali vengano tagliati rapidamente al massimo.