Memento Mori

A discussion at work took place about design patterns, and it prompted me to go back and look at something. One of the behavioural patterns is Memento, which (from Wikipedia) “provides the ability to restore an object to its previous state (undo)”. The implementation described uses three objects: a caretaker, an originator and a memento object that the caretaker can use to restore the originator to a previous state.

From a functional programming viewpoint, I find this overly complex. Consider a system in which an object follows the functional principle of immutability. To “change state”, a caller calls a method on that object, but the original object is unchanged: the method returns a new object with a different state. There’s then no need to have the complexity of undo – the previous state is available via the original instance.

Of course, this is already the case with immutable strings in many languages. Consider this C#:

    string s1="This String is Mixed Case";
    string s2=s1.ToLower();
    //Oops - we need to undo the ToLower() operation.
    s2=s1;  //This is effectively an "undo"

The only principle to keep in mind is to save a reference to a previous version of the object if there is a potential need to undo it.

Benefits: huge saving of complexity, and therefore of testing. I find that the testing load is often forgotten when developers assess how much work is involved in an implementation, unless TDD is in the blood of the team.
Downside: potential extra use of memory to keep hold of previous objects. With intelligent sharing of expensive resources between objects, this can be minimal.

Advertisements

Solving Sudoku With Superpositions

So I’m dead.

Actually, no, but that is a killer first line, from the movie Confidence. And when you have a killer first line, you go with it.

So I find myself writing up some examples and explanations of how to do basic object oriented design and development, and thus having to come up with something to serve as an example of how you might actually approach designing and implementing some code in C#. A problem slightly more connected to the real world than, say, yet another example like:

class Shape
{
    virtual void Draw{}
    { }
}

class Circle : Shape
{
    override void Draw{}
    { }
}

Sudoku will serve pretty well. First of all, it’s a fairly easy problem to understand. Also, anyone who’s of an algorithmic frame of mind and has encoutered a Sudoku puzzle has probably spent a while thinking about how to generally solve them. Programmers know that working out how to solve any problem of type X is more fun than actually solving any given individual problem of type X. And writing the code to do it also keeps you looking busy while someone else goes and does the actual work.

So, here is the algorithm that I’ve used as a basis, which I like to call solving with superposition because it lets me get all quantum and esoteric about it. To follow, you’ll need to know at least the basic rules of Sudoku puzzles, which are ably explained in the relevant Wikipedia article.

On first encountering a Sudoku puzzle, such as this:
Example Sudoku Puzzle
we can see that:

  • It’s made up of 81 cells
  • They’re arranged into 9 rows, 9 columns and 9 squares, each of which contains 9 cells.
  • Each cell either contains a number (we’ll call these solved), or is blank (unsolved)

For the purposes of this algorithm, let’s start off by assuming that each unsolved cell contains all the possible numbers 1 to 9 that it might hold. The work of solving the puzzle then involves finding numbers that cannot be in unsolved cells, and removing them, until each unsolved cell only contains one possible number, which means that it’s then a solved cell. I call this process pruning.

I should point out here that there are many different ways to solve Sudoku puzzles. This is just one, and not necessarily the best one; I’ve chosen it because it’s a nice little algorithmic example. If you have better approaches, go write a Wikipedia article.

Anyway, back to the explanation. Let’s show how the top-left group of nine cells in the example puzzle might be written out by a programmer trying out this algorithm. Conceptually it looks like this:

   
 5 
   
  3
   
   
123
456
789
   
  6
   
123
456
789
123
456
789
123
456
789
   
   
  9
   
   
 8 

When we prune the puzzle, we follow this approach:

  • For each solved cell in turn, remove the number it contains from all the unsolved cells in the same row, column and square.
  • If, as a result of that, an unsolved cell is left containing only one number, that cell is now solved.
  • Keep doing this until either the puzzle is completely solved, or there are no more solved cells to process.

The thoughtful amongst you will have noticed that this will, so far, only solve very simple puzzles. Patience: more is yet to follow. For the moment, let’s prune that example square of the board I showed above.

First, the topmost/leftmost cell contains a 5. So we know that we must remove the 5 from all the unsolved cells in the same row, column and square.

   
 5 
   
  3
   
   
123
4 6
789
   
  6
   
123
4 6
789
123
4 6
789
123
4 6
789
   
   
  9
   
   
 8 

We can then do the same for the other cells that are already solved (the 3, 6, 9 and 8):

   
 5 
   
  3
   
   
12 
4  
7  
   
  6
   
12 
4  
7  
12 
4  
7  
12 
4  
7  
   
   
  9
   
   
 8 

Okay, we now have a number of cells that are still ambiguous; that is, we know that they may still be one of n possible values, even though we’ve reduced the value of n by eliminating values that can’t be in the cell.

Here’s the superposition bit: we take a cell that still needs to be solved, and for every value that the cell could hold, we generate a different version of the board. So if we take the cell after the 5 & 3, that could be 1, 2, 4 or 7 (in red here):

   
 5 
   
  3
   
   
12 
4  
7  
   
  6
   
12 
4  
7  
12 
4  
7  
12 
4  
7  
   
   
  9
   
   
 8 

…we generate four versions of the board, one in which the red cell holds 1, one in which it holds 2, one in which it holds 4 and one in which it holds 7. You can think of this (if you like to play with quantum terminology) as a superposition of four possible boards. We then take each board in turn and proceed to try and solve it, using the same techniques again. For example, if we take the superposition in which the red cell holds 2, then we need to remove the 2 from any other cells in the same row, column and square…

   
 5 
   
  3
   
   
 2 
   
   
   
  6
   
1  
4  
7  
1  
4  
7  
1  
4  
7  
   
   
  9
   
   
 8 

We still have some ambiguous cells, such as the one in blue that could hold 1, 4 or 7. So we create three further superpositions, one for each of the possible values of the blue cell, and then proceed to solve each of those.

Okay, the software-oriented amongst you will immediately have started thinking about recursion and stacks. Which is exactly what I was after: an example which requires that the students think about objects as elements in data structures that must then be subjected to processing. I need only make it compulsory for them to use the generic System.Collections.Generic.Stack collection, and I have an interesting algorithmic problem for them to solve…