How can I check if 8puzzle is solvable

Question

I'm trying to create a 3x3 puzzle with random order but which is solvable. The algorithm I copied online I understood how it works but it doesn't work for me because I have an array of 9 elements and not a 3x3 matrix (3-D array).

This function create the random order and plays the game only if its solvable:

function restart() {
    // create new random order
    randomOrder = realOrder
        .map(value => ({ value, sort: Math.random() }))
        .sort((a, b) => a.sort - b.sort)
        .map(({ value }) => value)
    if (verifyIfSolved(randomOrder)) {
        alert("Solved")
        restart()
    }
    else {
        if (isSolvable(randomOrder)) {
            play(randomOrder)
        }
    }
}

The isSolvable function:

// check if the order is solvable
function isSolvable(arr) {
    return (getInversion(arr) % 2 == 0)
}

The getInversion function to get the number of inversions:

// count the number of inversions in the order
function getInversion(arr) {
    let inversionCount = 0
    for (let i = 0; i < 2; i++) {
        for (let j = i + 1; j < 3; j++) {
            // 0 is used for empty space
            if (arr[j][i] > 0 && arr[j][i] > arr[i][j]) {
                inversionCount += 1
            }
        }
    }
    return inversionCount
}

Answer 1

You'll need:

• to let your indices go up to index 8
• to adapt the empty-space check, since you are using 9 for it (and not 0 as stated in the comment)
• to address your array as a 1D array, not 2D

function getInversion(arr) {
    let inversionCount = 0
    for (let i = 0; i < 8; i++) {
        for (let j = i + 1; j < 9; j++) {
            if (arr[i] < 9 && arr[i] > arr[j]) {
                inversionCount += 1;
            }
        }
    }
    return inversionCount;
}