Il puzzle delle scimmie, nella sua versione classica, consiste in un gioco a nove carte quadrate, sui cui lati sono stampate le metà superiori e inferiori di scimmie colorate. Lo scopo è quello di costruire un quadrato 3*3 dove forme e colori delle scimmie combacino perfettamente.
Da un punto di vista umano il problema non è tra i più difficili, ma guardando all'aspetto algoritmico si possono fare alcune considerazioni interessanti.
Nel peggiore dei casi dovremmo analizzare 9! = 9*8*7*...*2*1 = 362.880 possibilità: ci sono infatti nove modi possibili per scegliere la prima carta, otto per la seconda, sette per la terza, e così via.
Se disponessimo di un computer in grado di controllare un miliardo di ordinamenti al secondo (supposizione ragionevole), il problema precedente verrebbe risolto in circa 0,36 millisecondi.
Ma la dimensione fattoriale cresce in modo esorbitante. Se il puzzle delle scimmie fosse costituito da 16 carte (quadrato 4*4) i tempi di calcolo sarebbero di quasi sei ore; con 25 carte (quadrato 5*5), invece, ci vorrebbero quasi 492 milioni di anni. Solo per curiosità: con 36 carte i tempi di calcolo supererebbero l'attuale età dell'universo.
