Difficult to solve the phaser sliding puzzle as so

Question

Im trying to create the phaser examples game sliding puzzle

Live example is demonstrated here

But in the output game, some parts of the original image is missing. So it is difficult to solve the puzzle. I am suspecting the algorithm of cutting the image to pieces is not correct.
The code for pieces is ,

function prepareBoard() {

    var piecesIndex = 0,
        i, j,
        piece;

    BOARD_COLS = Math.floor(game.world.width / PIECE_WIDTH);
    BOARD_ROWS = Math.floor(game.world.height / PIECE_HEIGHT);

    piecesAmount = BOARD_COLS * BOARD_ROWS;

    shuffledIndexArray = createShuffledIndexArray();

    piecesGroup = game.add.group();

    for (i = 0; i < BOARD_ROWS; i++)
    {
        for (j = 0; j < BOARD_COLS; j++)
        {
            if (shuffledIndexArray[piecesIndex]) {
                piece = piecesGroup.create(j * PIECE_WIDTH, i * PIECE_HEIGHT, "background", shuffledIndexArray[piecesIndex]);
            }
            else { //initial position of black piece
                piece = piecesGroup.create(j * PIECE_WIDTH, i * PIECE_HEIGHT);
                piece.black = true;
            }
            piece.name = 'piece' + i.toString() + 'x' + j.toString();
            piece.currentIndex = piecesIndex;
            piece.destIndex = shuffledIndexArray[piecesIndex];
            piece.inputEnabled = true;
            piece.events.onInputDown.add(selectPiece, this);
            piece.posX = j;
            piece.posY = i;
            piecesIndex++;
        }
    }

}

function createShuffledIndexArray() {

    var indexArray = [];

    for (var i = 0; i < piecesAmount; i++)
    {
        indexArray.push(i);
    }

    return shuffle(indexArray);

}

function shuffle(array) {

    var counter = array.length,
        temp,
        index;

    while (counter > 0)
    {
        index = Math.floor(Math.random() * counter);

        counter--;

        temp = array[counter];
        array[counter] = array[index];
        array[index] = temp;
    }

    return array;
    
}

Please anyone have any idea ? Please share any algorithm to correctly cut the pieces.

Thanks in advance iijb

Answer 1

This is the classic 15puzzle because it traditionally has a 4x4 grid with 1 tile missing (4x4-1=15 tiles). However the puzzle can practically be any grid size (4x3, 5x4, 6x6 etc).

You're using a .destIndex property to keep track of their position, but you could just give each tile a numbered index. I think that way it's easier because when all the tiles are ordered the puzzle is solved and it would also help the check-if-solvable-algorithm.

With these kind of sliding tile puzzles, there are two things to consider which are a little tricky, especially the 2nd point:

1. There is always one tile missing because that is the empty spot that the player can use to slide tiles into. Most commonly, the missing tile is the bottom-right tile of the image.

In your algorithm the blank tile is always the top-left tile of the image. This is unusual and players might not expect that, however in theory it doesn't really matter and you could make a workable puzzle that way. You then keep track of the empty tile in code by value 1 (or maybe 0 for zero-indexed) because it's the first tile.

2. Some configurations are unsolvable, i.e. not every random scrambled tiles situation can be solved by sliding the tiles around.

A puzzle is solvable when the number of inversions (switches) needed to solve it is an even number, not odd. So count the number of pairs where a bigger number is in front of a smaller one (=one inversions). For example in a 3x3 puzzle with the bottom-right tile missing:

5 3 4
2 6 1
8 7

In array it looks like this [5,3,4,2,6,1,8,7,9], so count pairs which are 5-3, 5-4, 5-2, 5-1, 3-2 3-1, 4-2 4-1, 2-1, 6-1, 8-7. This equals 11 pairs, so 11 inversions are needed. This is not an even number, thus this configuration is unsolvable. Btw note that the missing tile has internally the highest possible number, which is 9 in this case.

You can use this method to detect a unsolvable puzzle. All you need to do to make it solvable again is switch any two tiles, so for example the top first two tiles (so 5 and 3 in the example). When the number of switches needed is an even number, it's already solvable and you don't need to do anything.

I've made similar puzzle games, you can see the source code here to see how it works:

Photoscramble v2 (download incl Delphi source)
Photoscramble v1 (download incl BlitzBasic source)