problem https://github.com/kosakkun/MM-Tester/tree/master/SlidingPuzzle

Approach  貪欲法を使いました。現在の状態から、できるだけ良さそうな状態を見つけるのに、 beam search を使いました。
  • 評価関数 : 複数のセルのマンハッタン距離の和 同じなら 全部のセルのマンハッタン距離の和
    • 選ぶ複数のセルの順番はこんな感じ。slidingpazzle
  • beam search
    • 深さ : 最大20
    • 幅 : 最大100
  • beam search とマンハッタン距離の組み合わせは、現在の状態より悪い状態にしてからより良い状態にしにくいので(悪い状態が beam 幅内から除かれる)、対策を考えたがあまりうまくいかなかった。
    • 対策1 : 評価関数を 3x3 のセルが何手で順番通りになるか(一番大きい数字が空と仮定)の和に変えたら、評価関数が0になっても全部正しい位置になってなかったw。
    • 対策2 : 現在の状態より良い状態のみ beam 幅内に含むようにしようとして、 beam search 中に beam search してみたけど、悪い状態が beam 幅内から除かれるのを、 beam search 中の beam search に先送りしただけだった。




seed目安my
1(4x4)3244
2(5x5)154102
3(6x6)256188
4(7x7)2597248
5(8x8)3862412
6(9x9)642
7(10x10)
888

