HomeWork6 < Programmazione1/AA0506/PZ

Tags: view all tags

---++ Homework 6 - Nelle ore di Filosofia (o Diritto...)

Vedi anche: DomandeHomework6, SoluzioneHomework6, RisultatiHomework6.
----
%TOC%
----

Tutti gli studenti delle superiori, annoiandosi a morte durante lunghe spiegazioni, hanno almeno
una volta preso un foglio a quadretti, disegnato un quadrato (di norma 10x10) e hanno cominciato a 
riempirlo di numeretti, 1, 2, 3 e cosi' via, sperando almeno una volta di arrivare a 100 (a questo ci sono arrivati 
solo pochi fortunati... o qualche genietto), seguendo
la seguente regola: ci si puo' spostare in orizzontale o verticale lasciando libere due caselle e in diagonale lasciando libera una casella. Eccovi un esempio (fortunato, o abile!) di un quadrato 5x5.

<pre style="background:lightblue">
<verbatim>
  1 16  6 23 13
  8 21  3  9 20
  5 24 12 17 25
  2 15  7 22 14
 11 18  4 10 19
</verbatim>
</pre> 

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 procedura 

<verbatim>
tenta(int, int [])
</verbatim>
).

   * [[%ATTACHURL%/ottoReg.c][ottoReg.c]]: 

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).

   * [[%ATTACHURL%/Esempio.Bactrack.txt][Bactrack.txt]]: 

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...

---+++ Scadenza
L'esercizio va consegnato entro la mezzanotte di *domenica 21 Dicembre* .

%INCLUDE{"WebHome"}%

-- Users.IvanoSalvo - 12 Dic 2003

   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group