Fifteen Match

New flavour of the famous game

Comment

So, the task was to create a variation of the famous 15 puzzle. As we know, it is deceptively simple at its core and easy enough to implement. The difficulty lies only in checking the solvability of the puzzle. But this problem has already been solved by mathematicians and there is a fairly simple algorithm that allows you to check any position for solvability.

Idea

But how do you make an interesting new puzzle based on the 15 game? I started to think about it, and after a while I found an interesting solution. What if we displayd on the piece not its value, but some derivative value. I started by deciding to calculate for each piece the distance between its current position and its correct position. For a standard 4x4 field this gives us one of the numbers in the range [0...3]. Now all that's left to do is to use these numbers somehow. I decided that these numbers can be color-coded, so the original field will be represented as a multicolored mosaic. So the basic idea crystallized and I got down to design.

Design

The first thing I did was to make a small prototype in SwiftUI, to make sure that the idea worked and was attractive. Now it was up to the design, which I drew in Sketch. Initially, I had one screen of the game turned into a full-fledged puzzle game. I decided to make several different levels based on the above idea.

In terms of design, I decided that I would have several different types of pieces (square, round, irregularly shaped, different sizes, etc.). I also thought about having levels combined into collections, each using one type of piece. For each collection, I decided to use a different color palette of five colors. These colors would encode some of the characteristics of the piece (color, size), and would also be used to create a background gradient.

When creating the design I immediately expected that the game would support vertical and horizontal orientation. That's why I drew the main screens for all the necessary sizes right away. This then helps me properly layout the screens in Flutter.

Game logic

The application is built according to the classic Model-View-Controller scheme. The main game field is represented as a usual array. The index of an array element determines the correct position of the piece, and the value of the element is its current position. For standard 4x4 field this will look like the following:

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

Indexing starts from zero, X and Y coordinates are calculated for a particular piece dynamically using the formulas:

  // Size of the playing field
  int gridSize = 4

  // Current coordinates of the piece
  int X = pieces[index] % gridSize
  int Y = pieces[index] ~/ gridSize

All game logic is encapsulated in the Game object, which is responsible for both initial generation of position, checking their solvability, moving a piece, as well as keeping track of the number of moves, elapsed time and checks for the end of the game.

The solvability check is done by the classical algorithm with counting of the number of inversions. An inversion is when the value of the piece is less than its neighbor to the right, i.e. the larger element is to the left of the smaller one. An empty token (15 in our case) does not count. For a completely solved puzzle the number of inversions is zero.

  // A completely solved puzzle
  pieces = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, __]
  inversions(pieces) -> 0

  // The piece "11" is moved to an empty position (the puzzle is solvable)
  pieces = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, __, 12, 13, 14, 11]
  inversions(pieces) -> 1

  // Exchanged pieces "13" and "14" (puzzle unsolvable)
  pieces = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 13, __]
  inversions(pieces) -> 1

Knowing the number of inversions we can check whether the given position is solvable in principle or not. To do this, we need to know the dimensionality of the playing field and the number of the row in which the empty piece is located. The number of the row is counted from the bottom starting from one.

If the size of the playing field is even, the puzzle is solvable if the number of inversions is even and the number of the row in which the empty piece is located is odd and vice versa.

   int gridSize = 4
   int inversion = 2 // even
   int rowEmptyFromBottom = 1 // odd

   // Check the position solvability for an even numbered grid
   bool isSolvable
   if (gridSize % 2 == 0) {
        if (rowEmptyFromBottom % 2 == 1) {
            isSolvable = (inversions % 2 == 0)
        } else {
            isSolvable = (inversions % 2 == 1)
        }
   }

   // Puzzle solvable
   isSolvable -> true

If the size of the playing field is odd, the position of the empty piece does not matter, the puzzle is always solvable if the number of inversions is even.

   int gridSize = 3
   int inversion = 2 // even

   // Check if the position is solvable for an odd number of inversions
   bool isSolvable
   if (gridSize % 2 == 1) {
     isSolvable = (inversions % 2 == 0)
   }

   // Puzzle solvable
   isSolvable -> true

Using this algorithm we can both check any position for solvability and generate any pre-solvable position.

Levels

To make the game more interesting, I added the concept of collections, each containing several levels. As mentioned above, I decided to encode the value of the piece with colors and sizes depending on the distance from the current position of the piece to its correct position.

The common characteristics of the level, which include the color palette and piece type, are stored in the collection. The levels themselves contain only the initial arrangement of the pieces. In order to separate levels by difficulty, I also introduced, in addition to the 4x4 field, support for 3x3 and 5x5 dimensions. Also, for easier levels, I show the numerical values of the pieces. All of this additional information is stored in the level description.

The goal of the game, therefore, is to solve the initial position. In the process of solving the puzzle, to make it easier for the user, those pieces that are in their place are shown with their numerical value. As soon as the level is solved, it is marked as passed and the player is invited to move on to the next level.

Typography and Color Palettes

All text styles are placed in a separate style file. I have defined the required semantic styles for all text types used in the app. And this greatly simplified both the text widget code itself, and the overall management of styles.

With colors, the situation is a little different. Since I decided to support collections that themselves define color palettes for levels, it made no sense to put them in a separate general style file, as I did with texts. Color management was completely given to the collection itself. The only exception is the two universal colors - black and white, which are used for text and icons, depending on whether the theme is light or dark in a particular collection. These colors have been specified directly in the program code.

Supported Devices

The app was primarily written for smartphones, and both in portrait and landscape orientation. When you change the orientation, the user interface is automatically rebuilt. Also, given the variety of screen sizes on smartphones, the app tries to adjust to different sizes, while remaining pleasing to the eye and comfortable to play.

Built With

Share this project:

Updates