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 int long long
#define REP(i, n) for (long long i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (long long i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<int, int>;
template <class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

// debug
template <class T> ostream& operator<<(ostream &s, vector<T>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " "); return s; }
template <class T> ostream& operator<<(ostream &s, vector<vector<T>>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : "\n"); return s; }
template <class T, class S> ostream& operator<<(ostream &s, pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; }
template <class T, class S> ostream& operator<<(ostream& s, map<T, S> m) { for (auto it = m.begin(); it != m.end(); it++) { s << *it << (next(it) == m.end() ? "" : "\n"); } return s; }
#ifdef _MY_DEBUG
  #define dump(...) cerr << "/* " << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), cerr << "*/\n\n";
#else
  #define dump(...)
#endif
void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); }

struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr int MOD = 1000000007;
// *************** TEMPLATE END *************** 

signed main() {
  int n; cin >> n;
  string ss; cin >> ss;
  vector<int> s(n); REP (i, n) s[i] = ss[i] - '1';
  vector<vector<int>> a(9, vector<int>(9));
  REP (i, n - 1) {
    int x = s[i], y = s[i + 1];
    if (x > y) swap(x, y);
    a[x][y]++;
  }
  vector<int> va;
  int ans = 1e18;
  vector<int> t(9); REP (i, 9) t[i] = i;
  do {
    int acc = 0;
    REP (i, 9) {
      REPI (j, i + 1, 9) {
        int x = t[i], y = t[j];
        if (x > y) swap(x, y);
        int dis = abs(i % 3 - j % 3) + abs(i / 3 - j / 3);
        acc += a[x][y] * dis;
      }
    }
    if (chmin(ans, acc)) {
      va = t;
    }
  } while (next_permutation(ALL(t)));
  REP (i, 3) {
    REP (j, 3) {
      cout << va[3 * i + j] + 1;
    }
    cout << endl;
  }
}

C++: #include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int abs(int a) {return a < 0 ? (-a) : a;}
int costlist[362880][9][9];
int perm[362880][9];
int main() {
    int arr[] = {0,1,2,3,4,5,6,7,8};

    int index = 0;
    do {
        for (int row=0; row<3; row++) {
            for (int col=0; col<3; col++) {
                for (int t_row=0; t_row<3; t_row++) {
                    for (int t_col=0; t_col<3; t_col++) {
                        int distance = abs(row-t_row) + abs(col-t_col);
                        costlist[index][arr[row*3+col]][arr[t_row*3+t_col]] = distance;
                    }
                }
            }
        }
        for (int i=0; i<9; i++) perm[index][i] = arr[i] + 1;
        index++;
    } while (next_permutation(arr, arr+9));
    //cerr << "ready" << endl;

    int N;
    int move[9][9] = {0};
    cin >> N;
    int before;
    for (int i=0; i<N; i++) {
        char c;
        cin >> c;
        int s = c - 0x30 - 1;
        if (i > 0) {
            move[before][s]++;
        }
        before = s;
    }

    int mincost = -1;
    int min_index = 0;
    for (int index=0; index < 362880; index++) {
        int cost = 0;
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                cost += costlist[index][i][j] * move[i][j];
            }
        }
        if (mincost == -1 || cost < mincost) {
            mincost = cost;
            min_index = index;
        }
    }

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

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

#define INF 1<<29

int cnt[9][9];

int calc_dist(const vector<int> &v){
  int ret = 0;
  for(int i=0;i<9;i++){
    for(int j=i+1;j<9;j++){
      int dist_ij = abs(int(i/3) - int(j/3)) + abs(int(i%3) - int(j%3));
      //      cout << v[i] << " " << v[j] << " " << dist_ij << " " << cnt[v[i]-1][v[j]-1] << endl;
      ret += dist_ij * cnt[v[i]-1][v[j]-1];
    }
  }
  return ret;
}

int main(){
  memset(cnt, 0, sizeof(cnt));
  int N;
  string S;
  cin >> N >> S;
  for(int i=1;i<N;i++){
    cnt[S[i-1]-'1'][S[i]-'1']++;
    cnt[S[i]-'1'][S[i-1]-'1']++;
  }

  vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};
  vector<int> ret;
  int best_score = INF;
  do{
    int score = calc_dist(v);
    if(score < best_score){
      //      cout << score << endl;
      best_score = score;
      ret = v;
    }
}while(next_permutation(v.begin(), v.end()));
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cout << ret[i*3+j];
    }
    cout << endl;
  }
  return 0;
}