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>

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
std::string S;
int cnt[10][10];

int manhattan(P p, P q){
    int x1, y1, x2, y2;
    std::tie(x1, y1) = p;
    std::tie(x2, y2) = q;

    return std::abs(x1 - x2) + std::abs(y1 - y2);
}

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

    std::cin >> N >> S;

    for(int i=0;i+1<N;++i){
        cnt[S[i] - '0'][S[i+1] - '0'] += 1;
    }

    std::vector<int> order(9);
    std::iota(order.begin(), order.end(), 1);

    int minCost = 1001001001;
    std::vector<int> eff;

    while(true){
        std::vector<P> ps(10);
        for(int i=0;i<9;++i){
            ps[order[i]] = std::make_tuple(i / 3, i % 3);
        }

        int cost = 0;
        for(int i=1;i<=9;++i){
            for(int j=1;j<=9;++j){
                cost += manhattan(ps[i], ps[j]) * cnt[i][j];
            }
        }

        if(cost < minCost){
            minCost = cost;
            eff = order;
        }

        unless(std::next_permutation(order.begin(), order.end())){
            break;
        }
    }

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

C++: #include <bits/stdc++.h>
using namespace std;
#define DEBUG_MODE
#define endl '\n'
#ifdef DEBUG_MODE
#define DEBUG(X) debug_func(X, #X)
#define DEBUG_ENDL endl
#define DEBUG_SEPARATOR_LINE cout<<"=================\n"
#else
#define DEBUG(X) 0
#define DEBUG_ENDL 0
#define DEBUG_SEPARATOR_LINE 0
#endif
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
#define DEBUG_ENDL_S(S) ((S).size() ? "\n" : "")
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
void debug_func_preffix(const string &s) { if(s.size()) cout << s << " = "; }
template <typename T>
void debug_func(const T &t, const string &s = "") {
    debug_func_preffix(s);
    cout << t << DEBUG_ENDL_S(s);
}
template <typename T, typename U>
void debug_func(const P<T, U> &p, const string &s = "") {
    debug_func_preffix(s);
    cout << "(";
    debug_func(p.first);
    cout << ", ";
    debug_func(p.second);
    cout << ")" << DEBUG_ENDL_S(s);
}
template <typename T>
void debug_func(const V<T> &v, const string &s = "") {
    for(ll i = 0; i < v.size(); i++) {
        string t = s + "[" + to_string(i) + "]";
        debug_func(v[i], t);
    }
}

VV<ll> cnt(9, V<ll>(9, 0));

ll calc(const V<ll> &p) {
    V<PLL> coors(9);
    for(ll i = 0; i < 3; i++) for(ll j = 0; j < 3; j++) coors[p[3 * i + j]] = PLL(i, j);
    ll ret = 0;
    for(ll i = 0; i < 9; i++) for(ll j = 0; j < 9; j++) {
        ll d = abs(coors[i].first - coors[j].first) + abs(coors[i].second - coors[j].second); 
        ret += d * cnt[i][j];
    }
    return ret;
}

int main() {
    V<ll> nums(9);
    iota(ALL(nums), 0ll);
    ll N;
    cin >> N;
    string S;
    cin >> S;
    for(ll i = 0; i < N - 1; i++) cnt[S[i] - '1'][S[i + 1] - '1']++;
    V<ll> ans = nums;
    ll mcnt = 5e15;
    do {
        ll tmp = calc(nums);
        if(tmp < mcnt) {
            mcnt = tmp;
            ans = nums;
        }
    } while(next_permutation(ALL(nums)));
    for(ll i = 0; i < 3; i++) for(ll j = 0; j < 3; j++) {
        cout << ans[3 * i + j] + 1;
        if(j + 1 == 3) cout << endl;
    }
    return 0;
}