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 <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    int N; string S; cin >> N >> S;
    vector<int> hai(9);

    vector<vector<long long> > num(10, vector<long long>(10, 0));
    for (int i = 0; i + 1 < N; ++i) {
        int a = S[i] - '0';
        int b = S[i+1] - '0';
        num[a][b]++;
    }
    iota(hai.begin(), hai.end(), 1);

    long long mi = 1LL<<60;
    vector<int> mii;
    do {
        // Warshall-Floyd
        long long dp[10][10];
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < 10; ++j) {
                dp[i][j] = 1<<29;
            }
            dp[i][i] = 0;
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                int v = hai[i*3+j];
                for (int dir = 0; dir < 4; ++dir) {
                    int ni = i + dx[dir], nj = j + dy[dir];
                    if (ni < 0 || ni >= 3 || nj < 0 || nj >= 3) continue;
                    int w = hai[ni*3+nj];
                    dp[v][w] = dp[w][v] = 1;
                }
            }
        }
        for (int k = 0; k < 10; ++k)
            for (int i = 0; i < 10; ++i)
                for (int j = 0; j < 10; ++j) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                    //cout << i << ", " << j << ": " << dp[i][j] << endl;
                }

        long long res = 0;
        for (int i = 1; i < 10; ++i) {
            for (int j = 1; j < 10; ++j) {
                res += num[i][j] * dp[i][j];
            }
        }

        if (mi > res) {
            mi = res;
            mii = hai;
        }
                    
    } while (next_permutation(hai.begin(), hai.end()));

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) cout << mii[i*3+j];
        cout << endl;
    }
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

int di[9] = {0, 0, 0, 1, 1, 1, 2, 2, 2};
int dj[9] = {0, 1, 2, 0, 1, 2, 0, 1, 2};

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt[9][9] = {};
    for(int i = 1; i < s.length(); i++){
        int from = s[i-1]-'1', to = s[i]-'1';
        cnt[from][to]++;
        cnt[to][from]++;
    }
    vector<int> ans(9), arr(9);
    for(int i = 0; i < 9; i++)  arr[i] = i;
    int ma = 1<<30;
    do{
        int rev[9];
        for(int i = 0; i < 9; i++){
            rev[arr[i]] = i;
        }
        int tmp = 0;
        for(int i = 0; i < 9; i++){
            for(int j = i+1; j < 9; j++){
                int dist = abs(di[rev[i]]-di[rev[j]])+abs(dj[rev[i]]-dj[rev[j]]);
                tmp += dist * cnt[i][j];
            }
        }
        if(tmp < ma){
            ma = tmp;
            ans = arr;
        }
    }while(next_permutation(arr.begin(), arr.end()));
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cout << ans[i*3+j]+1;
        }
        cout << endl;
    }
    return 0;
}

C++: #include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	string s;
	cin >> s;
	vector<int>p(9);
	vector<vector<int>>num(10, vector<int>(10));
	for (int i = 1; i < s.size(); i++) {
		num[s[i] - '0'][s[i - 1] - '0']++;
	}
	for (int i = 0; i < 9; i++)p[i] = i + 1;
	vector<int>ans(9);
	for (auto &i : ans)i = MOD;
	int cost = MOD;
	do {
		vector<pair<int,int>>place(10);
		for (int i = 0; i < 9; i++) {
			place[p[i]] = { i / 3,i % 3 };
		}
		int box = 0;
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				box += (abs(place[i].first - place[j].first) + abs(place[i].second - place[j].second))*num[i][j];
			}
		}
		if (cost > box) {
			cost = box;
			ans = p;
		}
		else if (cost == box) {
			if (ans > p)ans = p;
		}
	} while (next_permutation(p.begin(), p.end()));
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cout << ans[i * 3 + j];
		}
		cout << endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a;i<b;i++)
using namespace std;
using ll=long long;
const ll LINF=0x1fffffffffffffff;



const vector<vector<ll>>dis={
    {0,1,2,1,2,3,2,3,4},
    {1,0,1,2,1,2,3,2,3},
    {2,1,0,3,2,1,4,3,2},
    {1,2,3,0,1,2,1,2,3},
    {2,1,2,1,0,1,2,1,2},
    {3,2,1,2,1,0,3,2,1},
    {2,3,4,1,2,3,0,1,2},
    {3,2,3,2,1,2,1,0,1},
    {4,3,2,3,2,1,2,1,0}
};
signed main(){
    ll n;
    string s;
    cin>>n>>s;
    vector<vector<ll>>cnt(9,vector<ll>(9));
    for(auto&&i:s)i-='1';
    rep(i,0,n-1)cnt[s[i]][s[i+1]]++;
    vector<ll>a={0,1,2,3,4,5,6,7,8},ans;
    ll max=LINF;
    do{
        vector<vector<ll>>cost(9,vector<ll>(9));
        ll c=0;
        rep(i,0,9)rep(j,0,9)c+=dis[i][j]*cnt[a[i]][a[j]];
        if(c<max){
            max=c;
            ans=a;
        }
    }while(next_permutation(a.begin(),a.end()));
    rep(i,0,3){
        rep(j,0,3)cout<<char(ans[i*3+j]+'1');
        cout<<endl;
    }
}