Ora pero' siete all'Universita' e state studiando Informatica... perche' non scrivere un programma che fa questo sporco lavoro per voi, cosi' potrete seguire le lezioni di Programmazione 1 a mente sgombra, senza chiedervi quale sia la strategia migliore per riempire quel maledetto quadrato! Si tratta di costruire un programma che legge un input un intero n e cerca di riempire il quadrato n x n seguendo la regola sopra descritta. La strategia da utilizzare va sotto il nome di backtrack: semplicemente si comincia a mettere il numero 1 in una posizione arbitraria e poi il 2 e cosi' via. Quando ci si accorge che non si puo' andare avanti (e non si e' raggiunta una soluzione), si torna all'ultimo punto in cui avevate una scelta per fare l'ultima mossa e si prova con la mossa successiva (SUGGERIMENTO: date un ordine alle 8 possibili mosse). La struttura generale delle procedure di backtrack, puo' essere vista nel programma che risolve il problema delle 8 regine (visto a lezione e riportato qui sotto nella pagina: a voi interessa la procedura1 16 6 23 13 8 21 3 9 20 5 24 12 17 25 2 15 7 22 14 11 18 4 10 19
tenta(int, int [])). Il quadrato 5x5 mostrato sopra e' stato ottenuto con un programmino. Per avere un'intuizione di come funziona il backtrack, sotto potete trovare la sequenza di punti in cui il programma ha dovuto tornare indietro, perche' aveva imboccato una strada che non portava alla soluzione (ATTENZIONE: il vostro output dovra' generare SOLO la matrice con la soluzione migliore trovata). Per valori sufficienti bassi (ad esempio 4) il problema non ha soluzione: in questo caso il vostro programma dovra' fornire in output la migliore soluzione trovata, cioe' la matrice con la sequenza piu' lunga. (Nel caso di un quadrato 4x4 si puo' arrivare a infilare 8 numeri nella matrice... come si fa?). Evitate di provare per valori troppo alti... gia' 10 potrebbe impegnare il vostro computer per ore... Se il vostro programma e' strutturato bene, una semplice modifica (cambiare la procedura che sceglie la prossima mossa da fare) potrebbe permettervi di risolve un altro celeberrimo gioco legato al mondo degli scacchi: passare su tutte le caselle di una scacchiera una sola volta muovendosi come un cavallo...
I | Attachment | History | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|---|
txt | Esempio.Bactrack.txt | r1 | manage | 0.5 K | 2003-12-11 - 18:03 | IvanoSalvo | |
c | ottoReg.c | r2 r1 | manage | 3.2 K | 2003-12-11 - 18:04 | IvanoSalvo |
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica |
|