# The Problem is in solve function
import sys
import random
sys.setrecursionlimit(250000)
goal = [[1,2,3] , [4 , 5 , 6] , [7,8,9]]
def check(ls):
cnt = 0
cl = list()
for i in range(0,3):
for j in range(0,3):
cl.append(ls[i][j])
for i in range(0,9):
for j in range(i,9):
if(cl[i] > cl[j]):
cnt = cnt + 1
if cnt%2==0:
return True
return False
def generate():
s = set()
for i in range(1 , 10):
s.add(i)
ls = goal.copy()
for i in range(0,3):
for j in range(0,3):
while True:
x = random.randint(1,10)
if x in s:
ls[i][j] = x
s.remove(x)
break
return ls
def get():
while True:
ls = generate()
if check(ls)==True:
return ls
xx = [1 , -1 , 0 , 0]
yy = [0 , 0 , -1 , 1]
def make_tuple(ls):
list = []
for i in range(0,3):
for j in range(0,3):
list.append(ls[i][j])
return tuple(list)
cnt = False
def solve(ls , i , j , visited):
global cnt
if ls==goal:
print("we have a solution")
cnt = True
return
for k in range (0,3):
for l in range(0,3):
print(ls[k][l] , end = " ")
print()
print('------------')
#return None
visited[make_tuple(ls)] = True
for k in range(0,4):
ni = (i + int(xx[k]))
nj = (j + int(yy[k]))
cp = list(ls)
x = False
if(ni >= 0 and nj >= 0 and ni < 3 and nj < 3):
cp[ni][nj] , cp[i][j] = cp[i][j] , cp[ni][nj]
x = True
if (x==True and cnt==False and (make_tuple(cp) not in visited)):
solve(cp , ni , nj , visited)
ls = get()
print(ls)
goal = [[1,2,3] , [4 , 5 , 6] , [7,8,9]]
print(goal)
print(ls)
for i in range(0,3):
for j in range(0,3):
if(ls[i][j]==9):
visited = {}
solve(ls.copy() , i , j , visited)
if cnt == False:
print("unable to solve")
print(cnt)
print(len(visited))
sys.exit()
if cnt==True:
print("Ohh We did it!")
print(ls)
print(goal)
print(cnt)
print(len(visited))
