Pedine in ordine sparso

[giobimbo]

Abbiamo una scacchiera 8x8 e 28 pedine così numerate:
sette col numero 7,
sei col numero 6,
...,
due col numero 2,
una col numero 1.
Vogliamo disporre tali pedine in modo da avere una fila orizzontale e una verticale con sette pedine, una fila orizzontale e una verticale con sei pedine, ..., una fila orizzontale e una verticale con una pedina. Sulle caselle della diagonale principale, quella che inizia con la prima casella in alto a sinistra e termina con l'ultima casella in basso a destra, invece non ne vanno messe.
Per pedine in fila si intendono pedine che stanno in una fila di otto caselle, tra una pedina e l'altra possono esserci delle caselle vuote.

Problema 1. Disporre le pedine in modo che in ogni fila orizzontale e verticale i numeri siano tutti diversi.
Problema 2. Come nel problema 1 ma, in più, anche le diagonali parallele alla diagonale principale devono contenere pedine con numeri tutti diversi.

[franco]

Io la vedo così:

[jepa]

mmm,ma nel secondo problema non dovremmo avere comunque una fila orizzontale e una verticale con sette numeri?? e così di 6, 5 4 3 etc.?

[franco]

Hai ragione; la fretta è una cattiva consigliera!

Ho fatto un pasticcio colossale e chiedo venia.

[giobimbo]

Ehhh, colossale... diciamo che a forza di far girare le pedine il cervello affaticato ti ha fatto uno scherzo. Giusta comunque la soluzione del primo problema.

Mi domando se Franco o qualcun altro riesce a trovare altre soluzioni del primo problema: siccome uso un certo metodo costruttivo vorrei vedere se salta fuori qualche disposizione che non segue tale metodo.

[Pasquale]

Scusa Giò, dovresti specificare in che modo vanno numerate le pedine e mi spiego:

se le numero da 1 a 28, i numeri sono tutti diversi, ma penso che non sia questo il caso;
se in una riga, o colonna ci sono 7 pedine, queste devono essere numerate da 1 a 7, senza saltare alcun numero (cioè non può esistere il numero 8 ) ?
se sono 6, devono essere numerate con i numeri da 1 a 6, o sono ammessi altri sistemi (ad esempio da 2 a 7) ?
se sono 5, può esistere la sequenza di numerazione 2,3,5,6,7 (cioè saltando 1 e 4) ?
Una sola pedina può essere numerata solo con il numero 1 ?

[giobimbo]

@Pasquale

Indicando con un numero le pedine che hanno quel numero le 28 pedine sono:
7 7 7 7 7 7 7
6 6 6 6 6 6
5 5 5 5 5
4 4 4 4
3 3 3
2 2
1

Ora, per fare una fila da sette pedine con numeri tutti diversi che pedine ci metterai? 1 2 3 4 5 6 7 immagino, anche se non in quest'ordine, al che rimangono le 21 pedine:
7 7 7 7 7 7
6 6 6 6 6
5 5 5 5
4 4 4
3 3
2

Ora, dovendo formare un fila di sei pedine con numeri tutti diversi, che pedine ci metterai? 2 3 4 5 6 7 immagino, anche se non in quest'ordine, al che rimangono le 15 pedine:
7 7 7 7 7
6 6 6 6
5 5 5
4 4
3

Eccetera. Quando arriverai alla fila da una sola pedina che numero ti rimarrà disponibile?

[Pasquale]

OK, scusa, avevo semplicemente dimenticato la premessa (mi pare grave).

[giobimbo]

In attesa che Pasquale scriva un programma che trovi tutte le 20.000 soluzioni del problema 1, per chi si usa carta e matita ecco un aiuto sotto forma di un esempio, una soluzione su scacchiera 5x5:

0...2...0...3...4
0...0...0...0...0
4...1...0...2...3
0...4...0...0...0
0...3...0...4...0

Non so se qualcuno l'ha notato, ma la soluzione trovata da Franco ha un valore che va al di là del fatto di essere una semplice soluzione, essa ci dice che per qualsiasi scacchiera nxn esiste una disposizione di pedine che soddisfa i requisiti del problema 1.

[franco]

Però su questa soluzione 5x5 ci sono due 4 sulla stessa diagonale ed anche due 2.

O sono io che avevo capito male i termini del secondo quesito?

[Pasquale]

No Giò, al momento non ho tempo di fare quello che dici, anche se ogni occasione di mettere mano al Decimal, a titolo di allenamento, non è motivo di dispiacere.

[giobimbo]

Hai capito benissimo, Franco, solo che nel mio ultimo intervento parlavo del primo quesito, di cui m'interessa comunque una soluzione diversa dalla tua, come scritto anche in precedenza. Ho messo giù l'esempio in fretta e siccome son più facili da costruire mi è venuto così.


Se stai ancora lavorando sul problema 2 ecco un esempio, se può aiutarti:

0...3...0...4...0
0...0...0...0...0
3...1...0...2...4
0...4...0...0...0
4...2...0...3...0

Mentre del problema 1 so già quasi tutto, una dimostrazione della risolubilità del problema 2 per scacchiere di qualsiasi dimensione sarebbe più che benvenuta.

[Sancho Panza]

Ciao Giobimbo,
ecco una possibile soluzione per il 2° problema:

(risulta facile generalizzarla, nota il valore modulo 3 sulle diagonali di tipo "/",
ora non ho tempo per maggiori spiegazioni;
siccome dubito di riuscire ad accedere di nuovo al forum prima di Pasqua, anticipo a tutti gli auguri di felice Pasqua)

[giobimbo]

L'idea è interessante, la valuterò in questi giorni, ma purtroppo la soluzione non è valida in quanto ci sono delle pedine nella diagonale principale, che invece dovrebbe essere vuota.

[Pasquale]

Insomma....cambiando i numeri di Sancho con il loro complemento ad 8, rientreremmo meglio nelle specifiche generali del problema e, per quanto riguarda il problema2, la soluzione è valida per le diagonali perpendicolari a quelle richieste.
Per quanto riguarda le proprietà della diagonale principale, penso che siano sfuggite all'attenzione, considerata la fretta.

Per quanto mi riguarda, inserisco qui di seguito una tabella 8x8, che soddisfa solo il problema1, ed una da 6x6 che soddisfa anche il problema2 (il per la scacchiera 8x8 mi sembra un pochino più tosto e quindi staremo a vedere):




Preciso, che la scacchiera 8x8 è stata realizzata a mano, mentre quella 6x6 con il computer, che è troppo lento per poter affrontare quella da 8x8, rispetto anche allo stupido algoritmo buttato giù velocemente, tanto per vedere dove andava a parare la questione ed a titolo di esercitazione.