The Prime Grid Game

Me divertí resolviendo esto, así que ofrezco este desafío de golf.

El objetivo de este golf es encontrar el número primo más grande que se pueda construir usando las instrucciones dadas.

Debe aceptar una cuadrícula de 3x3 de un solo dígito como entrada. (Depende de usted cómo quiere hacer eso, pero especifique eso en su programa).

Puede moverse a lo largo de la cuadrícula ortogonalmente (izquierda, derecha, arriba o abajo) y, a medida que avanza, sigue agregando los dígitos por los que camina.

P.ej

1 2 3
3 5 6 
1 8 9

Digamos que comenzamos en 1, podemos formar el número 1236589 pero no podemos formar 15.

Tienes que evaluar cada posición inicial.

Si no se puede encontrar una prima, imprima -1, de lo contrario imprima la propia prima.

El código más corto gana, asegúrese de que se ejecute en 10 segundos.

¡Que te diviertas!

Editar: Use una posición exactamente una vez, en el número completo.

Aquí hay un caso de prueba

Entrada:

1 2 3
4 5 6
7 8 9

Salida: 69854123

Haskell, 239 caracteres

p=2:q[3..]
q=filter(#p)
n#(x:y)=n==x||n`mod`x/=0&&(n`div`x<x||n#y)
(n§m)q=n:maybe[](\i->[q-4,q-1,q+1,q+4]>>=(n*10+i)§filter(/=(q,i))m)(lookup q m)
i=[0,1,2,4,5,6,8,9,10]
main=getLine>>=print.maximum.(-1:).q.(i>>=).(0§).zip i.map read.words

La entrada se da como una sola línea de nueve números:

$> echo 1 2 3  3 5 6  1 8 9 | runhaskell 2485-PrimeGrid.hs
81356321
$> echo 1 2 3  4 5 6  7 8 9 | runhaskell 2485-PrimeGrid.hs
69854123
$> echo 1 1 1  1 1 1  1 1 1 | runhaskell 2485-PrimeGrid.hs
11
$> echo 2 2 2  2 2 2  2 2 2 | runhaskell 2485-PrimeGrid.hs
2
$> echo 4 4 4  4 4 4  4 4 4 | runhaskell 2485-PrimeGrid.hs
-1

Python, 286 274 caracteres

I=lambda:raw_input().split()
m=['']
G=m*4+I()+m+I()+m+I()+m*4
def B(s,p):
 d=G[p]
 if''==d:return-1
 G[p]='';s+=d;n=int(s)
 r=max(n if n>1and all(n%i for i in range(2,n**.5+1))else-1,B(s,p-4),B(s,p+4),B(s,p-1),B(s,p+1))
 G[p]=d;return r
print max(B('',i)for i in range(15))

Esto da una advertencia de desaprobación para el argumento float range. Ignóralo o gasta 5 caracteres más para envolverlo int().