Implentation of a brute force algorithm for solving a 2x2 cube

2x2-solver.js

/**
 * @fileoverview Brute force algorithm for solving a 2x2 cube
 * @author LIOKA Ranarison Fiderana
 */

// These constants represent the corner pieces (see the picture in the comment)
const UBL = 0;
const UBR = 1;
const UFR = 2;
const UFL = 3;
const DFL = 4;
const DFR = 5;
const DBR = 6;
const DBL = 7;

// To represent the 2x2 cube state we will use two arrays:
// One for representing corner pieces position 'cp'
// ex: [UBL, UBR, UFR, UFL, DFL, DFR, DBR, DBL]
// And another one for representing the pieces orientation 'co'
// There can be 3 possible orientation values:
// '0' if correctly oriented (white or yellow on top/bottom)
// '1' if twisted clockwise
// '2' if twisted counter-clockwise
// ex: [0, 1, 2, 0, 0, 1, 2, 0],
// see SOLVED_CUBE and move states constant below for reference

class State {
    constructor(state) {
        this.cp = state.cp;
        this.co = state.co;
    }

    // moves are also represented as 'State', see the constants below
    // so to apply a move we just mix the two states with the following formula:
    // (Given two states 'A' and 'B')
    // for piece permutation
    // (A * B)(x).c = A(B(x).c).c
    // for piece orientation
    // (A * B)(x).o = (A(B(x).c).o + B(x).c) % 3

    applyMove(move) {
        let cp = [];
        let co = [];

        for (let i = 0; i < 8; i++) {
            cp[i] = this.cp[move.cp[i]];
            co[i] = this.co[move.cp[i]] + move.co[i];
            co[i] %= 3;
        }

        return new State({ cp, co });
    }

    // A state is 'solved' if all the pieces are at their initial position
    // And all the corners are correctly oriented (orientation value is 0)

    isSolved() {
        const cpSolved = SOLVED_STATE.cp.every((v, i) => this.cp[i] === v);
        const coSolved = SOLVED_STATE.co.every((v, i) => this.co[i] === v);

        return cpSolved && coSolved;
    }

    // this is a helper method for countng solved pieces
    // we will use this later for pruning

    solvedPiece() {
        let count = 0;

        for (let i = 0; i < 8; i++) {
            if (this.cp[i] == i && this.co[i] == 0) {
                count += 1;
            }
        }

        return count;
    }

    // static method for generating a state by applying all moves in the scramble string
    // ex: "R U R' U'"

    static fromScramble(scramble) {
        let state = SOLVED_STATE;

        for (const move of scramble.split(" ")) {
            state = state.applyMove(MOVES[move]);
        }

        return state;
    }
}

const SOLVED_STATE = new State({
    cp: [UBL, UBR, UFR, UFL, DFL, DFR, DBR, DBL],
    co: [0, 0, 0, 0, 0, 0, 0, 0],
});

// Move states constants

const U_STATE = new State({
    cp: [UFL, UBL, UBR, UFR, DFL, DFR, DBR, DBL],
    co: [0, 0, 0, 0, 0, 0, 0, 0],
});

const D_STATE = new State({
    cp: [UBL, UBR, UFR, UFL, DBL, DFL, DFR, DBR],
    co: [0, 0, 0, 0, 0, 0, 0, 0],
});

const R_STATE = new State({
    cp: [UBL, UFR, DFR, UFL, DFL, DBR, UBR, DBL],
    co: [0, 1, 2, 0, 0, 1, 2, 0],
});

const L_STATE = new State({
    cp: [DBL, UBR, UFR, UBL, UFL, DFR, DBR, DFL],
    co: [2, 0, 0, 1, 2, 0, 0, 1],
});

const F_STATE = new State({
    cp: [UBL, UBR, UFL, DFL, DFR, UFR, DBR, DBL],
    co: [0, 0, 1, 2, 1, 2, 0, 0],
});

const B_STATE = new State({
    cp: [UBR, DBR, UFR, UFL, DFL, DFR, DBL, UBL],
    co: [1, 2, 0, 0, 0, 0, 1, 2],
});

const MOVES = {
    U: U_STATE,
    D: D_STATE,
    R: R_STATE,
    L: L_STATE,
    F: F_STATE,
    B: B_STATE,
};

// fill double moves (2) and counter clockwise moves (')
for (const name in MOVES) {
    const move = MOVES[name];
    MOVES[name + "2"] = move.applyMove(move);
    MOVES[name + "'"] = move.applyMove(move).applyMove(move);
}

// To solve the cube we will use depth limited search
// if the solution is not found at the current depth we increase the search depth
// at each depth we loop through all 18 moves (U, U2, ...) and apply the moves to the current state
// then we recursively call the search algorithm until the cube is solved or the depth is 0

// NOTES:
// it has been proved that any 2x2 state can be solved in 11 moves or less
// the search can take longer to finish if the depth is greater than 8

class Solver {
    constructor() {
        this.solution = [];
    }

    solve(state, maxDepth) {
        for (let depth = 0; depth < maxDepth; depth++) {
            if (this.search(state, depth)) {
                return this.solution;
            }
        }

        return null;
    }

    search(state, depth) {
        if (depth === 0 && state.isSolved()) {
            return true;
        }

        if (depth === 0 || this.prune(state, depth)) {
            return false;
        }

        for (const move in MOVES) {
            const prevMove = this.solution[this.solution.length - 1];

            if (prevMove && !this.isMoveAvailable) {
                continue;
            }

            this.solution.push(move);
            const newState = state.applyMove(MOVES[move]);

            if (this.search(newState, depth - 1)) {
                return true;
            }

            this.solution.pop();
        }

        return false;
    }

    // helper functions

    // pruning filters non-solvable cube states within the current depth
    // for example it's impossible to solve a 2x2 with one move if there are less than 4 pieces solved

    prune(state, depth) {
        if (depth === 1 && state.solvedPiece() < 4) {
            return true;
        }

        if (depth === 2 && state.solvedPiece() < 2) {
            return true;
        }

        return false;
    }

    // we need to check if the current move is valid
    // repeated moves (ex: U U) and inversed (ex: U D U is the same as U2 D) are not allowed

    isMoveAvailable(prev, current) {
        const INVERSE_MOVES = {
            U: "D",
            R: "L",
            F: "B",
        };

        return prev[0] !== current[0] || INVERSE_MOVES[prev] !== current[0];
    }
}

// Main program

const scramble = "R U R' F2 U B2 L";
const state = State.fromScramble(scramble);
const solver = new Solver();

console.time("Duration");
const solution = solver.solve(state, 11);
console.timeEnd("Duration");

console.log(`Solution: ${solution.join(" ")}`);
console.log(`Move count: ${solution.length}`);

Here is the cube piece notation reference, pieces with U are located on the Up layer and pieces with D on the Down layer