Example scores:
0) 12.0
1) 14673.0
2) 727.0
3) 27.0
4) 4162.0
5) 465.0
6) 7921.0
7) 6024.0
8) 49.0
9) 2874.0


Approach
  • N<=10 : ビームサーチを1回使いました。
  • 10<N<=40 : 深さ20のビームサーチを9秒間使い続けた解と、すべての数のマンハッタン距離が6以下の状態まで戻して、貪欲に端からそろえる解の良い方を返しました。
  • 子の生成 :
    • 2x2と3x3だけ
    • R,Lを1回
      • Rotationせずにシミュレーションすることで、2倍くらい高速化できました。
    • N<=10のときは全部の位置からRotationする
    • 10<N<=40のときは、1つ数を選んで、その数が2x2または3x3に含まれる位置のもう1つ外側からRotationする
  • 盤面重複の除去 : Zobrist Hashing
  • 評価関数 : 4*この問題のスコア + max(abs(r1-r2),abs(c1-c2)) * (abs(r1-r2)+abs(c1-c2))
  • その他の工夫 : 中途半端にいい位置にすると、位置のペナルティを0にしたときのスコアの改善量よりRotationのペナルティの方が大きくなって、位置のペナルティが0にならなくなるので、5x5の範囲がP*5*5以下のペナルティになったときは、ビーム幅を2倍、Rotationする位置ももう1つじゃなくて2つ外側の位置からに増やして、ペナルティを0にしやすくした。


感想 ちゃんと差がつくいい問題だった。 ただ基本的に、まわしてそろえるなので、去年参加した人は強そうだな~と思った。 kosakkunさんのところにも似たようなのがあって、やったことある人は強そうだな~と思った。

source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;

class Solver {
    private final int N;
    private final int P;

    private final int[][] rxcToNumber;
    private final int[] numberToR;
    private final int[] numberToC;

    private final ArrayList moves = new ArrayList<>();
    private final int[] rotatePenalties;
    private int sumRotatePenalty;

    private final long[][][] hashes;
    private long hash;

    private int[][][] evaluations;

    private final XorShift rng = new XorShift(System.nanoTime());
    private final Watch watch = new Watch();

