A little Game (2)

In the last posts we created a digital version of the 15-puzzle I liked to play as a kid. Back then when we were playing the 15-puzzle there was one neat little trick. I would carefully remove two of the tiles sitting next to each other in a row and swap their position. This is a very good way to drive somebody crazy, because it makes the puzzle unsolvable.

Calculating the Parity

When I did that as a kid, I didn’t know why rearranging the tiles breaks the solvability. In the meantime I know that the solvability is related to the ‘parity’ of a pattern. The parity of a puzzle is either even or odd and never changes by valid moves. You can calculate it by adding the number of wrong pairs (n1) and the row where the empty Tile is (n2).

If this sum (n1+n2) is even then the puzzle can be solved. Whatever legal move you make this sum will stay an even value. So in order to annoy someone you just need to arrange the Tiles to create a negative parity. My ‘illegal’ move will either increase or decrease the value of n1 by one and create an odd parity. As a result the puzzle is no longer solvable.

Since we’re nice kids, we will make sure that the puzzle will always be solvable. So let’s add a method to the ViewModel that tests the solvability of a pattern:

  public static boolean isSolveable(List<Integer> tiles) {
        int n1 = 0;
        int n2 = 0;
        int empty = 15;
        for (int i = 0; i < tiles.size(); i++) {
            Integer a = tiles.get(i);
            if (a != 0) {
                for (int j = i; j < tiles.size(); j++) {
                    Integer b = tiles.get(j);
                    if (b != 0 && a > b) {
                        n1 += 1;
                    }
                }
            } else {
                empty = i;
            }
        }
        n2 = 1 + empty / 4;
        return (n1 + n2) % 2 == 0;
    }

And we’ll change the initGame method like this:

      private static Game initGame() {
        LinkedList<Integer> positions = new LinkedList<>();
        for (int i = 0; i < 16; i++) {
            positions.add(i);
        }
        Collections.shuffle(positions);
        while (!ViewModel.isSolveable(positions)) {
            Collections.shuffle(positions);
        }

        Tile empty = null;
        ArrayList<Tile> tiles = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                final Integer pos = positions.pop();
                final Tile tile = new Tile(i, j, pos);
                tiles.add(tile);
                if (pos == 0) {
                    empty = tile;
                }

            }
        }
        return new Game(empty, tiles.toArray(new Tile[16]));
    }

In the tradition of “fair minesweeper” we’ve now created a “fair 15-puzzle”.

Storing state

In the last part I promised to show how you can store the state of your app. We’ll use the StorageManager from three posts ago ago for this. Use the StorageManager in the Main class like this:

public static void onPageLoad() {
        Game game = initGame();
        String test = StorageManager.getStorage().get("game");

        if (test.isEmpty()) {
            game = initGame();
        } else {
            InputStream inputStream = new ByteArrayInputStream(test.getBytes(StandardCharsets.UTF_8));
            try {
                game = Models.parse(BrwsrCtx.findDefault(Game.class), Game.class, inputStream);
                List<Tile> tiles = game.getTiles();
                for (Tile tile : tiles) {
                    if (tile.getP()==0)game.setEmpty(tile);
                }
            } catch (IOException ex) {
                Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
                game = initGame();
            }

        }
        Models.applyBindings(game, "game");
    }

Since our Game logic is very simple there’s only one place where we manipulate the ViewModel and need to store state at the end of every move:

  @Function
    public static void move(Game game, Tile data) {
        if (data == game.getEmpty()) {
            return;
        }
        int x = data.getX();
        int y = data.getY();
        int x1 = game.getEmpty().getX();
        int y1 = game.getEmpty().getY();
        if ((Math.abs(x1 - x) == 1 && Math.abs(y1 - y) == 0)
                || (Math.abs(x1 - x) == 0 && Math.abs(y1 - y) == 1)) {
            data.setX(x1);
            data.setY(y1);
            game.getEmpty().setX(x);
            game.getEmpty().setY(y);
            StorageManager.getStorage().put("game", game.toString());
        }
    }

Reset the game

Now we’ll add a Button that allows us to reshuffle the tiles. For that we need a @Function:

    @Function
    public static void shuffle(Game game) {
        LinkedList<Integer> positions = new LinkedList<>();
        for (int i = 0; i < 16; i++) {
            positions.add(i);
        }
        Collections.shuffle(positions);
        while (!ViewModel.isSolveable(positions)) {
            Collections.shuffle(positions);
        }
        Tile empty = null;
        List<Tile> tiles = game.getTiles();
        for (Tile tile : tiles) {
            for (int i = 0; i < positions.size(); i++) {
                final Integer pos = positions.get(i);
                if (tile.getP() == pos) {
                    tile.setX(i % 4);
                    tile.setY(i / 4);
                }
                if (pos == 0) {
                    empty = tile;
                }

            }
        }
        game.setEmpty(empty);
        StorageManager.getStorage().put("game", game.toString());
    }

Now we need to add a Button to the UI:

 <div id="game" >
    <button id="shuffle-button" data-bind="click: shuffle" >Shuffle!</button>
        <div data-bind="foreach: tiles">
            <div class="tile" data-bind="text: p,css: 'tile-position-'+ (y()+1) +'-'+(x()+1), attr: { id: 'tile-'+ p() }, click: $parent.move"></div>
        </div>
</div>

That’s it for this time. We made the game a little less frustrating, we enabled peristent state, and we added a Function for reshuffling.

In the next blog entry we’ll make the HTML-Page responsive and add a score. So stay tuned!