source code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class SlidingPuzzle {
    private int R;
    private int C;
    private int ignoreR;
    private int ignoreC;
    private int[][] board;
    private IntSet rxcToNumber;

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

    private static final int[] dr = new int[] { -1, 0, 0, 1, };
    private static final int[] dc = new int[] { 0, -1, 1, 0, };

    private int spaceR;
    private int spaceC;

    private int score;
    private int partScore;

    private int[] moveHistory = new int[1 << 20];
    private int turn;

    private HashSet used2 = new HashSet<>();
    private long[][][] hashes;
    private long hash;

    private boolean[] isTargetNumber;

    private LinkedList> targetNumbersList = new LinkedList<>();

    public static void main(String[] args) {
        new SlidingPuzzle().run();
    }

    private void run() {
        read();
        solve();
        write();
    }

    private void solve() {

        score = calculateScore();
        partScore = calculatePartScore();

        for (; watch.getSecond() < 9.5;) {

            if (partScore > 0) {
                ArrayList moves = beamsearch(20, 100, turn);
                if (moves == null) {
                    Utils.debug("moves == null");
                    continue;
                }
                for (State move : moves) {
                    next(move.r, move.c);
                }
            }

            if (partScore == 0) {
                updateIgnoreRC();

                List targetNumbers = targetNumbersList.pollFirst();
                if (targetNumbers == null) {
                    break;
                }
                for (Integer targetNumber : targetNumbers) {
                    isTargetNumber[targetNumber.intValue()] = true;
                }

                score = calculateScore();
                partScore = calculatePartScore();
                hash = 0;
            } else {
            }
        }
    }

    private void greedy() {
        for (;;) {
            boolean update = false;
            for (int d = 0; d < dr.length; d++) {
                for (int length = 1;; length++) {
                    int nr = spaceR + length * dr[d];
                    int nc = spaceC + length * dc[d];
                    if (nr <= ignoreR || nr >= R) {
                        break;
                    }
                    if (nc <= ignoreC || nc >= C) {
                        break;
                    }

                    int before = calculateScore();

                    next(nr, nc);

                    int after = calculateScore();

                    if (after < before) {
                        update = true;
                    } else {
                        previous();
                    }
                }
            }

            if (!update) {
                break;
            }
        }
    }

    private void updateIgnoreRC() {
        for (int r = ignoreR + 1; r < R - 2; r++) {
            boolean ok = true;
            for (int c = 0; c < C; c++) {
                if (!isTargetNumber[r * C + c]) {
                    ok = !true;
                }
            }
            if (ok) {
                ignoreR = r;
            }
        }
        for (int c = ignoreC + 1; c < C - 2; c++) {
            boolean ok = true;
            for (int r = 0; r < R; r++) {
                if (!isTargetNumber[r * C + c]) {
                    ok = !true;
                }
            }
            if (ok) {
                ignoreC = c;
            }
        }
    }

    private ArrayList beamsearch(int maxDepth, int maxBeamWidth, int currentTurn) {
        ArrayList currents = new ArrayList<>();
        ArrayList nexts = new ArrayList<>();
        State best = null;

        used2.clear();
        used2.add(hash);

        State state0 = new State(null, spaceR, spaceC, score, partScore, 0);
        currents.add(state0);

        depthLoop: for (int depth = 0; depth < maxDepth; depth++) {
            if (watch.getSecond() > 59.5) {
                Utils.debug("depth", depth);
                break;
            }
            if (currents.size() == 0) {
                break;
            }
            int beamWidth = Math.min(maxBeamWidth, currents.size());
            Collections.sort(currents);
            for (int beam = 0; beam < beamWidth; beam++) {
                State currentState = currents.get(beam);

                if (currentState != state0) {
                    if (best == null || currentState.compareTo(best) < 0) {
                        best = currentState;
                    }
                    if (currentState.score < 1e-9) {
                        break depthLoop;
                    }
                }

                set(reverse(toList(currentState)), currentTurn);

                int r = currentState.r;
                int c = currentState.c;
                assert spaceR == r;
                assert spaceC == c;
                for (int d = 0; d < dr.length; d++) {
                    for (int length = 1;; length++) {
                        int nr = r + length * dr[d];
                        int nc = c + length * dc[d];
                        if (nr <= ignoreR || nr >= R) {
                            break;
                        }
                        if (nc <= ignoreC || nc >= C) {
                            break;
                        }

                        next(nr, nc);

                        if (used2.add(hash)) {
                            State e = new State(currentState, nr, nc, score, partScore, currentState.numMoves + 1);
                            nexts.add(e);
                        }

                        previous();
                    }
                }

            }
            {
                ArrayList swap = currents;
                currents = nexts;
                nexts = swap;
            }
            nexts.clear();
        }

        for (; turn > currentTurn;) {
            previous();
        }

        if (best == null) {
            return null;
        }

        return reverse(toList(best));

    }

    public static final ArrayList toList(State state0) {
        ArrayList list = new ArrayList<>();
        for (State state = state0; state.parent != null; state = state.parent) {
            list.add(state);
        }
        return list;
    }

    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;
    }

    private int calculateScore() {
        int score = 0;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                score += calculateScore(r, c);
            }
        }
        return score;
    }

    private int calculatePartScore() {
        int score = 0;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                score += calculatePartScore(r, c);
            }
        }
        return score;
    }

    private int calculateScore(int r, int c) {

        int number = getNumber(r, c);
        if (number == R * C - 1) {
            return 0;
        }
        int nr = number / C;
        int nc = number % C;
        int diff = Math.abs(r - nr) + Math.abs(c - nc);
        return diff;
    }

    private int calculatePartScore(int r, int c) {

        int number = getNumber(r, c);
        if (number == R * C - 1) {
            return 0;
        }
        if (!isTargetNumber[number]) {
            return 0;
        }
        int nr = number / C;
        int nc = number % C;
        int diff = Math.abs(r - nr) + Math.abs(c - nc);
        return diff;
    }

    private void set(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;
        for (int i = 0; i < list.size() && startIndex + i < turn; i++) {
            int v = moveHistory[startIndex + i];
            int r0 = (v >>> 8) & ((1 << 8) - 1);
            int c0 = (v >>> 0) & ((1 << 8) - 1);

            State state = list.get(i);
            if (state.r == r0 && state.c == c0) {
                startIndexMinus1 = startIndex + i;
                continue;
            }
            break;
        }
        for (; turn > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State state2 = list.get(i);
            next(state2.r, state2.c);
        }
    }

    private void previous() {
        int v = moveHistory[--turn];
        int sr = (v >>> 24) & ((1 << 8) - 1);
        int sc = (v >>> 16) & ((1 << 8) - 1);
        int r0 = (v >>> 8) & ((1 << 8) - 1);
        int c0 = (v >>> 0) & ((1 << 8) - 1);
        move(sr, sc);

    }

    private void next(int r0, int c0) {
        assert r0 >= 0 && r0 < R;
        assert c0 >= 0 && c0 < C;
        moveHistory[turn++] = (spaceR << 24) | (spaceC << 16) | (r0 << 8) | (c0);
        move(r0, c0);
    }

    private void move(int r0, int c0) {
        if (c0 == spaceC && r0 != spaceR) {
            if (r0 < spaceR) {
                for (int r = spaceR; r > r0; r--) {
                    swap2(r, c0, r - 1, c0);
                }
            } else {
                for (int r = spaceR; r < r0; r++) {
                    swap2(r, c0, r + 1, c0);
                }
            }
            spaceR = r0;
            spaceC = c0;
        } else if (c0 != spaceC && r0 == spaceR) {
            if (c0 < spaceC) {
                for (int c = spaceC; c > c0; c--) {
                    swap2(r0, c, r0, c - 1);
                }
            } else {
                for (int c = spaceC; c < c0; c++) {
                    swap2(r0, c, r0, c + 1);
                }
            }
            spaceR = r0;
            spaceC = c0;
        } else {
            Utils.debug(r0, c0, spaceR, spaceC);
            throw new AssertionError();
        }
    }

    private void swap2(int r, int c, int r2, int c2) {
        score -= calculateScore(r, c);
        score -= calculateScore(r2, c2);
        partScore -= calculatePartScore(r, c);
        partScore -= calculatePartScore(r2, c2);
        if (isTargetNumber[getNumber(r, c)]) {
            hash ^= hashes[r][c][getNumber(r, c)];
        }
        if (isTargetNumber[getNumber(r2, c2)]) {
            hash ^= hashes[r2][c2][getNumber(r2, c2)];
        }
        swapRxc(r, c, r2, c2);

        if (isTargetNumber[getNumber(r, c)]) {
            hash ^= hashes[r][c][getNumber(r, c)];
        }
        if (isTargetNumber[getNumber(r2, c2)]) {
            hash ^= hashes[r2][c2][getNumber(r2, c2)];
        }

        score += calculateScore(r, c);
        score += calculateScore(r2, c2);
        partScore += calculatePartScore(r, c);
        partScore += calculatePartScore(r2, c2);
    }

    private void swap(int[][] board, int r0, int c0, int r2, int c2) {
        int swap = board[r0][c0];
        board[r0][c0] = board[r2][c2];
        board[r2][c2] = swap;
    }

    private void print() {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                System.err.format("%3d", 1 + getNumber(r, c));
            }
            System.err.println();
        }
        System.err.println();
    }

    private Point searchPoint() {
        for (int index = 0; index < Math.max(R, C); index++) {
            for (int r = index; r < R - 2; r++) {
                for (int c = 0; c < C; c++) {
                    if (board[r][c] != r * C + c) {
                        if (board[r][c] != R * C - 1) {
                            return new Point(r, c);
                        }
                    }
                }
            }
            for (int c = index; c < C - 2; c++) {
                for (int r = 0; r < R; r++) {
                    if (board[r][c] != r * C + c) {
                        if (board[r][c] != R * C - 1) {
                            return new Point(r, c);
                        }
                    }
                }
            }
        }

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (board[r][c] != r * C + c) {
                    if (board[r][c] != R * C - 1) {
                        return new Point(r, c);
                    }
                }
            }
        }

        return null;
    }

    private void read() {
        try (Scanner sc = new Scanner(System.in)) {
            R = sc.nextInt();
            C = sc.nextInt();
            Utils.debug("R", R, "C", C);
            board = new int[R][C];
            rxcToNumber = new IntSet(R * C);
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    board[r][c] = sc.nextInt();
                    if (board[r][c] >= 0) {
                        board[r][c]--;
                    } else {
                        spaceR = r;
                        spaceC = c;
                        board[r][c] = R * C - 1;
                    }
                    rxcToNumber.add(board[r][c]);
                    assert r * C + c == rxcToNumber.indexOf(board[r][c]);
                }
            }
            for (int r = 0; r < R; r++) {
            }

            initHash();

            isTargetNumber = new boolean[R * C];

            for (int r = R - 1, c = C - 2, length = 1; r >= 0 || c >= 0; r--, c--, length++) {
                if (r >= 0) {
                    ArrayList targetNumbers = new ArrayList<>();
                    for (int i = 0, c2 = C - 1; c2 >= 0 && i < length; i++, c2--) {
                        targetNumbers.add(r * C + c2);
                    }
                    if (targetNumbers.size() >= 8) {
                        targetNumbersList.addFirst(targetNumbers.subList(targetNumbers.size() / 2, targetNumbers.size()));
                        targetNumbersList.addFirst(targetNumbers.subList(0, targetNumbers.size() / 2));
                    } else {
                        targetNumbersList.addFirst(targetNumbers);
                    }
                }
                if (c >= 0) {
                    ArrayList targetNumbers = new ArrayList<>();
                    for (int i = 0, r2 = R - 1; r2 >= 0 && i < length; i++, r2--) {
                        targetNumbers.add(r2 * C + c);
                    }
                    if (targetNumbers.size() >= 8) {
                        targetNumbersList.addFirst(targetNumbers.subList(targetNumbers.size() / 2, targetNumbers.size()));
                        targetNumbersList.addFirst(targetNumbers.subList(0, targetNumbers.size() / 2));
                    } else {
                        targetNumbersList.addFirst(targetNumbers);
                    }
                }
            }
            targetNumbersList.pollLast();
            isTargetNumber[R * C - 1] = true;

            List targetNumbers = targetNumbersList.pollFirst();
            for (Integer targetNumber : targetNumbers) {
                isTargetNumber[targetNumber.intValue()] = true;
            }

            ignoreR = -1;
            ignoreC = -1;

            score = calculateScore();

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private void initHash() {
        hashes = new long[R][C][R * C];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                for (int n = 0; n < R * C; n++) {
                    long l = (long) rng.nextInt();
                    long l2 = (long) rng.nextInt();
                    hashes[r][c][n] = (l << 32) | (l2);
                }
            }
        }
    }

    private void write() {

        System.out.println(turn);
        for (int t = 0; t < turn; t++) {
            int v = moveHistory[t];
            int r = (v >>> 8) & ((1 << 8) - 1);
            int c = (v >>> 0) & ((1 << 8) - 1);
            System.out.println(r + " " + c);
        }
        System.out.flush();
    }

    private int getNumber(int r, int c) {
        return rxcToNumber.get(r * C + c);
    }

    private int getRxc(int number) {
        return rxcToNumber.indexOf(number);
    }

    private void swapNumber(int number, int number2) {
        int rxc = getRxc(number);
        int rxc2 = getRxc(number2);
        rxcToNumber.swap(rxc, rxc2);
        assert rxc == getRxc(number2);
        assert rxc2 == getRxc(number);
    }

    private void swapRxc(int r, int c, int r2, int c2) {
        int rxc = r * C + c;
        int rxc2 = r2 * C + c2;
        int number = getNumber(r, c);
        int number2 = getNumber(r2, c2);
        rxcToNumber.swap(rxc, rxc2);
        assert number2 == getNumber(r, c);
        assert number == getNumber(r2, c2);
    }

}

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 double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

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

}

