Review: Find the Mafia! for iPhone and iPad

Find the Mafia! by Experiware takes a well known problem in computer science, the maximum clique problem, and straightforwardly turns it into a puzzle game. At the moment it's more like a proof of concept than a proper game, but with some work it might become a lot more interesting.

The basic idea is: you have a group of people arranged in a circle. Some of them know each other, and are connected by a line. You need to find a group of people which all know each other. For whatever reason, the game calls this group the "mafia".

Right at the start, you are asked to set some parameters.
You can change the number of people, from 6 to 16, and the "mafia" size, from 3 to 6 (the latter is further limited by the number of people).

You can also set the number of puzzles to solve. If you complete all of them, at the end you'll be shown the total and average time. I find this a bit backwards since I won't know beforehand how many puzzles I will want to solve.
Also, it's quite odd to see the settings every time you play, and I think this is the main reason why the game looks like a prototype. It would probably make more sense to have a separate settings screen.

At the easiest setting (6,3), the solution can be spotted at first glance, and can be played by a child:

At the hardest setting (16,6), it looks like an intricate mess.

The default setting is (10,4), which seems easy enough to appeal to most people without being trivial.

One way to approach these puzzles is to simply look at the graph and attempt to "see" the solving pattern. This could be an interesting exercise, but can the solution be reached by using logic alone?

In general, the maximum clique problem is NP-complete, however we have extra information: we know the exact size of the clique, so we can use that to make some direct deductions.

Since there must be 4 people in the clique, we can start by excluding everyone that has less than three connections:

Now look at the person at the top left: he has exactly three connections, so to form a clique those three people should all be connected to each other. But they are not, so we can exclude the top left character as well.

Now the character below the last one has only two usable connections, so we can exclude him as well, and we are left with just four characters, which all know each other and are the solution to the puzzle.

Unfortunately the game doesn't allow to exclude characters, so I had to draw the crosses manually. I wish you could cycle through three states when you tap on a character (selected, excluded, unselected); this would allow for a more methodic approach, especially at the harder difficulty settings.

Is it possible to use this kind of reasoning for all puzzles? Probably not, because the puzzles are randomly generated and, according to the instructions, it's not guaranteed that the solution is unique. This is certainly something that I'd like to change: all puzzles should have a unique solution, and it would be great if the puzzles were not entirely random but selected to ensure that it's possible to reach the solution using logical deductions.

As things stand, this game is interesting for mathematically inclined people, but it feels incomplete. It's worth a look if the price drops again to free (it was a few days before this review), otherwise I'd wait for an update.

Summary

Nontrivialness	★★★☆☆
Logical Reasoning	★★☆☆☆
User Interface	★☆☆☆☆
Presentation	☆☆☆☆☆
Loading Time	★★★★★
Saves Partial Progress	✘
Status Bar	✔

©2013 Nicola Salmoria. Unauthorized use and/or duplication without express and written permission is strictly prohibited. Excerpts and links may be used, provided that full and clear credit is given to Nicola Salmoria and nontrivialgames.blogspot.com with appropriate and specific direction to the original content.