[Python] Ayuda con "Runtime error"

[nacho87]

Hola a todos!

Estoy haciendo un pequeño programa en python para resolver éste problema: http://juegos.microsiervos.com/matematicas/17-por-17.html

Bueno, la verdad es que no pretendo resolverlo ya que es bastante dificil pero estoy aprendiendo bastante creando un programa que lo intente. En resumen el problema trata de crear una matriz 17x17 en la que con 4 colores distintos (números) no se formen "rectángulos virtuales", es decir, que no haya los mismos 4 números en formando las esquinas de ningún rectángulo en la matriz.

Por ahora con mi programa consigo si problema hasta las de 11x11, sin embargo al pasar a las 12x12 python me da un error pasado un rato que no se cómo evitar. El code de mi programa es el siguiente:

Código (python) [Seleccionar] Expandir

#!/usr/bin/python

import numpy
from random import uniform
import os
import sys
m = int(sys.argv[1])
matriz = numpy.zeros((m,m), dtype="int")
x = 0
y = 0
uno = 0
dos = 0
tres = 0
cuatro = 0
count = 0
error = 0
def check(num,x,y):
column = []
#print "x=%s,y=%s" % (x,y)
for col in range(0,x):
if num == matriz[col][y]:
column.append(col)
#print "colision de columna en %s %s con numero %s" % (col,y,num)
if col == x - 1:
return column

def check2(num,x,y):
fila = []
#print "x=%s,y=%s" % (x,y)
for fil in range(0,y):
if num == matriz[x][fil]:
#print "colision de fila en %s %s con numero %s" % (x,fil,num)
fila.append(fil)
if fil == y - 1:
return fila




def colision(nam,x,y):
i=0
j=0
if x==0 or y==0:
return 1
micol = check(nam,x,y)
mifil = check2(nam,x,y)
#print micol
#print mifil
if micol == None:
return 1
elif mifil == None:
return 1
else:
for i in micol:
for j in mifil:
if matriz[i][j] == nam:
#print "colision de diagonal en %s %s con numero %s" % (i,j,nam)
return 0
return 1


def fix(nam,x,y,countck):
i=0
j=0
micol = check(nam,x,y)
mifil = check2(nam,x,y)
for i in micol:
for j in mifil:
if matriz[i][j] == nam:
mynewnum = int(uniform(1,5))
while mynewnum == nam:
mynewnum = int(uniform(1,5))
if countck > 20 and countck < 40:
countck = 0
matriz[i][j] = mynewnum
elif countck >= 40:
countck = 0
matriz[x][j] = mynewnum
else:
matriz[i][y] = mynewnum
#print "cambio (%s,%s) por %s porque colisiona con (%s,%s)" % (i,y,mynewnum,i,j)
def checkear(countck):
x = 1
y = 1
while True:
if colision(matriz[x][y],x,y) == 0:
print "matriz con errores en (%s,%s)" % (x,y)
countck += 1
fix(matriz[x][y],x,y,countck)
os.system('clear')
print "\n"*8 + str(matriz)
print countck
checkear(countck)
else:
if x == m - 1:
if y == m - 1:
print "matriz sin errores"
exit()
x = -1
y += 1
x += 1





while True:
mynum = int(uniform(1,5))
if colision(mynum,x,y) != 0:
matriz[x][y] = mynum
if mynum == 1:
uno +=1
elif mynum == 2:
dos +=1
elif mynum == 3:
tres +=1
elif mynum == 4:
cuatro +=1
#print "x = " + str(x)
#print "y = " + str(y)
os.system('clear')
print "\n"*8 + str(matriz)
print "errores: %s" % error
print "hay %s unos, %s doses, %s treses y %s cuatros" % (uno,dos,tres,cuatro)
if x == m - 1:
if y == m - 1:
checkear(countck = 0)
x = -1
y += 1
x += 1
count = 0
else:
count += 1
if count == 15:
fix(mynum,x,y,0)
matriz[x][y] = mynum
error += 1
os.system('clear')
print "\n"*8 + str(matriz)
print "errores: %s" % error
print "hay %s unos, %s doses, %s treses y %s cuatros" % (uno,dos,tres,cuatro)
if x == m - 1:
if y == m - 1:
checkear(countck = 0)
x = -1
y += 1
x += 1
count = 0


Hay partes que están comentadas ya que las usaba para "debugear" el programa ya que lo estoy haciendo con gedit y necesitaba alguna forma de ver donde fallaba.

La cuestión es que al intentar conseguir una matriz 12x12, algo antes de llegar a las 1000 ejecuciones de la función chequear() me lanza el siguiente error:

Código [Seleccionar] Expandir

Exception RuntimeError:'maximum recursion depth exceeded while calling a Python object' in <type 'exceptions.AttributeError'> ignored

El código es un poco caótico ya que lo fui haciendo sobre la marcha y no tengo mucha idea de programar pero por mucho que lo reviso no encuentro la forma de evitar el error. Espero que me podais ayudar.

Un saludo!!

[pucheto]

El error es bastante claro...
Las recursiones no son infinitas... sino q las podes hacer hasta llenar el stack... si lo llenas... stack overflow...

En este caso... como es una matriz grande... y llamas a checkear muchas veces es muy probable q llegues al limite del stack... cuando eran mas chicas te alcanzaba....

Proba usando stackless python o no usando recursion...

[nacho87]

Gracias por la respuesta.

Con matrices más pequeñas(10x10 por ejemplo) encuantra la solución antes de saltar el error. Sin embargo con la de 11x11 hay veces que no la encuentra y el error salta en el mismo punto, poco antes de las 1000 recursiones.

He intentado cambiar el código para no usar la recursión en checkear() pero no se me ocurre como...

También he estado mirando lo del stackless. He probado pypy-stackless pero no consigo importar numpy, que lo uso para crear la matriz inicial.

Saludos!