    private Comparator comparator = new Comparator() {
        @Override
        public int compare(State o1, State o2) {

            if (o1.gridPenalty + o1.sumRotatePenalty < o2.gridPenalty + o2.sumRotatePenalty) {
                return -1;
            }
            if (o1.gridPenalty + o1.sumRotatePenalty > o2.gridPenalty + o2.sumRotatePenalty) {
                return 1;
            }

            int coef = 10;
            if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 < coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) {
                return -1;
            }
            if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 > coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) {
                return 1;
            }
            return 0;
        }
    };

    private Comparator comparator2 = new Comparator() {
        @Override
        public int compare(State o1, State o2) {
            int coef = 4;
            if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 < coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) {
                return -1;
            }
            if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 > coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) {
                return 1;
            }
            return 0;
        }
    };
    private Comparator comparator6 = new Comparator() {
        @Override
        public int compare(State2 o1, State2 o2) {
            if (o1.gridPenalty2 < o2.gridPenalty2) {
                return -1;
            }
            if (o1.gridPenalty2 > o2.gridPenalty2) {
                return 1;
            }

            if (o1.distance < o2.distance) {
                return -1;
            }
            if (o1.distance > o2.distance) {
                return 1;
            }

            if (o1.gridPenalty + o1.sumRotatePenalty < o2.gridPenalty + o2.sumRotatePenalty) {
                return -1;
            }
            if (o1.gridPenalty + o1.sumRotatePenalty > o2.gridPenalty + o2.sumRotatePenalty) {
                return 1;
            }

            return 0;
        }
    };
    private int baseDepth6 = -1;
    private ArrayList moveHistory6 = new ArrayList();
    private ArrayList moveHistoryGreedy = new ArrayList();

    public Solver(int N, int P, int[][] grid) {
        this.N = N;
        this.P = P;

        rxcToNumber = grid;
        numberToR = new int[N * N];
        numberToC = new int[N * N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                grid[r][c]--;
                numberToR[grid[r][c]] = r;
                numberToC[grid[r][c]] = c;
            }
        }

        rotatePenalties = new int[N + 1];
        for (int n = 2; n <= N; n++) {
            rotatePenalties[n] = (int) (1e-9 + Math.pow(n - 1, 1.5));
        }

        hashes = new long[N][N][N * N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                for (int number = 0; number < N * N; number++) {
                    hashes[r][c][number] = rng.nextLong();
                }
            }
        }
        hash = 0;

        evaluations = new int[N][N][N * N];
        Utils.debug("N", N, "P", P);
    }

    public void solve() {
        if (N <= 10) {
            solveOneBeam();
        } else if (N <= 40) {
            solveBeam2();
            ArrayList bestMoveHistory = new ArrayList();
            for (int i = 0; i < moveHistory.size(); i++) {
                Move move = moveHistory.get(i);
                bestMoveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
            }
            int bestScore = calculateGridPenalty() + sumRotatePenalty;
            Utils.debug("bestScore", bestScore, calculateGridPenalty(), sumRotatePenalty);
            for (; moveHistory.size() > 0;) {
                sumRotatePenalty -= rotatePenalties[moveHistory.get(moveHistory.size() - 1).size];
                previous();
            }
            for (int i = 0; i < moveHistory6.size(); i++) {
                Move move = moveHistory6.get(i);
                for (int j = 0; j < move.numRotations; j++) {
                    sumRotatePenalty += rotatePenalties[move.size];
                }
                next(move.r, move.c, move.size, move.dir, move.numRotations);
            }
            Utils.debug("score2", calculateGridPenalty(), sumRotatePenalty);

            greedy();

            int score = calculateGridPenalty() + sumRotatePenalty;
            Utils.debug("score", score, calculateGridPenalty(), sumRotatePenalty);
            if (score < bestScore) {
                moves.clear();
                for (int i = 0; i < moveHistory6.size(); i++) {
                    Move move = moveHistory6.get(i);
                    moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                }
                for (int i = 0; i < moveHistoryGreedy.size(); i++) {
                    Move move = moveHistoryGreedy.get(i);
                    moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                }

            } else {
                moves.clear();
                for (int i = 0; i < bestMoveHistory.size(); i++) {
                    Move move = bestMoveHistory.get(i);
                    moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                }

            }

        }
    }

    private void greedy() {

        int[] numbers = new int[N * N];
        {
            boolean[][] used = new boolean[N][N];
            int index = 0;
            for (int i = 0; i < N; i++) {

                {
                    int r = i;
                    for (int c = 0; c < N; c++) {
                        if (used[r][c]) {
                            continue;
                        }
                        used[r][c] = true;
                        numbers[index] = r * N + c;
                        index++;
                    }
                }
                {
                    int c = i;
                    for (int r = 0; r < N; r++) {
                        if (used[r][c]) {
                            continue;
                        }
                        used[r][c] = true;
                        numbers[index] = r * N + c;
                        index++;
                    }
                }

            }
        }
        for (int index = 0; index < N * N; index++) {
            if (index >= N * N - 16) {
                ArrayList moves = beamsearch4x4(20, 1000);
                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    this.moveHistoryGreedy.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        sumRotatePenalty += rotatePenalties[move.size];
                        rotate(move.r, move.c, move.size, move.dir);
                    }
                }
                break;
            }

            int number = numbers[index];
            if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) {
                evaluations[numberToR[number]][numberToC[number]][number] = -1;
                continue;
            }

            ArrayList moves = dijkstra(number);
            for (int i = 0; i < moves.size(); i++) {
                State2 move = moves.get(i);
                this.moveHistoryGreedy.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                for (int j = 0; j < move.numRotations; j++) {
                    this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                    sumRotatePenalty += rotatePenalties[move.size];
                    rotate(move.r, move.c, move.size, move.dir);
                }
            }
            if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) {
                evaluations[numberToR[number]][numberToC[number]][number] = -1;
                continue;
            }
            if (getTargetRow(number) < N - 1 && getTargetColumn(number) < N - 1) {
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        System.err.format("%3d", rxcToNumber[r][c]);
                    }
                    System.err.println();
                }
                assert false;
            }

            {
                if (numberToC[number] == N - 1) {
                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 2, 2, 'L', 1));
                    this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 2, 2, 'L', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 1, numberToC[number] - 2, 2, 'L');

                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'L', 1));
                    this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'L', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 1, numberToC[number] - 1, 2, 'L');

                    this.moveHistoryGreedy.add(new Move(numberToR[number], numberToC[number] - 2, 2, 'R', 1));
                    this.moves.add(new Move(numberToR[number], numberToC[number] - 2, 2, 'R', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number], numberToC[number] - 2, 2, 'R');
                    if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) {
                        evaluations[numberToR[number]][numberToC[number]][number] = -1;
                        continue;
                    }
                }

                if (numberToR[number] == N - 1) {
                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 2, numberToC[number] - 1, 2, 'R', 1));
                    this.moves.add(new Move(numberToR[number] - 2, numberToC[number] - 1, 2, 'R', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 2, numberToC[number] - 1, 2, 'R');

                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'R', 1));
                    this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'R', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 1, numberToC[number] - 1, 2, 'R');

                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 2, numberToC[number], 2, 'L', 1));
                    this.moves.add(new Move(numberToR[number] - 2, numberToC[number], 2, 'L', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 2, numberToC[number], 2, 'L');
                    if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) {
                        evaluations[numberToR[number]][numberToC[number]][number] = -1;
                        continue;
                    }
                }

                assert false;
            }
        }

        int score = calculateGridPenalty() + sumRotatePenalty;
        Utils.debug("greedy", "score", score, "GridPenalty",

                calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString());
    }

    private ArrayList dijkstra(int number) {
        int baseDepth = moveHistory.size();

        int goalR = getTargetRow(number);
        int goalC = getTargetColumn(number);
        if (goalC == N - 1) {
            goalR++;
        } else if (goalR == N - 1) {
            goalC++;
        }

        HashSet usedHash = new HashSet();

        boolean[][] used = new boolean[N][N];

        PriorityQueue pq = new PriorityQueue<>(comparator6);
        State2 best = null;
        final int calculateGridPenalty3 = calculateGridPenalty3();
        {
            State2 e = new State2(null, -1, -1, -1, 'L', 1, calculateGridPenalty(), sumRotatePenalty, calculateGridPenalty3, manhattanDistance(goalR, goalC, numberToR[number], numberToC[number]), 1000000);
            pq.add(e);

            usedHash.add(hash);
            best = e;
        }

        int numPolls = 0;
        for (; !pq.isEmpty();) {
            State2 currentState = pq.poll();

            numPolls++;
            ArrayList moves2 = reverse2(toList(currentState));
            set2(moves2, baseDepth);
            final int r0 = numberToR[number];
            final int c0 = numberToC[number];
            used[r0][c0] = true;
            if (currentState.distance == 0) {
                best = currentState;
                break;
            }

            int margin = 0;

            for (int size = 2; size <= 2; size++) {

                int startR = Math.max(0, r0 - (size - 1) - margin);
                int endR = Math.min(N - 1, r0 + margin);
                int startC = Math.max(0, c0 - (size - 1) - margin);
                int endC = Math.min(N - 1, c0 + margin);

                for (int r = startR; r <= endR; r++) {
                    for (int c = startC; c <= endC; c++) {
                        if (!canRotate(r, c, size)) {
                            continue;
                        }

                        int currentGridPenalty = calculateGridPenalty(r, c, size);
                        int currentGridPenalty3 = calculateGridPenalty3(r, c, size);
                        long currentHash = calculateHash(r, c, size);

                        {
                            int i = 1;
                            long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                            if (usedHash.add(e)) {
                                int gridPenalty = calculateGridPenaltyR(r, c, size);
                                int gridPenalty3 = calculateGridPenalty3R(r, c, size);
                                int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                boolean isOut = r0 - r < 0 || r0 - r >= size || c0 - c < 0 || c0 - c >= size;
                                int nextR = isOut ? r0 : calculateNextR_R(r, c, size, r0 - r, c0 - c);
                                int nextC = isOut ? c0 : calculateNextC_R(r, c, size, r0 - r, c0 - c);
                                int nextPenalty3 = currentState.gridPenalty2 - currentGridPenalty3 + gridPenalty3;
                                if (nextPenalty3 <= calculateGridPenalty3) {
                                    pq.add(new State2(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, nextPenalty3, manhattanDistance(goalR, goalC, nextR, nextC), 0));
                                }
                            }
                        }
                        {
                            int i = 3;
                            long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                            if (usedHash.add(e)) {
                                int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                int gridPenalty3 = calculateGridPenalty3RRR(r, c, size);
                                int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                boolean isOut = r0 - r < 0 || r0 - r >= size || c0 - c < 0 || c0 - c >= size;
                                int nextR = isOut ? r0 : calculateNextR_RRR(r, c, size, r0 - r, c0 - c);
                                int nextC = isOut ? c0 : calculateNextC_RRR(r, c, size, r0 - r, c0 - c);
                                int nextPenalty3 = currentState.gridPenalty2 - currentGridPenalty3 + gridPenalty3;
                                if (nextPenalty3 <= calculateGridPenalty3) {
                                    pq.add(new State2(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, nextPenalty3, manhattanDistance(goalR, goalC, nextR, nextC), 0));
                                }
                            }
                        }

                    }
                }

            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }
        return reverse2(toList(best));
    }

    private void solveBeam() {
        int bestScore = (int) 1e9;
        int numBeams = 0;
        int numMoves0 = 0;
        int numMovesNot0AndNotUpdateBest = 0;
        for (; watch.getSecond() < 9.5; numBeams++) {
            if (numBeams % 50 == 0) {
                Utils.debug("numBeams", numBeams, "bestScore", bestScore);
            }
            int worstNumber = -1;
            int worst = -1;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c]));
                    if (distance <= 0) {
                        continue;
                    }

                    distance = distance * 1000 + (int) (5000 * rng.nextDouble());
                    if (distance > worst) {
                        worst = distance;
                        worstNumber = rxcToNumber[r][c];
                    }
                }
            }
            if (worstNumber == -1) {
                break;
            }

            int maxDepth = 10;
            int maxWidth = 10;
            if (N == 8) {
                maxDepth = 20;
                maxWidth = 100;
            } else if (N == 9) {
                maxDepth = 20;
                maxWidth = 100;
            } else if (N == 10) {
                maxDepth = 10;
                maxWidth = 300;
            } else if (N >= 10 && N < 15) {
                maxDepth = 10;
                maxWidth = (int) (125 + (300 - 125) / 5.0 * (15 - N));
            } else if (N == 15) {
                maxDepth = 10;
                maxWidth = 125;
            } else if (N >= 15 && N < 20) {
                maxDepth = 10;
                maxWidth = (int) (50 + (125 - 50) / 5.0 * (20 - N));
            } else if (N == 20) {
                maxDepth = 10;
                maxWidth = 50;
            } else if (N >= 20 && N < 25) {
                maxDepth = 10;
                maxWidth = (int) (26 + 4.8 * (25 - N));
            } else if (N == 25) {
                maxDepth = 10;
                maxWidth = 26;
            } else if (N >= 25 && N < 30) {
                maxDepth = 10;
                maxWidth = (int) (16 + 2 * (30 - N));
            } else if (N == 30) {
                maxDepth = 10;
                maxWidth = 16;
            } else if (N >= 30 && N <= 40) {
                maxDepth = 10;
                maxWidth = 6 + 40 - N;
            } else if (N == 40) {
                maxDepth = 10;
                maxWidth = 6;
            }

            maxDepth = 20;

            ArrayList moves = null;

            if (useOtherBeam(worstNumber)) {
                moves = beamsearchMargin2(worstNumber, maxDepth, 2 * maxWidth);
            } else {
                moves = beamsearch(worstNumber, maxDepth, maxWidth);
            }

            if (moves.size() == 0) {
                numMoves0++;
                continue;
            }

            int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty;
            if (score < bestScore) {
                bestScore = score;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];
                    }
                }

                assert score == calculateGridPenalty() + sumRotatePenalty;

            } else {
                numMovesNot0AndNotUpdateBest++;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];
                    }
                }

            }

        }

        int score = calculateGridPenalty() + sumRotatePenalty;
        Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString());
        Utils.debug("numMoves0", numMoves0, "numMovesNot0AndNotUpdateBest", numMovesNot0AndNotUpdateBest);
    }

    private void solveBeam2() {
        int bestScore = (int) 1e9;
        int numBeams = 0;
        int numMoves0 = 0;
        int numMovesNot0AndNotUpdateBest = 0;
        for (; watch.getSecond() < 9.0; numBeams++) {
            if (numBeams % 50 == 0) {
                Utils.debug("numBeams", numBeams, "bestScore", bestScore);
            }
            int worstNumber = -1;
            int worst = -1;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c]));
                    if (distance <= 6) {
                        continue;
                    }

                    distance = distance * 1000 + (int) (5000 * rng.nextDouble());
                    if (distance > worst) {
                        worst = distance;
                        worstNumber = rxcToNumber[r][c];
                    }
                }
            }
            if (worstNumber == -1) {
                if (baseDepth6 == -1) {
                    baseDepth6 = moveHistory.size();
                    for (int i = 0; i < moveHistory.size(); i++) {
                        Move move = moveHistory.get(i);
                        moveHistory6.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                    }
                    Utils.debug("score2", calculateGridPenalty(), sumRotatePenalty);
                }
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c]));
                        if (distance <= 0) {
                            continue;
                        }

                        distance = distance * 1000 + (int) (5000 * rng.nextDouble());
                        if (distance > worst) {
                            worst = distance;
                            worstNumber = rxcToNumber[r][c];
                        }
                    }
                }
                if (worstNumber == -1) {
                    break;
                }
            }

            int maxDepth = 10;
            int maxWidth = 10;
            if (N == 8) {
                maxDepth = 20;
                maxWidth = 100;
            } else if (N == 9) {
                maxDepth = 20;
                maxWidth = 100;
            } else if (N == 10) {
                maxDepth = 10;
                maxWidth = 300;
            } else if (N >= 10 && N < 15) {
                maxDepth = 10;
                maxWidth = (int) (125 + (300 - 125) / 5.0 * (15 - N));
            } else if (N == 15) {
                maxDepth = 10;
                maxWidth = 125;
            } else if (N >= 15 && N < 20) {
                maxDepth = 10;
                maxWidth = (int) (50 + (125 - 50) / 5.0 * (20 - N));
            } else if (N == 20) {
                maxDepth = 10;
                maxWidth = 50;
            } else if (N >= 20 && N < 25) {
                maxDepth = 10;
                maxWidth = (int) (26 + 4.8 * (25 - N));
            } else if (N == 25) {
                maxDepth = 10;
                maxWidth = 26;
            } else if (N >= 25 && N < 30) {
                maxDepth = 10;
                maxWidth = (int) (16 + 2 * (30 - N));
            } else if (N == 30) {
                maxDepth = 10;
                maxWidth = 16;
            } else if (N >= 30 && N <= 40) {
                maxDepth = 10;
                maxWidth = 6 + 40 - N;
            } else if (N == 40) {
                maxDepth = 10;
                maxWidth = 6;
            }

            maxDepth = 20;

            ArrayList moves = null;

            if (useOtherBeam(worstNumber)) {
                moves = beamsearchMargin2(worstNumber, maxDepth, 2 * maxWidth);
            } else {
                moves = beamsearch(worstNumber, maxDepth, maxWidth);
            }

            if (moves.size() == 0) {
                numMoves0++;
                continue;
            }

            int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty;
            if (score < bestScore) {
                bestScore = score;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    moveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];
                    }
                }

                assert score == calculateGridPenalty() + sumRotatePenalty;

            } else {
                numMovesNot0AndNotUpdateBest++;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    moveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];
                    }
                }

            }

        }

        int score = calculateGridPenalty() + sumRotatePenalty;
        Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString());
        Utils.debug("numMoves0", numMoves0, "numMovesNot0AndNotUpdateBest", numMovesNot0AndNotUpdateBest);
    }

    private boolean useOtherBeam(int number) {
        int r = numberToR[number];
        int c = numberToC[number];
        r = Math.max(2, Math.min(N - 3, r));
        c = Math.max(2, Math.min(N - 3, c));
        int startR = r - 2;
        int startC = c - 2;
        int endR = r + 3;
        int endC = c + 3;
        return calculateGridPenalty(startR, startC, Math.min(endR - startR, endC - startC)) <= P * (endR - startR) * (endC - startC);
    }

    private void solveOneBeam() {
        int bestScore = (int) 1e9;
        int numBeams = 0;
        {

            int maxDepth = 1000;
            int maxWidth = 10;
            if (N == 4) {
                maxDepth = 25;
                maxWidth = 18000;
            } else if (N == 5) {
                maxDepth = 40;
                maxWidth = 6000;
            } else if (N == 6) {
                maxDepth = 60;
                maxWidth = 2500;
            } else if (N == 7) {
                maxDepth = 100;
                maxWidth = 1100;
            } else if (N == 8) {
                maxDepth = 150;
                maxWidth = 550;
            } else if (N == 9) {
                maxDepth = 220;
                maxWidth = 280;
            } else if (N == 10) {
                maxDepth = 320;
                maxWidth = 150;
            }
            ArrayList moves = beamsearch(maxDepth, maxWidth);

            int[] counts = new int[30];

            int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty;
            if (score < bestScore) {
                bestScore = score;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);

                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];

                        counts[move.size]++;
                    }
                }

                assert score == calculateGridPenalty() + sumRotatePenalty : Utils.toString(moves.get(moves.size() - 1).gridPenalty, moves.get(moves.size() - 1).sumRotatePenalty, calculateGridPenalty(), sumRotatePenalty);

            }

            Utils.debug("counts", counts);

        }

        int score = calculateGridPenalty() + sumRotatePenalty;
        Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString());
    }

    private boolean canRotate(int r, int c, int size) {
        return r >= 0 && c >= 0 && r + size <= N && c + size <= N;
    }

    private void rotate(int r0, int c0, int n, char dir0) {
        hash ^= calculateHash(r0, c0, n);
        if (dir0 == 'R') {
            for (int r = 0, m = n - 1, halfN = n / 2, halfN2 = (n - 1) / 2; r < halfN; r++) {
                for (int c = 0; c <= halfN2; c++) {
                    int swapppppppppppppppppppppppppppp = rxcToNumber[r0 + 0 + r][c0 + 0 + c];
                    rxcToNumber[r0 + 0 + r][c0 + 0 + c] = rxcToNumber[r0 + m - c][c0 + 0 + r];
                    rxcToNumber[r0 + m - c][c0 + 0 + r] = rxcToNumber[r0 + m - r][c0 + m - c];
                    rxcToNumber[r0 + m - r][c0 + m - c] = rxcToNumber[r0 + 0 + c][c0 + m - r];
                    rxcToNumber[r0 + 0 + c][c0 + m - r] = swapppppppppppppppppppppppppppp;
                }
            }
        } else {
            for (int r = 0, m = n - 1, halfN = n / 2, halfN2 = (n - 1) / 2; r < halfN; r++) {
                for (int c = 0; c <= halfN2; c++) {
                    int swapppppppppppppppppppppppppppp = rxcToNumber[r0 + 0 + r][c0 + 0 + c];
                    rxcToNumber[r0 + 0 + r][c0 + 0 + c] = rxcToNumber[r0 + 0 + c][c0 + m - r];
                    rxcToNumber[r0 + 0 + c][c0 + m - r] = rxcToNumber[r0 + m - r][c0 + m - c];
                    rxcToNumber[r0 + m - r][c0 + m - c] = rxcToNumber[r0 + m - c][c0 + 0 + r];
                    rxcToNumber[r0 + m - c][c0 + 0 + r] = swapppppppppppppppppppppppppppp;
                }
            }
        }
        hash ^= calculateHash(r0, c0, n);
        updateNumberToRxc(r0, c0, n);
    }

    private int calculateNextR_R(int r0, int c0, int size0, int r, int c) {
        return r0 + 0 + c;
    }

    private int calculateNextR_RR(int r0, int c0, int size0, int r, int c) {
        return r0 + (size0 - 1) - r;
    }

    private int calculateNextR_RRR(int r0, int c0, int size0, int r, int c) {
        return r0 + (size0 - 1) - c;
    }

    private int calculateNextC_R(int r0, int c0, int size0, int r, int c) {
        return c0 + (size0 - 1) - r;
    }

    private int calculateNextC_RR(int r0, int c0, int size0, int r, int c) {
        return c0 + (size0 - 1) - c;
    }

    private int calculateNextC_RRR(int r0, int c0, int size0, int r, int c) {
        return c0 + 0 + r;
    }

    private int calculateGridPenaltyR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - c][c0 + 0 + r];
                penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenaltyRR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - r][c0 + m - c];
                penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenaltyRRR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + 0 + c][c0 + m - r];
                penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = r0; r < r0 + size0; r++) {
            for (int c = c0; c < c0 + size0; c++) {
                int number = rxcToNumber[r][c];
                penalty += manhattanDistance(r, c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty() {
        int penalty = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int number = rxcToNumber[r][c];
                penalty += manhattanDistance(r, c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty3R(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - c][c0 + 0 + r];
                penalty += evaluations[r0 + r][c0 + c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty3RR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - r][c0 + m - c];
                penalty += evaluations[r0 + r][c0 + c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty3RRR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + 0 + c][c0 + m - r];
                penalty += evaluations[r0 + r][c0 + c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty3(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + r][c0 + c];
                penalty += evaluations[r0 + r][c0 + c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty3() {
        int penalty = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int number = rxcToNumber[r][c];
                penalty += evaluations[r][c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty2R(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - c][c0 + 0 + r];
                penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty2RR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - r][c0 + m - c];
                penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty2RRR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + 0 + c][c0 + m - r];
                penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty2(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = r0; r < r0 + size0; r++) {
            for (int c = c0; c < c0 + size0; c++) {
                int number = rxcToNumber[r][c];
                penalty += manhattanDistance2(r, c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty2() {
        int penalty = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int number = rxcToNumber[r][c];
                penalty += manhattanDistance2(r, c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    public String[] makeSolution() {
        String[] res = new String[moves.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = "" + moves.get(i).r + " " + moves.get(i).c + " " + moves.get(i).size + " " + moves.get(i).dir;
        }
        return res;
    }

    private int getTargetColumn(int number) {
        return number % N;
    }

    private int getTargetRow(int number) {
        return number / N;
    }

    private static int manhattanDistance2(int r, int c, int r2, int c2) {
        int absR = Math.abs(r - r2);
        int absC = Math.abs(c - c2);
        return Math.max(absR, absC) * (absR + absC);
    }

    private static int manhattanDistance(int r, int c, int r2, int c2) {
        int absR = Math.abs(r - r2);
        int absC = Math.abs(c - c2);
        return (absR + absC);
    }

    private ArrayList beamsearch4x4(int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();
        HashSet usedHash = new HashSet();

        ArrayList[] states = new ArrayList[1 << 5];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            int gridPenalty = calculateGridPenalty();
            int gridPenalty2 = calculateGridPenalty2();
            State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2);
            states[0].add(e);

            usedHash.add(hash);

            best = e;
        }
        int sumWidth = 0;

        for (int depth = 0; depth < maxDepth; depth++) {
            if (states[0].size() == 0) {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
                continue;
            }
            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (comparator.compare(currentState, best) < 0) {
                    best = currentState;
                }

                if (Integer.bitCount(depth) == 1) {
                    if (width == 0) {
                        Utils.debug(depth, currentState.gridPenalty, currentState.sumRotatePenalty);
                    }
                }

                set(reverse2(toList(currentState)), baseDepth);

                for (int size = 2; size <= 3; size++) {
                    for (int r = N - 4; r < N; r++) {
                        for (int c = N - 4; c < N; c++) {
                            if (!canRotate(r, c, size)) {
                                continue;
                            }

                            int currentGridPenalty = calculateGridPenalty(r, c, size);
                            int currentGridPenalty2 = calculateGridPenalty2(r, c, size);
                            long currentHash = calculateHash(r, c, size);
                            {
                                int i = 1;
                                long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2R(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }

                            }
                            {
                                int i = 3;
                                long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2RRR(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }

                            }
                        }
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0]);
            if (comparator.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }
        return reverse2(toList(best));
    }

    private ArrayList beamsearch(int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();
        HashSet usedHash = new HashSet();

        ArrayList[] states = new ArrayList[1 << 5];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            int gridPenalty = calculateGridPenalty();
            int gridPenalty2 = calculateGridPenalty2();
            State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2);
            states[0].add(e);

            usedHash.add(hash);

            best = e;
        }
        int sumWidth = 0;

        for (int depth = 0; depth < maxDepth; depth++) {
            if (states[0].size() == 0) {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
                continue;
            }

            if (depth % 4 == 0) {
                usedHash.clear();
            }
            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (comparator.compare(currentState, best) < 0) {
                    best = currentState;
                }

                if (Integer.bitCount(depth) == 1) {
                    if (width == 0) {
                        Utils.debug(depth, currentState.gridPenalty, currentState.sumRotatePenalty);
                    }
                }

                set(reverse2(toList(currentState)), baseDepth);

                for (int size = 2; size <= 3; size++) {
                    for (int r = 0; r < N; r++) {
                        for (int c = 0; c < N; c++) {
                            if (!canRotate(r, c, size)) {
                                continue;
                            }

                            int currentGridPenalty = calculateGridPenalty(r, c, size);
                            int currentGridPenalty2 = calculateGridPenalty2(r, c, size);
                            long currentHash = calculateHash(r, c, size);
                            {
                                int i = 1;
                                long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2R(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }

                            }
                            {
                                int i = 3;
                                long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2RRR(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }

                            }
                        }
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0]);
            if (comparator.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }

        Utils.debug("mean width", sumWidth / (double) maxDepth);

        return reverse2(toList(best));
    }

    private ArrayList beamsearch(int number, int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();

        HashSet usedHash = new HashSet();

        ArrayList[] states = new ArrayList[1 << 5];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            int gridPenalty = calculateGridPenalty();
            int gridPenalty2 = calculateGridPenalty2();
            State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2);
            states[0].add(e);

            usedHash.add(hash);

            best = e;
        }

        for (int depth = 0; depth < maxDepth; depth++) {
            if (states[0].size() == 0) {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
                continue;
            }

            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (comparator2.compare(currentState, best) < 0) {
                    best = currentState;
                }

                set(reverse2(toList(currentState)), baseDepth);

                int targetR = numberToR[number];
                int targetC = numberToC[number];

                int margin = 1;

                for (int size = 2; size <= 3; size++) {

                    int startR = Math.max(0, targetR - (size - 1) - margin);
                    int endR = Math.min(N - 1, targetR + margin);
                    int startC = Math.max(0, targetC - (size - 1) - margin);
                    int endC = Math.min(N - 1, targetC + margin);

                    for (int r = startR; r <= endR; r++) {
                        for (int c = startC; c <= endC; c++) {
                            if (!canRotate(r, c, size)) {
                                continue;
                            }
                            int currentGridPenalty = calculateGridPenalty(r, c, size);
                            int currentGridPenalty2 = calculateGridPenalty2(r, c, size);
                            long currentHash = calculateHash(r, c, size);

                            {
                                int i = 1;
                                long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2R(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }
                            }
                            {
                                int i = 3;
                                long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2RRR(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }
                            }

                        }
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0]);
            if (comparator2.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }

        return reverse2(toList(best));
    }

    private ArrayList beamsearchMargin2(int number, int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();

        HashSet usedHash = new HashSet();

        ArrayList[] states = new ArrayList[1 << 5];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            int gridPenalty = calculateGridPenalty();
            int gridPenalty2 = calculateGridPenalty2();
            State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2);
            states[0].add(e);

            usedHash.add(hash);

            best = e;
        }

        for (int depth = 0; depth < maxDepth; depth++) {
            if (states[0].size() == 0) {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
                continue;
            }

            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (comparator2.compare(currentState, best) < 0) {
                    best = currentState;
                }

                set(reverse2(toList(currentState)), baseDepth);

                int targetR = numberToR[number];
                int targetC = numberToC[number];

                int margin = 2;

                for (int size = 2; size <= 3; size++) {

                    int startR = Math.max(0, targetR - (size - 1) - margin);
                    int endR = Math.min(N - 1, targetR + margin);
                    int startC = Math.max(0, targetC - (size - 1) - margin);
                    int endC = Math.min(N - 1, targetC + margin);

                    for (int r = startR; r <= endR; r++) {
                        for (int c = startC; c <= endC; c++) {
                            if (!canRotate(r, c, size)) {
                                continue;
                            }
                            int currentGridPenalty = calculateGridPenalty(r, c, size);
                            int currentGridPenalty2 = calculateGridPenalty2(r, c, size);
                            long currentHash = calculateHash(r, c, size);

                            {
                                int i = 1;
                                long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2R(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }
                            }
                            {
                                int i = 3;
                                long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2RRR(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }
                            }

                        }
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0]);
            if (comparator2.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }

        return reverse2(toList(best));
    }

    private long calculateHashR(int r0, int c0, int size0) {
        long hash = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - c][c0 + 0 + r];
                hash ^= hashes[r0 + r][c0 + c][number];
            }
        }
        return hash;
    }

    private long calculateHashRR(int r0, int c0, int size0) {
        long hash = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - r][c0 + m - c];
                hash ^= hashes[r0 + r][c0 + c][number];
            }
        }
        return hash;
    }

    private long calculateHashRRR(int r0, int c0, int size0) {
        long hash = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + 0 + c][c0 + m - r];
                hash ^= hashes[r0 + r][c0 + c][number];
            }
        }
        return hash;
    }

    private long calculateHash(int r0, int c0, int size0) {
        long hash = 0;
        for (int r = r0; r < r0 + size0; r++) {
            for (int c = c0; c < c0 + size0; c++) {
                int number = rxcToNumber[r][c];
                hash ^= hashes[r][c][number];
            }
        }
        return hash;
    }

    private void updateNumberToRxc(int r0, int c0, int size0) {
        for (int r = r0; r < r0 + size0; r++) {
            for (int c = c0; c < c0 + size0; c++) {
                numberToR[rxcToNumber[r][c]] = r;
                numberToC[rxcToNumber[r][c]] = c;
            }
        }
    }

    public void set(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;
        for (int i = 0; i < list.size() && startIndex + i < moveHistory.size(); i++) {
            if (!isSameMove(moveHistory.get(startIndex + i), list.get(i))) {
                break;
            }
            startIndexMinus1 = startIndex + i;
        }
        for (; moveHistory.size() > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State state2 = list.get(i);
            next(state2.r, state2.c, state2.size, state2.dir, state2.numRotations);
        }
    }

    private boolean isSameMove(Move move, State state) {
        if (state.r != move.r || state.c != move.c || state.size != move.size || state.dir != move.dir || state.numRotations != move.numRotations) {
            return false;
        }
        return true;
    }

    public void set2(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;
        for (int i = 0; i < list.size() && startIndex + i < moveHistory.size(); i++) {
            if (!isSameMove(moveHistory.get(startIndex + i), list.get(i))) {
                break;
            }
            startIndexMinus1 = startIndex + i;
        }
        for (; moveHistory.size() > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State2 state2 = list.get(i);
            next(state2.r, state2.c, state2.size, state2.dir, state2.numRotations);
        }
    }

    private boolean isSameMove(Move move, State2 state) {
        if (state.r != move.r || state.c != move.c || state.size != move.size || state.dir != move.dir || state.numRotations != move.numRotations) {
            return false;
        }
        return true;
    }

    private ArrayList moveHistory = new ArrayList<>();

    public void next(int r, int c, int size, char dir, int numRotations) {
        moveHistory.add(new Move(r, c, size, dir, numRotations));
        for (int i = 0; i < numRotations; i++) {
            rotate(r, c, size, dir);
        }
    }

    public void previous() {
        Move lastMove = moveHistory.remove(moveHistory.size() - 1);
        int r = lastMove.r;
        int c = lastMove.c;
        int size = lastMove.size;
        char dir = lastMove.dir == 'L' ? 'R' : 'L';
        for (int i = 0; i < lastMove.numRotations; i++) {
            rotate(r, c, size, dir);
        }
    }

    private  ArrayList reverse2(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    private ArrayList toList(State state0) {
        ArrayList res = new ArrayList<>();
        for (State current = state0; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    private ArrayList toList(State2 state0) {
        ArrayList res = new ArrayList<>();
        for (State2 current = state0; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

}

class State implements Comparable {

    State parent;
    int r;
    int c;
    int size;
    char dir;
    int numRotations;
    int gridPenalty;
    int gridPenalty2;
    int sumRotatePenalty;

    public State(State parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
        this.gridPenalty = gridPenalty;
        this.sumRotatePenalty = sumRotatePenalty;
    }

    public State(State parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int gridPenalty2) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
        this.gridPenalty = gridPenalty;
        this.gridPenalty2 = gridPenalty2;
        this.sumRotatePenalty = sumRotatePenalty;
    }

    @Override
    public int compareTo(State o) {
        if (gridPenalty < o.gridPenalty) {
            return -1;
        }
        if (gridPenalty > o.gridPenalty) {
            return 1;
        }
        return 0;
    }

}

class State2 {

    State2 parent;
    int r;
    int c;
    int size;
    char dir;
    int numRotations;
    int gridPenalty;
    int gridPenalty2;
    int sumRotatePenalty;

    int distance;
    int c2;

    public State2(State2 parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int r2, int c2) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
        this.gridPenalty = gridPenalty;
        this.sumRotatePenalty = sumRotatePenalty;
        this.distance = r2;
        this.c2 = c2;
    }

    public State2(State2 parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int gridPenalty2, int r2, int c2) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
        this.gridPenalty = gridPenalty;
        this.gridPenalty2 = gridPenalty2;
        this.sumRotatePenalty = sumRotatePenalty;
        this.distance = r2;
        this.c2 = c2;
    }

}

class Move {
    int r;
    int c;
    int size;
    char dir;
    int numRotations;

    public Move(int r, int c, int size, char dir, int numRotations) {
        super();
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
    }
}

public class RotatingNumbers {

    public String[] findSolution(int N, int P, int[][] grid) {
        Solver solver = new Solver(N, P, grid);
        solver.solve();
        return solver.makeSolution();
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            int N = Integer.parseInt(br.readLine());
            int P = Integer.parseInt(br.readLine());
            int[][] grid = new int[N][N];
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    grid[r][c] = Integer.parseInt(br.readLine());
                }
            }

            RotatingNumbers prog = new RotatingNumbers();
            String[] ret = prog.findSolution(N, P, grid);

            System.out.println(ret.length);
            for (int i = 0; i < ret.length; i++) {
                System.out.println(ret[i]);
            }
            System.out.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class CollectionsUtils {
    private CollectionsUtils() {
    }

    public static final  void shuffle(ArrayList list, Random rng) {
        for (int i = list.size() - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            CollectionsUtils.swap(list, i, j);
        }
    }

    public static final  void shuffle(ArrayList list, XorShift rng) {
        for (int i = list.size() - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            CollectionsUtils.swap(list, i, j);
        }
    }

    public static final  void select0(ArrayList a, int l, int r, int k, Comparator comparator) {
        while (l < r) {
            int i = CollectionsUtils.partition3(a, l, r, comparator);
            if (i >= k)
                r = i - 1;
            if (i <= k)
                l = i + 1;
        }
    }

    public static final  void select(ArrayList a, int startInclusive, int endExclusive, int k, Comparator comparator) {
        select0(a, startInclusive, endExclusive - 1, k, comparator);
    }

    public static final > void select0(ArrayList a, int l, int r, int k) {
        while (l < r) {
            int i = CollectionsUtils.partition3(a, l, r);
            if (i >= k)
                r = i - 1;
            if (i <= k)
                l = i + 1;
        }
    }

    public static final > void select(ArrayList a, int startInclusive, int endExclusive, int k) {
        select0(a, startInclusive, endExclusive - 1, k);
    }

    public static final  void swap(ArrayList a, int i, int j) {
        T swap = a.set(i, a.get(j));
        a.set(j, swap);
    }

    public static final  void sort3(ArrayList a, int i, int j, int k, Comparator comparator) {
        if (comparator.compare(a.get(i), a.get(j)) > 0) {
            swap(a, i, j);
        }
        if (comparator.compare(a.get(i), a.get(k)) > 0) {
            swap(a, i, k);
        }
        if (comparator.compare(a.get(j), a.get(k)) > 0) {
            swap(a, j, k);
        }
    }

    public static final > void sort3(ArrayList a, int i, int j, int k) {
        if (a.get(i).compareTo(a.get(j)) > 0) {
            swap(a, i, j);
        }
        if (a.get(i).compareTo(a.get(k)) > 0) {
            swap(a, i, k);
        }
        if (a.get(j).compareTo(a.get(k)) > 0) {
            swap(a, j, k);
        }
    }

    public static final  int partition3(ArrayList a, int l, int r, Comparator comparator) {
        int center = (l + r) >>> 1;
        sort3(a, l, center, r, comparator);
        swap(a, center, r - 1);
        if (r - l < 3) {
            return l;
        }
        int r1 = r - 1;
        T v = a.get(r1);
        int i = l - 1;
        int j = r1;
        for (;;) {
            for (; comparator.compare(a.get(++i), v) < 0;) {
            }
            for (; comparator.compare(a.get(--j), v) > 0;) {
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, r1);
        return i;
    }

    public static final > int partition3(ArrayList a, int l, int r) {
        int center = (l + r) >>> 1;
        sort3(a, l, center, r);
        swap(a, center, r - 1);
        if (r - l < 3) {
            return l;
        }
        int r1 = r - 1;
        T v = a.get(r1);
        int i = l - 1;
        int j = r1;
        for (;;) {
            for (; a.get(++i).compareTo(v) < 0;) {
            }
            for (; a.get(--j).compareTo(v) > 0;) {
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, r1);
        return i;
    }

    public static final > int partition(ArrayList a, int l, int r) {
        int i = l - 1, j = r;
        T v = a.get(r);
        for (;;) {
            while (a.get(++i).compareTo(v) < 0)
                ;
            while (v.compareTo(a.get(--j)) < 0)
                if (j == l)
                    break;
            if (i >= j)
                break;
            swap(a, i, j);
        }
        swap(a, i, r);
        return i;
    }

    public static final  void sort(ArrayList a, int lInclusive, int rInclusive, Comparator comparator) {
        if (lInclusive >= rInclusive) {
            return;
        }
        int k = partition3(a, lInclusive, rInclusive, comparator);
        sort(a, lInclusive, k - 1, comparator);
        sort(a, k + 1, rInclusive, comparator);
    }

    public static final > void sort(ArrayList a, int lInclusive, int rInclusive) {
        if (lInclusive >= rInclusive) {
            return;
        }
        int k = partition3(a, lInclusive, rInclusive);
        sort(a, lInclusive, k - 1);
        sort(a, k + 1, rInclusive);
    }

    public static final  ArrayList reverse(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    public static final  ArrayList newReverse(ArrayList list) {
        ArrayList res = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            res.add(list.get(i));
        }
        return res;
    }

}

final class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

}

class Watch {
    private long start;

    public Watch() {
        init();
    }

    public double getSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}

class XorShift {
    private int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;

    public XorShift(long l) {
        x = (int) l;
    }

    public int nextInt() {
        final int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
        return w;
    }

    public long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

}