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;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; // 移動方向

int n;
string s;

void input(){
    cin >> n >> s;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    vector<int> button = {1,2,3,4,5,6,7,8,9};
    // 9!ためす
    int tmp = INF;
    vector<int> ans;
    map<pair<int, int>, int> cnt; //key:grid->grid, value:回数
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            cnt[make_pair(i, j)] = 0;
        }
    }
    for(int i=0;i<n-1;i++){
        cnt[make_pair(int(s[i]-'0'), int(s[i+1]-'0'))]++;
    }

    do{
        map<int, pair<int, int>> grid; //key:button, value:grid
        for(int i=0;i<9;i++){
            grid[button[i]] = make_pair(i/3, i%3);
        }
        int rec = 0;
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                pair<int, int> a,b;
                a = grid[i];
                b = grid[j];
                rec += cnt[make_pair(i, j)] * (abs(a.first - b.first) + abs(a.second - b.second));
            }
        }
        if(tmp > rec){
            tmp = rec;
            ans = button;
        }
    }while(next_permutation(button.begin(), button.end()));
    for(int i=0;i<9;i++){
        cout << ans[i];
        if(i%3 == 2) cout << endl;
    }
    return 0;
}

C++: #include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

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

    // count i -> j 
    int num[10][10];
    memset(num, 0, sizeof(num));
    for(int i=0; i<n-1; i++){
        num[s[i]-'0'][s[i+1]-'0']++;
    }

    vector<int> v(9);
    iota(v.begin(), v.end(), 1);

    ll costmin=INF;
    vector<int> ans(9);
    do{
        int phone[3][3];
        for(int i=0; i<9; i++){
            phone[i/3][i%3]=v[i];
        }

        int cost[10][10];
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                cost[phone[i/3][i%3]][phone[j/3][j%3]]=abs(i/3-j/3)+abs(i%3-j%3);
            }
        }

        ll sum=0;
        for(int i=1; i<=9; i++){
            for(int j=1; j<=9; j++){
                sum+=cost[i][j]*num[i][j];
            }
        }

        if(sum<costmin){
            costmin=sum;
            ans=v;
        }

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

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

C++: #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
string s;
vector<int>ans;
int D[10][10]={
	{0,0,0,0,0,0,0,0,0,0},
	{0,0,1,2,1,2,3,2,3,4},
	{0,1,0,1,2,1,2,3,2,3},
	{0,2,1,0,3,2,1,4,3,2},
	{0,1,2,3,0,1,2,1,2,3},
	{0,2,1,2,1,0,1,2,1,2},
	{0,3,2,1,2,1,0,3,2,1},
	{0,2,3,4,1,2,3,0,1,2},
	{0,3,2,3,2,1,2,1,0,1},
	{0,4,3,2,3,2,1,2,1,0}
};
main()
{
	cin>>n>>s;
	int c[10][10]={};
	for(int i=1;i<n;i++)c[s[i-1]-'0'][s[i]-'0']++;
	vector<int>now;
	for(int i=1;i<=9;i++)
	{
		now.push_back(i);
	}
	int ansm=1e9;
	int cnt=0;
	do{
		int nowm=0;
		for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)
		{
			nowm+=c[now[i-1]][now[j-1]]*D[i][j];
		}
		if(ansm>nowm)
		{
			ansm=nowm;
			ans=now;
		}
		else if(ansm==nowm&&ans>now)
		{
			ans=now;
		}
		cnt++;
	}while(next_permutation(now.begin(),now.end()));
	for(int i=0;i<9;i++)
	{
		cout<<ans[i];
		if(i%3==2)cout<<endl;
	}
}