Transcendental Generalization

I seem to see too many movies to write a review of each, but this one is priceless.

In the lives of Ashoke, Ashima, and their son, we are given a complete view of the immigrant experience, from the hopes and troubles that motivate naive young people to rebuild their lives in a foreign country, to their longing for the familiar faces and routines of home, to the humor of misunderstandings between cultures, sexes and generations, to the difficulties for the new generation of being completely assimilated.

The story is a series of such incidents laid out like a string of pearls. I had not read Jhumpa Lahiri’s book, on which this movie is based. Having read (and reviewed) Lahiri’s Interpreter of Maladies, I found many of the characters familiar, yet they remained realistic, multi-dimensional, and loveable. There is no strong-armed activism or political commentary in this story. By treating every character with compassion and every event even-handedly, Lahiri captures an essentially Indian perspective on life.

I was not immediately impressed by Mira Nair’s direction. The intentional use of grainy film seemed erratic, and the positioning of the camera to separate people seemed overt. But upon further reflection, I realized it is the direction and editing that so powerfully communicates either the closeness or the separation between the characters and their homes.

For Kal Penn, this is certainly a step up from Harold & Kumar Go To White Castle. A masterful performance is given by Irfan Khan who superbly plays the absent minded professor and awkward father and husband who is so gentle and loving at heart. But the star of this movie is Tabu, whose character we follow from youth through marriage, motherhood and finally matriarchy.

I don’t know who first said it, but in developing almost any skill, the following stages apply:

1. You don’t know the rules. Practitioners in this stage perform poorly and don’t seem to “know what they’re doing”. Their own experience is often one of frustration and struggle.
2. You know the rules and follow them. Practitioners in this stage perform well. They and others enjoy their performance of the skill.
3. You know the rules and break them. Practitioners in this stage perform exceptionally well. They break the rules in order to differentiate and individualize their performance and to enable others to enjoy it in unprecedented ways.
4. You re-write the rules. Practitioners in this stage establish new structures and standards for their skill. They may be rejected by the mass of other practitioners and connoisseurs who are accustomed to the old structures and standards.

In personal finance, one rule is, “Avoid debt.” People who don’t know this rule may rack up exorbitant credit card debt and end up filing for bankruptcy. People who know this rule and follow it will typically enjoy debt-free life and slow but steady growth of their net worth. People who know this rule and break it will occasionally take on low-interest debt for necessary purchases so that their capital can earn higher rates elsewhere. Those who are experts can re-write the rule as, “Finance high returns with low-interest debt.” They actively manage risk and seek high returns on investments, financing those investments with low-interest debt if necessary.

On my most recent plane trip, I finished my books and newspapers and used my computer until its battery ran out. So, I picked up the in-flight magazine and started working on the Sudoku puzzle.

The computer scientist in me has always known that programming a computer to solve a Sudoku puzzle should be fairly easy. Its rules are quite simple and only logic is required to solve it.

I typically took two approaches in solving the puzzle.

• Choose a number and eliminate cells: By far, my preferred approach was to pick a number and use existing constraints to determine in which cell the number must be.
• Choose a cell and eliminate numbers: Rarely, I would take the other approach, which was to pick a cell and use existing constraints to determine which number must go in it.

(I never had to use the hard approach where you guess and then backtrack when your guess turns out wrong.)

In any case, being a contrarian, non-zero-sum kind of guy, I was always more interested in the prospect of generating Sudoku puzzles. So I would think about where, which, and how many numerals to place in a blank grid to make a Sudoku puzzle. I was also cognizant that the puzzle would have to be uniquely solvable—it was no good if there were multiple solutions or if no solution was possible.

On this trip, I realized that solving and generating were linked. When you choose a first number and place it in a blank grid, you can no longer place that number in the same row, column, or three-by-three block. You’ve eliminated that number for those cells. This sounded like the second approach above. For some reason, this insight moved me profoundly. It made me think any puzzle could be solved by taking only that approach. So instead of solving the puzzle, I filled the page with pseudocode implementing the approach.

