Primi vicini

Innanzitutto, visto che tutti i numeri primi maggiori di 2 sono dispari, è chiaro che occorrerà alternare un numero pari e uno dispari, e che gli estremi dovranno essere due numeri dispari. Un possibile modo per trovare la soluzione è partire usando agli estremi le coppie (1,2) e (8,9), ottenendo 12...89. A questo punto si può provare a mettere il 3 dopo il 2; l'unica possibilità vicino all'8 diventa il 5, e da qui è facile arrivare alla soluzione 123476589.

Un'ultima parola

Se invece si fosse messo il 5 dopo il 2 si sarebbe avuta la soluzione simile 125674389. Sicuramente ci sono altre soluzioni, ma non ho avuto voglia di cercarle tutte...