Go: package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	s := getNextString(scanner)
	cc := makeGrid(9, 9)
	for i := 0; i < n-1; i++ {
		cc[s[i]-'0'-1][s[i+1]-'0'-1]++
	}
	p := make(permutation, 9)
	ans := make([]int, 9)
	p.dfs(0, 9, 0, ans, cc)
	for i := 0; i < 9; i++ {
		fmt.Fprint(writer, ans[i]+1)
		if i%3 == 2 {
			fmt.Fprintln(writer, "")
		}
	}
}
func makeGrid(h, w int) [][]int {
	index := make([][]int, h, h)
	data := make([]int, h*w, h*w)
	for i := 0; i < h; i++ {
		index[i] = data[i*w : (i+1)*w]
	}
	return index
}

var min int = math.MaxInt32

type permutation []int

func (p permutation) dfs(i, n int, used uint32, ans []int, cc [][]int) {
	if i == n {
		sum := getsum(p, cc)
		if min > sum {
			for i := 0; i < 9; i++ {
				ans[i] = p[i]
			}
			min = sum
		}
		return
	}
	for b := 0; b < 9; b++ {
		if used&(1<<uint(b)) != 0 {
			continue
		}
		p[i] = b
		p.dfs(i+1, n, used|(1<<uint(b)), ans, cc)
	}
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func getsum(p permutation, cc [][]int) int {
	sum := 0
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if i == j {
				continue
			}
			sum += (abs(i/3-j/3) + abs(i%3-j%3)) * cc[p[i]][p[j]]
		}
	}
	return sum
}

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

#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<vector<int>> v(9,vector<int>(9,0));
  for(int i=0;i<n-1;i++){
    v[s[i]-'1'][s[i+1]-'1']++;
  }
  vector<int> p(9);
  vector<int> ans(9,-1);
  int val=IINF,tmp;
  for(int i=0;i<9;i++) p[i]=i;
  vector<int> x={0,0,0,1,1,1,2,2,2};
  vector<int> y={0,1,2,0,1,2,0,1,2};
  do {
    vector<int> pos(9);
    for(int i=0;i<9;i++) pos[p[i]]=i;
    tmp=0;
    for(int i=0;i<9;i++){
      for(int j=0;j<9;j++){
        tmp+=v[i][j]*(abs(x[pos[i]]-x[pos[j]])+abs(y[pos[i]]-y[pos[j]]));
      }
    }
    if(tmp<val){
      val=tmp;
      for(int i=0;i<9;i++){
        ans[i]=p[i];

      }
    }
  } while( next_permutation(p.begin(), p.end()) );     // 次の順列を生成
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cout << ans[3*i+j]+1;
    }
    cout << endl;
  }
  return 0;
}

C++: #include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

pair<int,string> v=make_pair(19191919,"1919");
string A="123456789";
char pat[114514];
int n,cnt[10][10];

int cal(string s){
    int a[3][3],x[10],y[10],sum=0;
    r(i,3){
        r(j,3){
            int p=(s[i*3+j]-'0');
            a[i][j]=p;
            x[p]=j;
            y[p]=i;
        }
    }
    r(i,10){
        r(j,10){
            int X=abs(x[i]-x[j]);
            int Y=abs(y[i]-y[j]);
            sum += (X+Y)*cnt[i][j];
        }
    }
    return sum;
}

int main(){
    scanf("%d%s",&n,pat);
    r(i,n-1){
        cnt[pat[i]-'0'][pat[i+1]-'0']++;
    }
    do{
        v=min(v,make_pair(cal(A),A));
    }while(next_permutation(A.begin(),A.end()));

    cout<<v.second.substr(0,3)<<endl;
    cout<<v.second.substr(3,3)<<endl;
    cout<<v.second.substr(6,3)<<endl;
}

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

int n;
string s;
int cnt[10][10] = {0};
int dis[10][10] = {0};
int answer[9] = {0};

void solve();

int main() {
  cin >> n >> s;
  for(int i = 1; i < n; ++i) {
    int a, b;
    a = s[i] - '1';
    b = s[i - 1] - '1';
    if(a > b) swap(a, b);
    ++cnt[a][b];
  }
  for(int i = 0; i < 10; ++i)
    for(int j = 0; j < 10; ++j) {
      int a, b;
      a = abs(i % 3 - j % 3);
      b = abs(i / 3 - j / 3);
      dis[i][j] = a + b;
    }
  solve();
  for(int i = 0; i < 9; ++i) {
    cout << answer[i] + 1;
    if(i % 3 == 2) cout << endl;
  }
  return 0;
}

void solve() {
  int ls[9] = {0};
  long long best = 1000000000000l;
  for(int i = 0; i < 9; ++i) ls[i] = i;
  do {
    int now = 0;
    for(int i = 0; i < 9; ++i)
      for(int j = i + 1; j < 9; ++j) {
        int mi = ls[i], ma = ls[j];
        if(mi > ma) swap(mi, ma);
        now += cnt[mi][ma] * dis[i][j];
      }
    if(best > now) {
      best = now;
      for(int i = 0; i < 9; ++i) answer[i] = ls[i];
    }
  } while(next_permutation(ls, ls + 9));
}

C++: #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int num[10][10] = {};
    rep(i,n-1)num[s[i]-'0'][s[i+1]-'0']++;
    vi v(9);
    rep(i,9)v[i] = i+1;
    vector<vi> ans(3,vi(3));
    int sum = LINF;
    do{
        int t = 0;
        rep(i,9)rep(j,9){
            int xa = i/3, ya = i%3;
            int xb = j/3, yb = j%3;
            t += num[v[i]][v[j]] * (abs(xa-xb) + abs(ya-yb));
        }
        if(t < sum){
            sum = t;
            rep(i,3)rep(j,3)ans[i][j] = v[i*3+j];
        }
    }while(next_permutation(all(v)));
    rep(i,3){
        rep(j,3)cout << ans[i][j];
        cout << endl;
    }
}

C++: #include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7;
const ll LINF=1e18;
using namespace std;
#define int long long
//template
int d[10][10];
//main
signed main(){
  int N;string s;cin>>N>>s;
  std::vector<int> ans(9);
  memset(d,0,sizeof(d));
  for(int i=1;i<N;i++)d[s[i-1]-'0'][s[i]-'0']++;
  std::vector<int> v(9);
  for(int i=0;i<9;i++)v[i]=i+1;
  int mi=1e9;
  do{
    int res=0;
    for(int i=0;i<9;i++){
      for(int j=0;j<9;j++){
        res+=(abs(i/3-j/3)+abs(i%3-j%3))*d[v[i]][v[j]];
      }
    }
    if(res<mi){
      mi=res;
      for(int i=0;i<9;i++)ans[i]=v[i];
    }
  }while (std::next_permutation(v.begin(), v.end()));
  for(int i=0;i<9;i++){
    cout<<ans[i];
    if(i%3==2)cout<<endl;
  }
  /*
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++)cout<<d[i][j]<<" ";
    cout<<endl;
  }
  */
}