As soon as I got home, I plugged in the computer and fired up Microsoft Visual Studio. That night and the next day, finding a few minutes at a time here and there, I implemented the algorithm in C#. Here’s how it worked:

1. Start with an empty grid and represent all possibilities for all squares.
2. Initialize the puzzle from the printed page by eliminating all but one possibility for the cells that are known, or certain.
3. For each cell that is certain, eliminate its number as a possibility from the cell’s row, column, and block. I referred to this as advancing the puzzle.
4. Assuming additional cells now are certain, repeat the prior step until all cells are certain.

One really interesting thing became clear as I was writing the code. It might seem like you might need a two-dimensional array to represent the cells, but you don’t. All that matters is that each cell be associated with the correct row, column, and block. Each row, column, or block can in fact be represented as an unordered set of cells.

Well, after writing this program, I ran it on the first puzzle in the in-flight magazine. It filled in a few cells as expected and then stopped. This approach alone was not sufficient to solve the puzzle.

After thinking about it for some time, I had insight #2: the puzzle had to be advanced in two ways. The puzzle seemed to require advancing like an inchworm moving first its rear and then its head. So I modified the program as follows:

1. Start with an empty grid and represent all possibilities for all squares.
2. Initialize the puzzle from the printed page by eliminating all but one possibility for the cells that are known, or certain.
3. For each cell that is certain, eliminate its number as a possibility from the cell’s row, column, and block. I referred to this as the push part of the advance.
4. For each row, column, or block, if a number is only possible in one cell, then eliminate all other possibilities in that cell. I referred to this as the pull part of the advance.
5. Assuming additional cells now are certain, repeat the prior step until all cells are certain.

This algorithm worked extremely well at solving the Sudoku puzzle. (Update: here is a Zip File of Java Source Code and a Zip File of C# Source Code.) But what about generating one? It was true that you could start with a grid, and put a random number in a random cell. After that, you couldn’t just put any number anywhere, because the first number you placed would limit your choices somewhat, but there would still be lots of possibilities. However, you could keep going until you filled the grid. At what point would you have a puzzle?

Answer: there is a third approach to advancing the puzzle, which is to put a random number in a random cell, constrained only by the cells that are already occupied. This approach can always be used in an empty grid, and may have to be used if the first two approaches can no longer advance the puzzle. Insight #3: puzzles are solved and generated in pretty much the same way.

To generate a puzzle, start with an empty grid and attempt repeatedly to apply the approaches in order. In the beginning, only the third approach will be possible. However, you will reach a point after which the first two approaches will be sufficient to complete the puzzle. That point is, of course, a publishable puzzle.

It turns out that some of the hardest puzzles published do require this third approach. However, I have not tried solving any of them, nor have I modified my program to do so, yet.

Once I realized this, I naturally began to think about minimal and maximal puzzles. A minimal puzzle would be one where a minimum number of cells have been determined using the third approach, and the first two approaches are now sufficient. A maximal puzzle is one where removing even one cell would require solving using the third approach.

A lot of questions remain unanswered. A Google search reveals that people have probably already answered them, but it’s not clear (to me) what the answers are.

• The difficulty of a puzzle is proportional to two things: the number of cells that must be filled, and the number of approaches that must be used. How do you generate a puzzle of a specified difficulty? There are generators that allow you to specify the difficulty, but what exactly do they mean by a named difficulty level (”easy,” “hard,” “devilish”)? Is it an indication of the number of approaches used? I haven’t seen the generation algorithms in sufficient detail to know.
• If the third approach must be used for a published puzzle, then does that mean multiple solutions must be possible? Some of the generators do generate puzzles that have multiple solutions. However, I think it is possible to generate a puzzle that requires the third approach, but has only one solution—if you choose the wrong random number/cell, you eventually find out because the puzzle becomes impossible to solve. It may be that your puzzle must require the third approach only once.

It would be cool if you could generate puzzles with a specified number of empty cells requiring the third approach to fill the next cell. You could generate progressively harder puzzles that would teach use of the third approach.