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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

struct LOC{
	void set(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

int LENGTH;
int min_change;

int table_index;
int table[362880][9];
int tmp_array[9],phone[3][3],ans[3][3],adj[10][10];
bool used[10];
char buf[NUM];
LOC loc[10];

void recursive(int index){

	if(index == 9){

		for(int i = 0; i < 9; i++){
			table[table_index][i] = tmp_array[i];
		}
		table_index++;

		return;
	}

	for(int i = 1; i <= 9; i++){

		if(used[i])continue;
		tmp_array[index] = i;
		used[i] = true;
		recursive(index+1);
		used[i] = false;
	}
}

void calc(int num_index){

	int index = 0;

	//電話を作成
	for(int row = 0; row < 3; row++){
		for(int col = 0; col < 3; col++){
			phone[row][col] = table[num_index][index++];
			loc[phone[row][col]].set(row,col);
		}
	}

	int count = 0;
	//指は最初の数字に合わせておく

	for(int i = 1; i <= 9; i++){
		for(int k = 1; k <= 9; k++){
			count += (abs(loc[i].row-loc[k].row)+abs(loc[i].col-loc[k].col))*adj[i][k];
		}
	}

	if(count < min_change){
		for(int row = 0; row < 3; row++){
			for(int col = 0; col < 3; col++){
				ans[row][col] = phone[row][col];
			}
		}
		min_change = count;
	}
}



int main(){

	scanf("%d",&LENGTH);
	scanf("%s",buf);

	for(int i = 1; i <= 9; i++){
		for(int k = 1; k <= 9; k++){
			adj[i][k] = 0;
		}
	}

	//隣接回数を数える
	for(int i = 1; i < LENGTH; i++){

		adj[buf[i]-'0'][buf[i-1]-'0']++;
	}

	table_index = 0;

	for(int i = 1; i <= 9; i++)used[i] = false;

	//9!の数列を作る
	for(int i = 1; i <= 9; i++){

		tmp_array[0] = i;
		used[i] = true;
		recursive(1);

		used[i] = false;
	}

	min_change = BIG_NUM;

	for(int i = 0; i < table_index; i++){

		calc(i);
	}


	for(int row = 0; row < 3; row++){
		for(int col = 0; col < 3; col++){
			printf("%d",ans[row][col]);
		}
		printf("\n");
	}


	return 0;
}

C++: #include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template <class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	string s; cin >> s;
	vvi cnt(9, vi(9, 0));
	REP(i, n - 1) {
		cnt[s[i] - '0' - 1][s[i + 1] - '0' - 1]++;
	}
	vi p(9);
	REP(i, 9)p[i] = i;
	int ans = INF;
	vi ansp = p;
	do {
		vi x(9), y(9);
		REP(i, 9) {
			x[i] = i / 3;
			y[i] = i % 3;
		}
		int sum = 0;
		REP(i, 9)REP(j, 9) {
			sum += cnt[p[i]][p[j]] * (abs(x[i] - x[j]) + abs(y[i] - y[j]));
		}
		if (chmin(ans, sum))ansp = p;
	} while (next_permutation(ALL(p)));
	REP(i, 3) {
		REP(j, 3) {
			cout << ansp[i * 3 + j]+1;
		}
		cout << endl;
	}
}