A DFS search for a first grade puzzle

Puzzle.java

import java.util.*;
import java.util.function.Consumer;

public class Puzzle {
    static record Move(int pos1, int pos2, int score) {
        @Override
        public String toString() {
            return String.format("%d <-> %d", pos1, pos2);
        }
    }

    private static final String initialSetup = "CCSFSHHCFSHFHFCS"; // Cow Sheep Horse Feline
    private static final byte[] board;

    static {
        board = new byte[initialSetup.length()];
        for (var i = 0; i < initialSetup.length(); i++) {
            board[i] = switch (initialSetup.charAt(i)) {
                case 'C' -> (byte)0x1;
                case 'S' -> (byte)0x2;
                case 'H' -> (byte)0x4;
                case 'F' -> (byte)0x8;
                default -> throw new IllegalArgumentException("check setup");
            };
        }
    }

    private static int numMisplacements(byte[] pos) {
        return  numMisplacements(pos[0], pos[1], pos[2], pos[3]) +
                numMisplacements(pos[4], pos[5], pos[6], pos[7]) +
                numMisplacements(pos[8], pos[9], pos[10], pos[11]) +
                numMisplacements(pos[12], pos[13], pos[14], pos[15]) +
                numMisplacements(pos[0], pos[4], pos[8], pos[12]) +
                numMisplacements(pos[1], pos[5], pos[9], pos[13]) +
                numMisplacements(pos[2], pos[6], pos[10], pos[14]) +
                numMisplacements(pos[3], pos[7], pos[11], pos[15]);
    }

    private static int numMisplacements(byte b0, byte b1, byte b2, byte b3) {
        int n = 0;
        byte s = b0;

        if ((s & b1) > 0) {
            n++;
        }
        s |= b1;

        if ((s & b2) > 0) {
            n++;
        }
        s |= b2;

        if ((s & b3) > 0) {
            n++;
        }
        s |= b3;

        return n;
    }

    private static List<Move> availableMoves(byte[] pos) {
        var currMisplaced = numMisplacements(pos);
        if (currMisplaced == 0) {
            return Collections.emptyList();
        }

        var moves = new ArrayList<Move>();
        for (var s = 0; s < pos.length; s++) {
            for (var t = 0; t < pos.length; t++) {
                swap(pos, s, t);

                var m = numMisplacements(pos);
                if (m < currMisplaced) {
                    moves.add(new Move(s, t, m));
                }

                swap(pos, s, t);
            }
        }

        moves.sort(Comparator.comparingInt(Move::score));
        return moves;
    }

    private static void solve(byte[] pos, Consumer<List<Move>> reporter) {
        solveAux(new HashSet<Integer>(), new ArrayList<Move>(), pos, reporter);
    }

    private static void solveAux(Set<Integer> seen, List<Move> solution, byte[] pos, Consumer<List<Move>> reporter) {
        var h = Arrays.hashCode(pos);
        if (seen.contains(h)) {
            return;
        } else {
            seen.add(h);
        }

        var currMisplaced = numMisplacements(pos);
        if (currMisplaced == 0) {
            reporter.accept(solution);
            return;
        }

        var moves = availableMoves(pos);
        for (var move: moves) {
            swap(pos, move.pos1, move.pos2);
            solution.add(move);
            solveAux(seen, solution, pos, reporter);
            solution.remove(solution.size() - 1);
            swap(pos, move.pos1, move.pos2);
        }
    }

    private static void swap(byte[] pos, int p1, int p2) {
        var tmp = pos[p1];
        pos[p1] = pos[p2];
        pos[p2] = tmp;
    }

    public static void main(String[] args) {
        final var solutions = new ArrayList<List<Move>>();
        solve(board, (sol) -> solutions.add(new ArrayList<>(sol)));
        solutions.sort(Comparator.comparingInt(List::size));
        solutions.forEach((sol) -> System.out.printf("%d %s%n", sol.size(), sol));
    }
}

Solutions. Board is numbered 0 to 15, in row order, left to right

2 [3 <-> 6, 0 <-> 8]
3 [1 <-> 5, 6 <-> 11, 7 <-> 11]
4 [1 <-> 5, 3 <-> 6, 0 <-> 8, 3 <-> 7]
4 [1 <-> 5, 5 <-> 11, 6 <-> 7, 13 <-> 14]
4 [1 <-> 5, 5 <-> 11, 10 <-> 11, 13 <-> 14]
4 [5 <-> 11, 0 <-> 10, 5 <-> 6, 12 <-> 14]
4 [5 <-> 11, 0 <-> 10, 8 <-> 10, 12 <-> 13]
4 [5 <-> 11, 0 <-> 10, 12 <-> 13, 12 <-> 14]
4 [6 <-> 8, 3 <-> 12, 0 <-> 12, 10 <-> 14]
4 [6 <-> 8, 3 <-> 12, 1 <-> 13, 10 <-> 14]
4 [7 <-> 11, 1 <-> 6, 1 <-> 3, 13 <-> 14]