class Point {
    int r;
    int c;

    public Point(int r, int c) {
        super();
        this.r = r;
        this.c = c;
    }

}

class State implements Comparable {
    State parent;
    int r;
    int c;
    int partScore;
    int score;
    int numMoves;
    double random;

    public State(State parent, int r, int c, int score, int partScore, int numMoves) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.score = score;
        this.partScore = partScore;
        this.numMoves = numMoves;
        random = Math.random();
    }

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

class IntSet {
    private static final int EMPTY = -1;
    private int size;
    private int[] indexToValue;
    private int[] valueToIndex;

    public IntSet(int capacity) {
        this.size = 0;
        indexToValue = new int[capacity];
        valueToIndex = new int[capacity];
        Arrays.fill(valueToIndex, EMPTY);
    }

    public boolean add(int value) {
        if (valueToIndex[value] != EMPTY) {
            return false;
        }
        indexToValue[size] = value;
        valueToIndex[indexToValue[size]] = size;
        size++;
        return true;
    }

    public boolean remove(int index) {
        if (size == 0) {
            return false;
        }
        assert index < size;
        int swap = indexToValue[index];
        indexToValue[index] = indexToValue[size - 1];
        indexToValue[size - 1] = swap;

        valueToIndex[indexToValue[index]] = index;
        valueToIndex[indexToValue[size - 1]] = EMPTY;

        size--;
        return true;
    }

    public boolean removeValue(int value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public void swap(int index, int index2) {
        assert index < size;
        assert index2 < size;

        int swap = indexToValue[index];
        indexToValue[index] = indexToValue[index2];
        indexToValue[index2] = swap;

        valueToIndex[indexToValue[index]] = index;
        valueToIndex[indexToValue[index2]] = index2;

    }

    public int get(int index) {
        assert index < size;
        return indexToValue[index];
    }

    public int indexOf(int value) {
        return valueToIndex[value];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public void clear() {
        for (; size() > 0;) {
            remove(0);
        }
    }

    public boolean contains(int value) {
        return indexOf(value) != EMPTY;
    }

}