Final state is
1 2 3
4 5 6
7 8 9
I am assuming blank space as 9 .

# 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))

#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;
}

I used ulimit to increase recursion depth for C++