Grant's Review Corner: Volume 2

I'm sorry to post this on a Monday and risk taking attention away from today's Monday Mutant, but I felt it was necessary.

Not too long ago, I got the following e-mail:

Hi,

I’m an incurable puzzler but found that Sudoku was getting too easy.  So I wrote a new puzzle app for iPhone, [name redacted], which is available in the iPhone store for the first time today.  ([link redacted])

The easiest level is kid friendly.  The hardest level (with almost 4 quadrillion, quadrillion, quadrillion possible answers) is “Insane”.  The game is called [name redacted] and, like Sudoku, it challenges us to place a set of numbers in the correct positions on a square grid.  In this case, “correct” means that once placed, the numbers add up to the sums shown for each row, column and diagonal.

A 3 x 3 grid isn’t much of a challenge.  A 6 x 6 grid is incredibly challenging. (Yes, hints are available)

I would love it if you would review the puzzle in your blog.  I would be happy to send you a promo code to download and test it.


I've never considered myself an expert at constructive criticism, but I think I'll make an exception for this app and try my hand at reviewing it. In fact, looking at the iTunes store, I see that you have since released a second puzzle game app, and I will throw in a review of that one as a free bonus! Unfortunately, Mr. Incurable Puzzler, as you might have already surmised from that fact that I have redacted your name and your apps' names, it's not going to be a positive one.

My first criticism of the game is that fact that there is no free demo version of either app. The "try it before you buy it" business model popularized by many shareware computer games of the 90's has proven to be very successful. Why do car dealerships let you test-drive their cars before buying them? Why do grocery stores offer free samples of certain food items? It's to give the potential buyer a better idea of what's being offered for sale. For example, Nikoli has a line of iPhone apps, including Akari Free, a free app containing ten Akari puzzles, and several Akari apps which cost $2.99 and contain fifty puzzles each. Imagine being someone who has never solved an Akari puzzle before. Wouldn't you be reluctant to spend money on this app? You don't know whether Akari puzzles are very interesting. You don't know whether this particular app's interface is pleasant enough to make the puzzles fun to play (because if the puzzles are otherwise well-designed, but the interface is designed poorly, the app as a whole will be very unpleasant to play). The free app gives you a better idea of what you're buying, and whether you'll enjoy it or not. I know that I personally would not have payed for Nikoli's $2.99 apps were it not for the availability of the free apps. My suggestion to fix this: offer a free version of each app with maybe 5 puzzles in each size, and add a version with unlimited puzzles as an in-app purchase.

Before I continue my review, I should probably add that I have not actually downloaded either app, despite having an iPhone on which I could easily do so, and without having downloaded the apps, all I can really judge are their screenshots and their descriptions. While the author has expressed willingness to give me a promo code for one of the apps, I don't have the heart to get his hopes up by asking for said promo code, and then demonstrate my gratitude by posting a negative review. (I do, however, apparently have the heart to post a negative review in the first place. . . .) So without further ado, here are the screenshots! (These screenshots and the puzzles therein are © 2010 "Mr. Incurable Puzzler"; I believe the use of these screenshots for review purposes qualifies as fair use.)
(click to enlarge)
In both puzzles, the objective is to fill each cell with a distinct number from 1 through 9. In the puzzle on the left, the sum of the numbers in each row, column, and one of the diagonals is given; in the puzzle on the right, the sum of the numbers in each 2x2 block is given. Some of the numbers are given in each puzzle.

The puzzle on the left can be solved algebraically, without the need to use the rule that every integer from 1 through 9 appears exactly once. This is because we have a system of seven linear equations with six variables:
a+2+b=11 [i]
c+d+1=13 [ii]
5+e+f=21 [iii]
a+c+5=16 [iv]
2+d+e=15 [v]
b+a+f=14 [vi]
a+d+f=14 [vii]
Note, however, that the sum of the row totals must be the same as the sum of the column totals, which means that any one of the first six equations is redundant, as it is implied by the others. Thus, we really have a system of six equations over six variables, which is still solvable.

Subtract [iv] from [ii] to get:
c+d+1-a-c-5=13-16 ⇒ d-1=a

Similarly, subtracting [iii] from [v] yields this:
2+d+e-5-e-f=15-21 ⇒ d+3=f

