#include using namespace std; struct wrapper { int arr[3][3]; int used[10]; }; int global_match_val = 1000000; int check_valid(int arr[][3] ,int cost) { for ( int i = 0;i<3;i++) { if ( ( arr[i][0]+ arr[i][1]+arr[i][2] ) != 15 ) return 0; } for ( int i = 0;i<3;i++) { if ( ( arr[0][i]+ arr[1][i]+arr[2][i] ) != 15 ) return 0; } if ( (arr[0][0]+arr[1][1]+arr[2][2]) != 15 ) return 0 ; if ( (arr[0][2]+arr[1][1]+arr[2][0]) != 15 ) return 0 ; if ( global_match_val > cost ) global_match_val = cost; return 1; } int check (wrapper wr , int row , int col , int cost) { int cost_min = 0 , temp_cost,temp_u,temp_a,cost_l; if ( cost > global_match_val ) return 0; if ( check_valid(wr.arr,cost) ) return cost; else { col++; if ( col >= 3 ) { row++ ;col = 0 ; } if ( row >= 3 ) return 0; for ( int i = 1 ; i<= 9 ; i++ ) { if ( wr.used[i] != 0 ) { temp_u = wr.used[i] ; temp_a = wr.arr[row][col]; cost_l = abs(wr.arr[row][col] - wr.used[i]); wr.arr[row][col] = wr.used[i]; wr.used[i] = 0 ; temp_cost = check(wr,row,col,cost+cost_l) ; if ( cost_min == 0 ) cost_min = temp_cost; else if ( temp_cost < cost_min ) cost_min = temp_cost ; // restore wr.arr[row][col] = temp_a ; wr.used[i] = temp_u; } } return cost_min; } } wrapper wr; int main() { int ans; for ( int i = 0;i<3;i++) { for ( int j = 0;j<3;j++) { cin>>wr.arr[i][j]; } } for (int i = 1 ; i<10; i++) wr.used[i] = i ; ans = check (wr,0,-1 ,0); cout <