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;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;


signed main(){
    int n;
    string s;
    cin >> n >> s;

    // n = 1 のコーナーケースに気をつける


    vector<vector<int>> c(9, vector<int>(9, 0));
    for(int i = 0; i < n - 1; ++i)
        ++c[s[i] - '1'][s[i + 1] - '1'];

    vector<int> t(9, 0);
    iota(t.begin(), t.end(), 0);
    vector<int> ans_v = t;
    i64 ans = INF;
    do{
        i64 sum = 0;
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                int x = t[i];
                int y = t[j];

                int i_x = i % 3;
                int i_y = i / 3;
                int j_x = j % 3;
                int j_y = j / 3;
                int cost = abs(i_x - j_x) + abs(i_y - j_y);
                sum += cost * c[x][y];
            }
        }
        if(ans > sum){
            ans = sum;
            ans_v = t;
        }
    }while(next_permutation(t.begin(), t.end()));

    for(int i = 0; i < 9; ++i){
        cout << ans_v[i] + 1;
        if(i % 3 == 2)
            cout << endl;
    }

                       /*
    // dp[i]: iの集合まで見た時のほげ
    vector<vector<int>> dp(1 << 9, vector<int>(9, MOD));
    vector<vector<vector<int>>> v(1 << 9, vector<vector<int>>(9));

    for(int i = 0; i < n; ++i){
        dp[1 << i][i] = 0;
        v[1 << i][i].emplace_back(i);
    }
    for(int i = 0; i < (1 << 9); ++i){
        for(int j = 0; j < 9; ++j)
            for(int k = 0; k < 9; ++k)
                // 遷移できる
                if(~i & (1 << k)){
                    int bef = dp[i | (1 << k)][k];
                    int aft = dp[i][j] + c[j][k];
                    if(bef > aft){
                        dp[i | (1 << k)][k] = aft;
                        auto vv = v[i][j];
                        vv.emplace_back(k);
                        v[i | (1 << k)][k] = vv;
                    }
                    if(bef == aft){
                        auto vv = v[i][j];
                        vv.emplace_back(k);
                        v[i | (1 << k)][k] = min(v[i | (1 << k)][k], vv);
                    }
                }
    }
    pair<int,vector<int>> ans(dp.back()[0], v.back()[0]);
    for(int i = 1; i < 9; ++i){
        ans = min(ans, make_pair(dp.back()[i], v.back()[i]));
    }
                       */
}

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

int main() {
    int n;
    string s;
    cin >> n >> s;
    map<pair<int, int>, int> cnt;
    for (int i = 0; i < n - 1; i++) {
        int a = s[i] - '0', b = s[i + 1] - '0';
        cnt[{a, b}]++;
    }

    int nin = 1e9;
    vector<int> best;
    vector<int> pm(9);
    iota(pm.begin(), pm.end(), 1);

    do {
        int tmp = 0;
        pair<int, int> pos[10];
        for (int i = 1; i < 10; i++) {
            pos[pm[i - 1]] = {(i - 1) / 3, (i - 1) % 3};
        }
        for (auto& p : cnt) {
            int dist = abs(pos[p.first.first].first - pos[p.first.second].first) + abs(pos[p.first.first].second - pos[p.first.second].second);
            tmp += dist * p.second;
        }
        if (tmp < nin) {
            nin = tmp;
            best = pm;
        }
    } while (next_permutation(pm.begin(), pm.end()));

    for (int i = 0; i < 9; i++) {
        cout << best[i];
        if (i % 3 == 2) cout << '\n';
    }
}

C++: #include <bits/stdc++.h>

using namespace std;

int c[10][10];

int main() {
    int N;
    string s;
    cin >> N;
    cin >> s;
    vector<int> p = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    for (int i = 0; i + 1 < s.size(); i++) {
        c[s[i] - '1'][s[i + 1] - '1']++;
    }

    vector<int> bst;
    int ans = 1e9;
    do {
        int d[10][10] = {};
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int y = i / 3 - j / 3;
                int x = i % 3 - j % 3;
                d[p[i]][p[j]] = abs(x) + abs(y);
            }
        }
        int cst = 0;
        for(int i = 0 ; i < 9 ; i++)
            for(int j = 0 ; j < 9 ; j++)
                cst += c[i][j] * d[i][j];
        if( ans > cst ){
            ans = cst;
            bst = p;
        }

    } while (next_permutation(p.begin(), p.end()));

    for(int i = 0 ; i < 3 ; i++){
        for(int j = 0 ; j < 3 ; j++){
            cout << bst[i*3+j]+1 << (j+1==3 ? "\n" : "");
        }
    }


}