Taking equation [vii] and substituting d-1 for a and d+3 for f produces:
d-1+d+d+3=14 ⇒ 3d+2=14 ⇒ d=4

From here, the rest is trivial:
3 2 6
8 4 1
5 9 7
I could have observed that the bottom row must have a permutation of 7 and 9 and figured out which permutation works, but why use logic when mere algebra is sufficient?

In the puzzle on the right, we have only four sums given, resulting in a system of four linear equations over six variables; we have no choice but to use fact that every integer from 1 through 9 appears once. The upper-right corner has 6, 9, and two other numbers that add up to 8 to make up a total of 23, and the only numbers available are 1, 2, 3, 5, 7, and 8; these numbers must be {1, 7} or {3, 5} in some order. The lower-left corner has 4, 6, and two other numbers that add up to 8 to make up a total of 18, so these numbers must also be {1, 7} or {3, 5} in some order. Thus we have 8 possibilities:
- 1 9    - 1 9    - 3 9    - 3 9
3 6 7    5 6 7    1 6 5    7 6 5
4 5 -    4 3 -    4 7 -    4 1 -

- 5 9    - 5 9    - 7 9    - 7 9
1 6 3    7 6 3    3 6 1    5 6 1
4 7 -    4 1 -    4 5 -    4 3 -
The upper-left corner has a sum of 18, and the lower-right corner has a sum of 20, so the remaining two spaces can be filled in:
8 1 9    6 1 9*   8 3 9    2 3 9
3 6 7    5 6 7    1 6 5    7 6 5
4 5 2    4 3 4    4 7 2    4 1 8

6 5 9*   0 5 9*   2 7 9    0 7 9*
1 6 3    7 6 3    3 6 1    5 6 1
4 7 4    4 1 10   4 5 8    4 3 10
The possibilities marked with asterisks can be eliminated because they either repeat a number or use the illegal numbers 0 and 10, leaving us with four solutions.

Wait a minute. Four solutions?

FOUR SOLUTIONS?!?!?

Both apps' descriptions say, "All [app's name] puzzles can be solved with logic so there’s no need to guess. Which is just as well because there are over 300,000 possible answers to the Beginner puzzle and only one is right." Yet one of the screenshots of the latter app shows a 3x3 Beginner puzzle with FOUR SOLUTIONS! How am I, as a logic puzzle connoisseur, supposed to respond to such an atrocity? Actually, let me rephrase that: how am I, as a logic puzzle connoisseur who wishes to keep his blog PG-rated, supposed to respond to such an atrocity? There is no appropriate invective-free response to this kind of horror. You simply do not bill something as a logic puzzle with only one solution, and have it actually have four solutions.

Now let's look at a pair of 6x6 Insane puzzles:
I think it's pretty obvious what's going on here: the program merely randomly permutes the numbers (there are 36! ways to do this), randomly gives you one number per row and per column (there are 6! ways to do this), gives you the sums, and says "Solve it!" "Created by an expert Sudoku player tired of repetitive game boards and short challenges", my eye! Thomas Snyder is an expert Sudoku player, and has the World Sudoku Championship victories to prove it, so I know what kind of puzzle an expert Sudoku player creates. This is more like created by someone who solved five Sudoku puzzles and realized that puzzles make money, so he slapped some programming code together as quickly as possible and called it a puzzle. It reminds me of when I was younger, and I thought I could make a Battleships puzzle by randomly placing the ships, randomly picking some shots, and putting the numbers everywhere. I didn't realize the most important step: make sure there's only one solution.

I see no obvious logical way to start either one of these 6x6 puzzles except to do what I did earlier and list every possible case I find until one of them works. But frankly, after arriving at four solutions earlier, I'd rather play an expert grid in Minesweeper in real life while people are constantly throwing durians at me until I either clear the board and win or trigger a landmine and lose. (And that's just the PG version of what I'd rather do.) If anyone out there is willing to punish themselves by solving these puzzles, or to write a computer program to do so, I will gladly edit this review to reflect how many solutions they have. (Edit: According to ralphmerridew, the puzzle on the left has at least three hundred solutions – a far cry from one! – and the one on the right has just one.)

