Bruteforce su un puzzle

Il problema consiste nello scoprire quanti confronti dobbiamo fare (nel caso peggiore) se dobbiamo provare a risolvere un puzzle con il metodo del bruteforce.

Se dividiamo il puzzle nei suoi componenti atomici (i pezzi del puzzle),possiamo immaginare il puzzle come una griglia composta da tali componenti.

Quindi dividiamo l'immagine del puzzle secondo questa griglia e numeriamo ogni casella in modo progressivo a partire da 1.

Adesso consideriamo i seguenti predicati:

P(1)="Inserimento del pezzo nella casella 1"
P(2)="Inserimento del pezzo nella casella 2"
....
....
P(x)="Inserimento del pezzo nella casella x"

Dove x sono i pezzi del puzzle.

P(1) assume x*4 possibili valori distinti considerando che ogni pezzo può essere posizionato in 4 maniere diverse.
Possiamo notare,che scelto comunque un valore per P(1),P(2) assume 4*(x-1) valori distinti.
Scelto comunque un valore per P(1) e P(2),P(3) assume 4*(x-2) valori distinti.
...
...
Scelto comunque un valore per P(1),(P2),.....,(Px-1) P(x) assume 1 solo valore

Per il principio delle scelte multiple possiamo affermare quindi,che il numero totale di confronti nel caso peggiore è 4x*4(x-1)*4(x-2)*......*4 ovvero 4*x!.



Un altro metodo per arrivare allo stesso risultato è il seguente.
Numeriamo la griglia e i pezzi in modo progressivo a partire da 1.
Costruiamo 2 insiemi A,B costituiti dai primi x numeri naturali,dove A sono le caselle distinte e B sono i pezzi distinti.

A={1,2,3,......,x} caselle
B={1,2,3,......,x} pezzi

Se f è la funzione definita in A con valori in B che associa ad ogni casella uno ed un solo pezzo,il problema diventa trovare la funzione che associa ad ogni casella il pezzo giusto.

Possiamo supporre che la funzione che stiamo cercando sia la funzione identica.


Quindi
1->1
2->2
3->3
...
...
x->x

Adesso,numeriamo ogni coppia di elementi della funzione sempre in modo progressivo a partire da 1.

1->1 la numeriamo con 1
2->2 la numeriamo con 2
3->3 la numeriamo con 3
...
...
x->x numeriamo con x

Quello che abbiamo trovato,quindi,è la seguente disposizione dei numeri naturali

1,2,3,......,x

In sostanza l'unica disposizione corretta dei pezzi nel puzzle è quella rappresentata sopra.
Per sapere quante sono TUTTE le possibili disposizioni (quindi tutti i modi di mettere i pezzi nelle caselle) basta trovare una permutazione dei primi x numeri.
Le permutazioni di x numeri sono x!.
Se poi consideriamo che ogni pezzo può essere posizionato in 4 maniere differenti allora il numero diventa 4*x!

Per concludere,poichè x! cresce quasi quanto n^x,NON provate mai a fare bruteforce su un puzzle.
Già solo per 10 pezzi dovete fare 3.628.800 prove per avere la soluzione.