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).
3*2^12=12288?
L’unica cosa che cambierei: punto esclamativo invece dell’interrogativo :).
NB Il punto esclamativo nel senso di fattoriale, alla mia età, lo vedo ormai solo davanti a lettere, mai a numeri.
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 :)
ARGH volevo dire NON nel senso di fattoriale.
ah ecco! :)
@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.
Se ti interessa, ho preso questo quizzino come pretesto per una lezione sulla ricorsione (corso di Tecniche di Programmazione al Politecnico di Torino). Ovviamente siamo arrivati a contarne 12288 (anche se non abbiamo riflettuto sul perché… approccio brute-force).
Il sorgente Java è https://github.com/TdP-2016/Scacchiera012
Lo screencast della lezione è http://elite.polito.it/files/videos/03fyz-2016/TdP2016-lez15-2016-04-05.avi
(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…
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
ah, ok :-)