Final verdict: these apps are abominations! You can't review an app on iTunes unless you've actually downloaded it, but were I able to do so, I'd rate them each one star with absolutely no regret. (A one-star rating is especially in order for the first app – it has a five-star rating from someone whose review does nothing to explain the rationale behind the rating except to refer to the app's creator as "padre".) Nikoli's Kakuro puzzles are fun. Nikoli's Sudoku puzzles are fun. These puzzles, in contrast, are not fun, but frustrating beyond measure! Also, remember when I said you should make a free demo version of the app available? I take that back – don't make a free version of this app. If you're lucky, you'll make a buck or two off of people who don't know how terrible the game is because they haven't tried it and don't follow my blog. Make the game good, or at the very minimum passable, and then offer a free demo!

Moral of the story: don't ever ask me to review your iPhone app. Because I just might. . . and mock you mercilessly. In fact, "ask me to link to or review your stuff on my blog" is now officially on my "YOU MAY NOT" list on my sidebar, thanks to these two games.

Update (October 15, 2010): as of now, version 1.1 of the former game, [name redacted], is available. What's new about version 1.1? "Correct an incorrect logo image". That's it. Clearly Mr. Incurable Puzzler hasn't read my review, or doesn't care.

21 comments

ralphmerridew said...

I wrote a program to brute-force the right-hand problem, and it found only one solution.

Grant Fikes said...

