Quizzino della domenica: scacchiera

Avete davanti a voi una scacchiera 5×5, e dovete riempire tutte le caselle con uno dei numeri 0, 1, 2 in modo che due caselle adiacenti (per un lato, non per un angolo) abbiano valori che differiscano esattamente di 1. In quanti modi potete farlo?

(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p198.html; la risposta verrà postata lì il prossimo mercoledì. Problema tratto da Math StackExchange).

11 pensieri su “Quizzino della domenica: scacchiera

      1. Barbara

        NB Il punto esclamativo nel senso di fattoriale, alla mia età, lo vedo ormai solo davanti a lettere, mai a numeri.

        1. gimusi

          dici davvero?…ma diventerebbe un numero enorme…
          ho messo il punto interrogativo perché ho il dubbio che per lo 0 e il 2 in angolo esistano alcune configurazioni simmetriche contate più volte (simmetriche per rotazione intendo, ammesso che i numeri non ruotino)…diciamo che 12288 è un limite superiore :)

  1. gnugnu

    @gimusi:
    di soluzioni ‘contate” più volte, in quanto ottenibili per rotazioni o simmetrie di altre, ve ne sono in abbondanza, ma penso che il quesito non chiedesse la loro riduzione. Il tuo risultato mi piace com’è.
    Ciao
    B.

    1. .mau. Autore articolo

      (senza farmi guardare il video… sono pigro) e come l’hai messo in forma ricorsiva? Per me era semplicemente un problema combinatorio, e il lavorare in due dimensioni mi rende difficile usare tecniche ricorsive standard…

      1. Fulvio Corno

        I livelli di ricorsione corrispondono alle N^2 caselle. Ogni livello deve determinare quale cifra inserire nella casella, scegliendola tra 0, 1, 2.
        Prima di posizionare la cifra, vengono fatti i controlli di adiacenza con le caselle a sinistra e in alto.

        Il fatto che il problema sia bidimensionale impatta solamente i controlli di adiacenza, per il resto è come dover riempire un vettore di N^2 elementi con 3 valori possibili.
        Il codice (essendo stupidissimo) è semplicissimo: https://github.com/TdP-2016/Scacchiera012/blob/master/src/it/polito/tdp/scacchiera/model/Ricerca.java

I commenti sono chiusi.