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 ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;
const int INF = 19191919;

int dist(pi p, pi q){
    return abs(p.fi-q.fi) + abs(p.se-q.se);
}

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

    map<pi,int> ct;
    rep(i,n-1){
        int a = s[i]-'0', b = s[i+1]-'0';
        ++ct[{a,b}];
    }

    int ans = INF;
    vector<int> v(9);

    vector<int> p(9);
    rep(i,9) p[i] = i+1;
    do{
        vector<pi> pos(10);
        rep(i,9) pos[p[i]] = {i/3,i%3};

        int t = 0;
        for(const auto &pp:ct){
            int num = pp.se;
            int a = pp.fi.fi, b = pp.fi.se;
            t += num * dist(pos[a],pos[b]);
        }

        if(t < ans){
            ans = t;
            v = p;
        }
    }while(next_permutation(all(p)));

    rep(i,3){
        rep(j,3) cout << v[3*i+j];
        cout << "\n";
    }
    return 0;
}

C++: //
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class reverse_range {private:struct I {int x;int operator*() {return x-1;}bool operator!=(I& lhs) {return x>lhs.x;}void operator++() {--x;}};I i, n;public:reverse_range(int n) :i({ 0 }), n({ n }){}reverse_range(int i, int n) :i({ i }), n({ n }){}I& begin() {return n;}I& end() {return i;}};
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }reverse_range operator!(){return reverse_range(*i,*n);}};

int cnt[10][10];
int d[10][10];
int main(){
    int N;
    cin>>N;
    string s;
    cin>>s;
    for(int i:range(N-1)){
        cnt[s[i]-'0'][s[i+1]-'0']++;
    }
    pair<int,vector<int>> ret(912345,vector<int>());
    vector<int> o(9);
    iota(ALL(o),1);
    do{
        for(int i:range(1,10)){
            d[i][i]=0;
            for(int j:range(1,10))d[i][j]=10;
        }
        for(int i:range(6)){
            d[o[i]][o[i+3]]=1;
            d[o[i+3]][o[i]]=1;
        }
        for(int i:range(10)){
            if(i%3){
                d[o[i]][o[i-1]]=1;
                d[o[i-1]][o[i]]=1;
            }
        }
        for(int k:range(1,10))
        for(int i:range(1,10))
        for(int j:range(1,10))
        chmin(d[i][j],d[i][k]+d[k][j]);
        int ans=0;
        for(int i:range(1,10)){
            for(int j:range(1,10)){
                ans+=d[i][j]*cnt[i][j];
            }
        }
        chmin(ret,make_pair(ans,o));
    }while(next_permutation(ALL(o)));
    for(int i:range(3)){
        for(int j:range(3)){
            cout<<ret.second[i*3+j];
        }
        cout<<endl;
    }
    return 0;
}

C++: /*  -*- coding: utf-8 -*-
 *
 * 3053.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int M = 9;
const int W = 3;
const int INF = 1 << 30;

/* typedef */

/* global variables */

char s[MAX_N + 4];
int mvs[M][M], ds[M][M], ps[M];

/* subroutines */

inline int ps2i(int ps[]) {
  int sum = 0;
  for (int i = 0; i < M; i++) sum = sum * 10 + ps[i];
  return sum;
}

inline void pos2xy(int pos, int &x, int &y) { x = pos % W, y = pos / W; }
inline int xy2pos(int x, int y) { return y * W + x; }

inline int dist(int pi, int pj) {
  int xi, yi, xj, yj;
  pos2xy(pi, xi, yi), pos2xy(pj, xj, yj);
  return abs(xj - xi) + abs(yj - yi);
}

/* main */

int main() {
  int n;
  scanf("%d%s", &n, s);

  for (int i = 0, j = 1; j < n; i++, j++)
    if (s[i] != s[j]) {
      int di = s[i] - '1', dj = s[j] - '1';
      mvs[di][dj]++;
    }

  for (int i = 0; i < M; i++)
    for (int j = 0; j < M; j++) ds[i][j] = dist(i, j);
  for (int i = 0; i < M; i++) ps[i] = i;

  int mind = INF, minph = 0;

  do {
    //printf("%09d\n", ps2i(ps));
    int d = 0;
    for (int i = 0; i < M; i++)
      for (int j = 0; j < M; j++)
	d += mvs[ps[i]][ps[j]] * ds[i][j];

    if (mind > d)
      mind = d, minph = ps2i(ps);
    else if (mind == d) {
      int ph = ps2i(ps);
      if (minph > ph) minph = ph;
    }
  } while (next_permutation(ps, ps + M));
  //printf("%09d\n", minph);

  for (int y = 0, e = 100000000; y < W; y++) {
    for (int x = 0; x < W; x++, e /= 10)
      putchar('1' + (minph / e) % 10);
    putchar('\n');
  }
  return 0;
}