ralphmerridew: I am quite relieved. While I kind of had a strategy in mind for brute-forcing it myself (start with one block, and then move to an adjacent block each time), I knew that no matter which block I started with, there'd be a crapload of possibilities, and they'd only branch out further from there, yielding lots of tedious adding and subtracting. The puzzle on the left looks even worse, since every combination for a row or column can be permuted in 120 ways, and there are fewer clues. :[

As frequent commenter Spheniscine said regarding the puzzle with 4 solutions: "Methinks 'these puzzles can be solved by logic alone' [is] just a string of buzzwords the creator see[s] that most logic puzzles advertise themselves with. X3"

Anonymous said...

The right side large puzzle is rather easy to brute force. There are 30 variables and 25 equations, so you only need to guess 5 values, which is definitely doable. You just need to make sure to choose an independent set.

Actually solving it doesn't look interesting at all, though the puzzle raises two possibly interesting questions.

1. Can an interesting puzzle with these rules be designed? This can be limited to solving several blocks until it can be solved algebraically, or to a complete solution.

2. What is the expected number of solutions for such a puzzle? My guess would be that for large puzzles, the number of solutions is usually small.

On the other hand, the left hand puzzle has 30 variables and 12 (+1 redundant) linear equations. I would guess there are many solutions to most such puzzles, not that I would bother checking.

Anonymous said...

A very similar puzzle type is Mathrax, see

http://www.janko.at/Raetsel/Mathrax/

Each puzzle has a unique solution and can be solved without guessing.

Anonymous said...

And the listed home page for the app at itunes is one of these domain-for-sale advertising pages...

Grant Fikes said...

First Anonymous: One reason why I wouldn't want to solve the puzzle on the right is that, even if only 5 values need to be guessed before the rest can be calculated purely algebraically, that's still a lot of permutations to check. If I were solving this puzzle, I'd probably start with the block with the sum of 27. There are 10 combinations that can complete the block, and each has 3!=6 permutations, so I have to check 60 possibilities, which sadly seems to be the fewest possibilities of any block to start with. And the branching and tedious arithmetic (as opposed to, I dunno, logic) can only get worse from there. I just solved a 4x4 puzzle, and it wasn't particularly interesting at all, so I'd hate to think how tedious a 6x6 would be.

Meanwhile, in the puzzle on the left, every combination for a row or column has 5!=120 permutations, which is even worse! :[

Second Anonymous: I gave Mathrax a look -- it's infinitely better than [name redacted] and [name redacted], because it's clear that actual effort was put into making the puzzles solvable. If these puzzles were in an app whose interface is relatively usable, then it would automatically garner at least a three-star rating from me.

Third Anonymous: I noticed that, too. It's damnable enough that the creator of the app didn't care to make sure the puzzles are solvable, but his failure to maintain his website is the most unprofessional mistake any app developer could possibly make. Even a poorly-designed website is better than just plain not paying for your domain name and having no website.

Anonymous said...

I never said I would want to solve the puzzle on the right. I just noted that it would be rather easy for a computer to do that, for the 6x6 puzzle, and probably also slightly larger puzzles.

I think I have a better idea how I would start such a puzzle, not that that I actually would want to. I'll try to think about it and I might comment on it tomorrow.

I agree this isn't "logic" as normally used in logic puzzles.

The left puzzle can't be easily solved by naive brute force. I wouldn't be surprised if this "problem" is a plain NP-complete problem, exponential in the number of cells.

ralphmerridew said...

Okay: brute-forcing on the left-hand puzzle has started to yield apparent answers:
35 13 5 4 2 1 | 17 24 33 25 15 32 | 8 28 21 11 20 9 | 3 16 18 19 31 30 | 6 10 26 12 23 14 | 7 22 34 27 29 36

35 13 5 4 2 1 | 17 22 34 26 15 32 | 8 28 20 10 19 12 | 3 16 18 21 29 30 | 6 9 27 14 24 11 | 7 25 33 23 31 36

Seven found so far.

ralphmerridew said...

300+ solutions, and they're all "35 13 5 4 2 1 | 17" so far.

Mr. Incurable Puzzler doesn't understand the claims he was making.

Anonymous said...

If ralphmerridew offers the source for his programs, I'll try to find some other interesting results on this "puzzle" type.

ralphmerridew said...

Perl source: http://pastebin.com/QAv40W7m

You'll probably want to rewrite it in C rather than Perl.

Anonymous said...

Thanks, ralphmerridew. Perl is just fine. I actually wanted the right hand puzzle, but this should be enough.

Rajesh Kumar said...

I solved your puzzles on janko.at website and these are quite good. Thanks for these puzzles.

term said...

This was written responding to a page lingering open in my tabset, so it covers some ground other posters have as well.

I’m probably in the minority in that I mind neither computer–generated puzzles, nor multiple solutions (provided I know of their existence beforehand, and can thus appropriately adjust my approach). However, if your problem does have multiple solutions, your app should accept them all; in this respect, the “only one solution” part in the quoted blurb does not fill me with confidence. Given that the large blue problem has over a quarter million solutions, that’s a deal breaker.

Interestingly enough, the large red problem has a unique solution. It’s no great wonder large generated red problems are much more likely to lead to uniqueness. For a grid of size n, you’re given 2n+1 (2n-1 non–trivial) “blue” linear equations, but n^2-2n+1 “red” linear equations, for n^2-n variables. Since the low information constraints (diophantic, range, pairwise inequalities) are identical, blue wins for n=3 (easy), red wins for n>4(hard, insane). A less–obvious–than–it–seems corollary is that “violet” problems (using both clue sets), would always be solvable, even without the aforebracketed constraints, but I digress.

Trying to be generous with the benefit of the doubt here, but I don’t know how the hint system works, and the form these hints take. They might introduce novel logic, or they may introduce economy elements leading to evaluating the puzzle for regional information density. Some may object on principle to looking at hints; I have no such qualms, for I don’t see why I should intentionally try to cripple my enjoyment of a product.

Having said that, solving systems of equations is no-one’s idea of fun. Even if it was, the interface we see is perfectly acceptable for entering your solution, but worse than paper (in fact, utterly useless) for helping you get there, the caveat being that we might be missing some notation nuances from the screenshots. In fact, should such amenities exist, I’d be very curious to know of their UI implementation.

term said...

Solution for large red problem is [[27,33,13,4,16,7],[14,21,9,1,28,31],[30,8,18,32,24,25],[26,5,29,3,2,15],[11,19,35,17,12,10],[22,34,20,23,36,6]]

Prolog code that solves both problems can be found at: http://pastebin.com/TmdzG9wb

The following queries will give you solutions for the left and right problems respectively:

p1(Solution).
and
p2(Solution).
Press ; to get another solution, or return to stop.

succeeds_n_times(p1(_), Number_of_solutions).
will give you a counter of solutions as they are found. This is pretty dumb code, so you will likely run out of patience before it runs out of cases.

Those of you with programming but no prolog / clp experience will likely have fun trying to figure out what's going on in the code.

Grant Fikes said...

term: I don't mind computer-generated puzzles, either, as a source of amusement. (For example, I have the app "Sherlock: The Game of Logic" on my iPhone; all of its puzzles are computer-generated, but they actually have unique solutions, and for some reason, I enjoy them. Also, there's a link to Conceptis in my sidebar, because I enjoy their Link-a-Pix puzzles.) I do, however, mind crappy computer-generated puzzles, which many (including these) are. Also, being the logic puzzle epicure that I am, I generally don't find as much to appreciate in them from an artistic standpoint as in handmade puzzles.

According to the apps' descriptions, the "hint" button shows you which numbers are wrong. That's it.

Phil Walker said...

Thanks for the review of the puzzles. In spite of the tone, it was helpful. I particularly liked the solution example for the screenshot you saw. I've been using that level to teach my kids some pre-algebra skills in much the same way. Nice work.

I know what you mean about try before you buy. I posted free versions at the same time as the paid versions but they got hung up in the iTunes app approval process. They should be out shortly.

The question of multiple solutions was something I thought about as well. I was looking for a way to test boards for multiple solutions and then to either discard those with more than one solution or challenge users to find all of them. Obviously if there are 300 possible solutions then that would be a stretch. If anyone has suggestions about how to figure this out without brute forcing it, let me know.

One point I didn't quite follow is the beef about solvability. I can solve a basic level of either app in a few minutes. Still working on the expert levels without hints. Is your beef that solving them is too mechanical or is it that its too hard?

Again, thanks for the review. I'm sorry you didn't like the games (they're certain to be more fun if you actually download them) but I appreciate the feedback nonetheless.

David Millar said...

Phil, I strongly suggest implementing a solver that uses the same logic humans could use to test solve puzzles as they're generated and add clues as needed to make them solvable. That, or simply use only handmade or pre-tested puzzles.

One of my biggest beefs with your app, however, is the user interface. Granted, I can't give it a try since I can't run the app of my first gen iPod Touch (why is it iOS4 compatible only anyway?) but just looking at it gives me a headache. The backgrounds make no sense whatsoever and only distract from the puzzle - and they're headache inducing patterns reminiscent of Windows 95 backgrounds.

Further, you spend a lot of screen real estate on buttons that probably wouldn't get used much in the course of solving. For example, you could easily add a separate menu for difficulty and toggling hints and give more space to the number display. Additionally, the semi-opaque background behind numbers that are already placed makes them harder to see for those with poor eyesight, and the round corners on some corners but not all of them makes for a really tacky appearance.

Honestly, even if the functionality were fixed, I'd still be inclined to give a low review just because the app doesn't look professionally made and seems like it would be hard to use.

Phil Walker said...

David, again thanks. New versions that are work with earlier OS versions are in the approval process. And I agree with you re the backgrounds - the kids like them, though. I'll likely eliminate those in the next version or make them optional. Same goes for the re-menuing. I'd like to make the clue buttons bigger and maximize board size (+10% or so given width constraints).

Thanks

Grant Fikes said...

Phil: I appreciate your good sportsmanship in spite of this review's rather scathing tone. I especially admire you being bold enough to attach your name to your comment and not remain anonymous.

You say, regarding the issue of determining whether a puzzle has a unique solution, "If anyone has suggestions about how to figure this out without brute forcing it, let me know." This is the source of my number one beef with the game. Essentially, how I solved the 3x3 puzzle on the right was by brute force, and I see no way to approach either 6x6 puzzle aside from brute force guessing, either. If I, a human being with years of experience with logic puzzles, cannot solve a puzzle without brute force, how can I expect a computer program to fare better?

Perhaps the easiest repair is to remove the claim that every puzzle can be solved by logic, since that implies that there is one solution to every puzzle. You might even add that a puzzle can have multiple solutions, but that hopefully doesn't necessarily make finding just one of them less difficult (as long as the program accepts any valid solution). However, it may not be the best fix, since many readers of this blog (and especially its author) would prefer for anything that even looks like a logic puzzle to have exactly one solution. The other option is to create a solver that can determine whether a puzzle is solvable and, if not, add givens to make it solvable. If it takes too long for the solver to generate a puzzle, consider having all of the puzzles pre-generated rather than generated on the fly.

"One point I didn't quite follow is the beef about solvability. I can solve a basic level of either app in a few minutes. . . . Is your beef that solving them is too mechanical or is it that its too hard?" I believe there are two different concepts of what "solvable" means. The first concept is to interpret the puzzle as a task to be done. In this sense, a puzzle with four solutions is solvable in four ways. The other concept is to interpret the puzzle as the task of deducing something logically using several clues. Thus, if there are four solutions, then you can't deduce which one is the correct one, so the puzzle is unsolvable. Consider a 2x2 Minesweeper puzzle with the number 2 in the upper-left corner. Under the first concept, the task is to place mines on the grid so that the number, representing how many mines it shares a corner or an edge with, is correct, and the puzzle is solvable in three ways. Under the second concept, the mines are already hidden in the grid, and the task is to use the clue provided by the 2 to determine where the mines are, but since you can't determine where they are (there isn't enough information to do so), the puzzle is not solvable. I personally believe the latter definition is more true to the definition of a "logic puzzle".

term said...

@Phil:
As I mentioned before, unless I’m being extremely stupid, giving both red and blue clues will result in a consistently solvable problem, though I can see how that would go against the business plan. It would still need note taking (preferably on app), and it would still be as fun as having teeth pulled though.

Another approach to cutting down on solutions may be to modify the problems so that the integer and set constraints are much more effective than usual. This would mean changing the set of numbers in the solution to something other than 1..n^2, which is quite possibly the worst choice one could make. For example, a 5x5 problem that had only 5 odd numbers in its solution but all blue clues odd would be much more constrained than normal. You can do the same thing with, say, a small subset of numbers being much larger than the others. You can use number sets such as {1,2,3,11,12,13,21,22,23}. Or make sure the differences of adjacent numbers in the set are also distinct, like {1,12,22,31,39,46,52,57,61} Using one (or more simultaneously) tricks of this sort will cut down on the number of solutions considerably. At the very least, determine your solution number set randomly. My bigger points are, I suppose, that
a) the solution numbers can, and should, become a useful piece of information .
b) if you inject a pattern in the problem (a pattern of givens and/or solution values), that becomes both better specified and more interesting to the solver.
Yes, this means a much more complex problem generator; no pain, no gain.

Now regarding determining uniqueness: there is a ton of literature on computationally effective ways to attack linear equation sets, and about as much work on diophantic problems. I know not of work on sets of linear diophantic equations, which I suppose reflects more my ignorance than its paucity. I also need to point out that work that specifically determines a lower bound of solutions would do at least as well, and may in fact involve methods that calculate no solutions in themselves. But I’m not willing to do someone else’s research. I got my results by relying on an existing finite domain constraint logic library, which pretty much implements all generic shortcuts, and gave it exclusive use of a Q9550 2,83GHz core. Good luck getting/writing somesuch for iOS. Still, Big Red was verified unique in about 2,5 seconds, and Big Blue took more than a second for non-uniqueness (I have a feeling it would take much, much longer to certify this problem’s uniqueness). Admittedly, Prolog isn’t exactly what you call speedy, and ralphmerridew’s direct and brutal approach may be more suited to your needs.

But the thing is, even if you get a speedy uniqueness check, a workflow that goes something like “randomly generate problem until you get a uniquely clued one” very much depends on the ratio of uniquely solvable problems to problems. For a large blue problem, and possibly others, I expect that ratio to be vanishingly small. A few billion repetitions of a lightning-fast generate-verify cycle is still more than a user can be reasonably expected to wait.

@Mathgrant
“If I, a human being with years of experience with logic puzzles, cannot solve a puzzle without brute force, how can I expect a computer program to fare better?” Well, if it comes down to brute force, I’m pretty sure the computer will fare better, but that’s not what you meant. And obviously, the computer can’t do anything you can’t tell it to do, but you’re not one for the near tautologous. The answer is that humans will shy away from notetaking when it gets too much, while the computer revels in that. The aforementioned clpfd library is kind of an example. How many hundreds of notes would you take then combine to make trivial progress? (Feel free to literally answer this rhetorical question in retaliation.) Of course, if the only method of progress is such copious notetaking, the most intelligent approach to the problem would be to ignore it.
Unless it involves Ducks.

Blog Archive