I use this blog as a soap box to preach (ahem... to talk :-) about subjects that interest me.

Tuesday, September 27, 2011

Progress on the CalcuDoku application for the iPad

This is to report on my progress on the development of the application I announced in my previous article. Here a snapshot that gives you an idea on some of the functionality:

As you can see by comparing this image with the image in the previous article, I have added some important feature.

First of all, each cell is now identifiable by its row/column coordinates like those used in chessboards. This also lets you identify each cage by giving the coordinates of its cell that contains result and operation code. For example, you can use G4 to identify the 3/ cage.

The most visible improvement is that each cell now shows its candidates. I found that without candidates, solving the puzzle was incredibly more difficult than solve the same puzzle with paper and pencil. The advantage of having the application determine the candidates for you, is that now you can concentrate on finding conflicts and solving cells. To take full advantage of the candidates, you have to check the cage combinations.

For example, in the 3/ cage you find in F4 of the following example

you see that the two cells have candidates 13 and 139, but when you consider that the two possible combinations are 13 (with two permutations) and 39, you realise that a 3 is always present in either F4 or G4. This means that any other 3 in the other cells of column 4 are not possible. Every such a small step gets you closer to solving the puzzle. In the example, I have already removed the 3s from column 4, because I want to use it to show you another possible strategy. Notice that the cell A4 only has a 1 and a 9. As cage F4 can only contain either 13/31 or 39, it means that if the correct solution for cell A4 is 1, the solution for cage F4 can only be 39. Alternatively, if 9 is the correct solution for A4, F4 will be solved with either 13 or 31. In either case, the other six cells of colun 4 cannot contain any 1 or 3. This lets you discard as possible candidates the 1s in cells H4 and I4.

These type of reasoning is what makes CalcuDoku appealing and a very good excercise for the brain.

Another extension I have introduced is the list of permutations, which you see at the bottom of the image. They are sometimes useful in figuring out how to solve a cell, but, in any case, they give you an indication of how close you are to solving the cage. There is not much point in analysing at length a cage when it contains more than a handful of permutations. Note that a single combination can result in many permutations.

Obviously, the application keeps the lists of candidates, combinations, and permutations up to date as the solution progresses. While the candidates are always visible, combinations and permutations of a cage are only displayed when you touch a cell of the cage. When you do so, what I have decided to call ‘action menu’ appears, as shown in the following snapshot.

As you can see from the description below the puzzle, the menu of this particular example appeared when I touched one of the two cells of cage 3/ in A8. I didn’t bother to make it more complicated and confusing by also writing which one of the two cells I had touched. I assume that you always know what cell you have touched.

The cage can only contain the combination 26. Notice that the application always orders the digits from the largest to the samllest (e.g., 62 instead of 26). This has to do with the logic of the application itself. I got used to it and I don’t think it is worth wasting effort and processing time to swapt them around.

Anyhow, the menu lets you choose or remove a candidate among those possible for the cell you have touched. It also lets you ask the application to tell you the solution of the cell or of the entire puzzle.

This is going to change, as I am going to move the possibility to reveal the whole puzzle to a toolbar. The menu should only let you do something with an individual cell.

I generate the puzzles offline and load them into the iPad application as resources. Initially, I thought that I would provide a service with daily puzzles, but I have changed my mind. One of the reasons is that I don’t actually like to have to provide the service. It is much simpler to sell an application with, say, one hundred built-in puzzles.

There is also another more critical reason: a few percent of the puzzles my program generates are too difficult to be solved with the iPad application, and I don’t want to deliver puzzles that cannot in all honesty be solved. So far, I have been able to solve all puzzles with pencil and paper, but sometimes I had to use complex ‘what if’ analyses that are not possible on the screen (or, to put it bluntly, that would make the application too complex).

Finally, in a few percent of the cases, different pseudorandom seeds result in identical puzzles. This is due to the many restrictions that I impose on the puzzle generator in order to make puzzles that can be solved analytically.

As a result, I solve all the puzzles with the iPad application before permanently loading them into it. This ensures that they can be solved. You might argue that a more skilled puzzler might solve puzzles I cannot solve, but, after solving hundreds of CalcuDokus, I have become quite good at it, and even the most adept puzzlers will find my puzzles challenging!

One thing I still want to do before releasing the application is provide a ‘hint’ button. This will be a toolbar button, not associated with any cell. For example, in a puzzle including the following couple of rows:

the hint could be that no 4s or 5s are possible in cells D1 to D6 because they certainly appear in D7 to D9. Indeed, cage 7+ in D7 can only contain either 43 or 52/25, thereby forming an exclusing pair with the 4 and 5 of cell D9. The challenge is to make the application recognise these occurrences and formulate intelligible hints. I will start working on it as soon as I post this article to the blog. I have half an idea of how I should be able to do it.

Ultimately, I want to be able to solve the puzzles exclusively by using hints. And this is the test that I will do before releasing each new puzzle. It will ensure that the application will not run out of hints. To road-test the algorithm, I will try it out on the puzzles I have solved by hand.

The number of hints necessary to solve a puzzle will also provide a rough measure of its difficulty.

Now I am eager to get started on the hint functionality. My apologies for the typos I have left in this article because of my haste...

No comments:

Post a Comment