Find valid positions in a board

Question

I'm looking at solving the Puzzle 15 game. Example.

Basically at each position, valid positions can only come vertically or horizontally. I am looking for an algorithm that can determine it at any given position in a board of 16 elements, 4 by 4.

Currently I have the positions hard coded

var rules = [
    { "0": [1, 4]},{ "1": [0, 2, 5] },{ "2": [1, 3, 6] },{ "3": [2, 7] },
    { "4": [0, 5, 8] },{ "5": [1, 4, 6, 9] },{ "6": [2, 5, 7, 10] },{ "7": [3, 6, 11] },
    { "8": [4, 9, 12] },{ "9": [5, 8, 10, 13]},{ "10": [6, 9, 11, 14] },{ "11": [7, 10, 15] },
    { "12": [8, 13] },{ "13": [12, 9, 14] },{ "14": [10, 13, 15] },{ "15": [11, 14] },
]

For example at position "0", only positions [1, 4] are valid to move from.

 [ _,  1,   2,  3 ]
 [ 4,  5,   6,  7 ]
 [ 8,  9,  10, 11 ]
 [ 0,  12, 13, 14 ]

What's a better way?

Depends. You may encode the rules you used to get the hard coded values i.e. a position to move from is valid if it's a horizontal or vertical neighbour and it's on the board. But for a fixed sized board building a lookup table (by hand or by algorithms) might be a good idea: it may improve readability or performance especially when the rules are far too complex or expensive to evaluate in every step. — BeyelerStudios
It's called 8 puzzle and once you implement it for 8 cells then that will also work for 15 or any size. btw this is not the right way to go. — Luai Ghunim

blaz pecnik blaz pecnik · Accepted Answer · 2017-12-16T12:35:11

I'm not sure if I 100% understand your problem, but i hope this helps.

If I understand correctly:

You need a function that will tell you, which cells can be moved.
A cell can be moved only if its a direct neighbor of the empty cell.

i would suggest something like this:



    // game grid, empty-cell = -1
    const grid = [
        [ 1,  2,  3,  4],
        [ 5,  6,  7,  8],
        [ 9, 10, 11, 12],
        [13, 14, -1, 15],
    ]

    // Gets value from grid, return null when outside of array
    function getCellValue(grid, row, col) {
        if (grid[row] === undefined) return null;
        if (grid[row][col] === undefined) return null;
        return grid[row][col];
    }

    // Returns array of [row, col] cells,
    // that are direct neighbors of the empty cell
    function getEmptyCellNeighbors(grid) {
        let cells = [];
        grid.forEach((cols, row) => {
            cols.forEach((value, col) => {
                if (getCellValue(grid, row - 1, col) === -1) cells.push([row, col]);
                if (getCellValue(grid, row + 1, col) === -1) cells.push([row, col]);
                if (getCellValue(grid, row, col - 1) === -1) cells.push([row, col]);
                if (getCellValue(grid, row, col + 1) === -1) cells.push([row, col]);
            })
        })
        return cells;
    }

    // The empty cell(-1) is at[row = 3, col = 2]
    // You can move  11, 14, 15 to the empty cell.
    // The cuntion will return the[row, col] of cells 11, 14 & 15

    console.log(getEmptyCellNeighbors(grid));
    // returns => [
    //     [2, 2], // 11
    //     [3, 1], // 14
    //     [3, 3], // 15
    // ]

Find valid positions in a board

1 Answers