Today I was making an automated program to solve 8 Puzzle and when I am running the same logic in c++ it is working fine but in python it is going to near about 6000-6500 recursions and the recursion is not even working properly and I have no idea why ? Please help !
Note
Final state is
1 2 3
4 5 6
7 8 9
I am assuming blank space as 9 .
Python Code
# 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))
C++ Code
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector<vector<int> > goal(3 , vector<int>(3,0));
void print(vector<vector<int> > x){
int n = x.size();
int m = x[0].size();
for(int i = 0 ; i < n ; ++i)
for(int j = 0 ; j < m ; ++j)
cout<<x[i][j]<<" \n"[j==m-1];
}
bool compare(vector<vector<int> > a , vector<vector<int> > b){
bool ok = true;
for(int i = 0 ; i < 3 ; ++i)
for(int j = 0 ; j < 3 ; ++j)
if(a[i][j]!=b[i][j]){
ok = false;
}
return ok;
}
bool checkParity(vector<vector<int> > ans){
vector<int> x;
for(int i = 0 ; i < 3 ; ++i)
for(int j = 0 ; j < 3 ; ++j)
x.pb(ans[i][j]);
int cnt = 0;
for(int i = 0 ; i < 9 ; ++i)
for(int j = i ;j < 9 ; ++j)
if(x[i]!=9 and x[j]!=9 && x[i] > x[j])
cnt++;
if(cnt&1)
return false;
return true;
}
vector<vector<int> > generate(){
set<int> s = {1,2,3,4,5,6,7,8,9};
vector<vector<int> > ans(3 , vector<int>(3,0));;
srand(time(NULL));
for(int i = 0 ; i < 3 ; ++i){
for(int j = 0 ; j < 3 ; ++j){
while(1){
int x = rand()%9 + 1;
if(s.find(x)!=s.end()){
s.erase(x) , ans[i][j] = x;
break;
}
}
}
}
return ans;
}
vector<vector<int> > get(){
while(1){
vector<vector<int> > ans = generate();
if(checkParity(ans))
return ans;
}
}
map<vector<vector<int> > , bool > vis;
int xx[] = {1 , -1 , 0 , 0};
int yy[] = {0,0,-1,1};
int cnt = 0;
bool f = false;
void solve(vector<vector<int> > ans , int i , int j){
if(ans==goal){
cout<<"WE got it\n";
f = true;
return ;
}
cnt++;
// if(cnt > 100)
// return ;
vis[ans] = true;
/*cout<<"..................\n";
print(ans);
cout<<"..................\n";*/
//vector<vector<int> > cp = ans;
for(int k = 0 ; k < 4 ; ++k){
int ni = i + xx[k];
int nj = j + yy[k];
bool x = false;
vector<vector<int> > cp = ans;
if(ni >= 0 && nj >= 0 && ni < 3 && nj < 3){
swap(cp[i][j] , cp[ni][nj]);
x = true;
}
//cout<<vis[cp]<<endl;
if(x==true && vis[cp]==false && f==false){
//print(cp);
solve(cp , ni , nj);
}
}
return ;
}
int main(){
int cnt = 1;
for(int i = 0 ; i < 3 ; ++i)
for(int j = 0 ; j < 3 ; ++j)
goal[i][j] = cnt++;
vector<vector<int> > ls = goal;
ls = get();
//ls = goal;
print(ls);
print(goal);
cout<<compare(goal,ls)<<endl;
for(int i = 0 ; i < 3 ; ++i)
for(int j = 0 ; j < 3 ; ++j)
if(ls[i][j]==9)
solve(ls , i , j);
cout<<vis.size()<<endl;
cout<<vis[goal]<<endl;
}
Note2
I used ulimit to increase recursion depth for C++
Use Bootstrap recursion with PyPy2 in order to avoid recursion problems in Python. You can have at the # Pajenegod's Solution of recursion problems, he generally uses Bootstrap recursion Have a look at this link... https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py
But I think python should also do the job and I want to know why these errors happen in python .
I used recursion in python for the first time in life .
yeah..it can work with Python also but if you wanna speed up your program then you must use PyPy2. Generally, Python has inbuilt very small recursion limit (10**3) so, to increase it we generally write
sys.setrecursionlimit(10**7)I have increased it .
But it is still running for only near about 6500 .