この問題はBFSにより解くことができます。
グリッドの数字の並びを状態とします。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	vector<int>a(8);
	for(int i=0;i<8;i++)cin >> a[i];

	map<vector<int>,int>memo;
	queue<vector<int>>q;
	memo[a]=0;
	q.push(a);
	while(!q.empty()){
		vector<int>a=q.front();
		q.pop();
		int crr=memo[a];
		//左右swap
		for(int i=0;i<7;i++){
			if(i==3)continue;
			swap(a[i],a[i+1]);
			if(memo.find(a)==memo.end()){
				memo[a]=crr+1;
				q.push(a);
			}
			swap(a[i],a[i+1]);
		}
		//上下swap
		for(int i=0;i<4;i++){
			swap(a[i],a[i+4]);
			if(memo.find(a)==memo.end()){
				memo[a]=crr+1;
				q.push(a);
			}
			swap(a[i],a[i+4]);
		}
	}

	cout << memo[{1,2,3,4,5,6,7,8}] << endl;
}

実装例(Python)

a=list(map(int,input().split()))+list(map(int,input().split()))

memo={}
q=[]
memo[tuple(a)]=0
q.append(tuple(a))
for a in q:
  crr=memo[a]
  a=list(a)
  # 左右swap
  for i in range(7):
    if i==3: continue
    a[i],a[i+1]=a[i+1],a[i]
    if tuple(a) not in memo:
      memo[tuple(a)]=crr+1
      q.append(tuple(a))
    a[i],a[i+1]=a[i+1],a[i]
  # 上下swap
  for i in range(4):
    a[i],a[i+4]=a[i+4],a[i]
    if tuple(a) not in memo:
      memo[tuple(a)]=crr+1
      q.append(tuple(a))
    a[i],a[i+4]=a[i+4],a[i]

print(memo[(1,2,3,4,5,6,7,8)])