All posts by AfterMath

Latin Squares are so Beautiful

Figure 1: Image of a 5 by 5 Latin Square with colors mapped to numbers.

I was recently reading another math blog on Latin Squares and it brought the concept back to the forefront of my mind. For years I have wanted to do something with Latin Squares, but nothing generated enough of my interest to follow through on a project to completion. I had done some things to create a random Latin Square, but didn’t think that in itself was worthy of publication. So I let it linger.

Then I read this post. It talks about Latin Squares with added chess-based restrictions. So the one based on a chess knight’s move would say that in addition to being a Latin Square, there would be a restriction that cells (x, y) and (x +/- 2, y +/- 1) and (x +/- 1, y +/- 2) all be different. Likewise there is a bishop based restriction saying that cells (x, y) and (x +/- i, y +/- i) all be different. Because Latin Squares already assume that cells have horizontally and vertically different characters, this is the same as a queen’s move would be. Latin Squares also already take into account the rook moves. The remaining pieces talked about were the king based Latin squares. These say that for a cell (x, y) the cells (x+/-1, y+/-1) must all be different. There is an accompanying paper that I also found interesting.

I read this blog article on the heels of having just improved my puzzle generations, so naturally I thought these would be good puzzles to attempt to generate and add to my puzzle section. So the first thing I did was complete a standard puzzle for Basic Latin Squares. These are under the standard assumptions saying that no number can appear more than once in any row or column. Then I used the max-submatrix problem to remove cells from this completed solution to create a puzzle. I played with this for a while and that was that. I attempted to add variants of the Latin Squares based on the chess pieces mentioned above, but with the exception of the trivial ones these were difficult and timely to generate. So again, that was that.

Until it wasn’t. I played around with the puzzles for a few hours (puzzles are addictive and started asking more questions. One of the first ones was simply how many clues do I need to have for a Latin Square to remain unique? I’m sure this problem has been studied, as it is a well studied problem for Sudoku puzzles, which are Latin Squares with an added restriction on the 3 by 3 subgrids. I found that the critical set of a Latin Square is the minimum number of cells from which a Latin Square can be reconstructed. Interesting.

Figure 2: Latin Squares with some cells removed, making them into completion puzzles.

Then I started thinking about visualizing Latin Squares. Obviously there is a way of visualizing them as a grid, possibly with colors instead of numbers or letters. That can make it more visually appealing. I was thinking about more of a graph theoretic approach though. So the first thing I did was something similar to the permutation graphs. With permutations, we had two lines, one representing the given permutation and one representing the lexicographically sorted permutation. Then lines are drawn between elements with the same value on different row. From this graph, we can construct a second graph consisting of the crossings (intersections of lines) in the first graph.

Figure 3: Visualization of the Latin Square originally Presented, with lines connecting elements of the same color on different rows

I used a similar approach to construct visualizations of Latin Squares. The first visualization is a node representing each cell in the square. Then lines are drawn between cells/nodes that have the same value. Once again, from this initial graph, we can look at the crossings and build a second graph, where we have the same node set, and an edge is present between two nodes if the two corresponding lines cross one another.

Figure 4: A second Visualization of the Latin Square presented in Figures 1 and 3. Edges in Figure 3 are nodes here, and two edges that cross in Figure 3 have an edge between them here.

Apart from the (beautiful) visualization, the question I was asking myself is what information can be gained from these representations of Latin Squares. Could we gain anything from these crossing numbers? Would this last graphical representation always produce the original Latin Square? Or how similar must two Latin Squares be to get the same graph? Is there a graphical representation that preserves Latin Squares with less information?

Puzzle Generation Idea (Its Working)

A lot of my friends ask me what I do with my spare time. There are a number of ways I could answer that question, but the answer is basically this site. Its full of the thoughts that go through my mind as I’m at work, when I’m on a run, or driving my car or with my kids. Sometimes It’ll be a new idea, or a way of teaching/explaining/visualizing something, or something for my kids or a new way to relax.

A few years back, I added a section to this site called Puzzles. These were basically puzzles that I had seen in passing at some site or in a book that I thought were fun and challenging and wanted to do more of. The site started with the puzzles being offered as a part of the LEARNINGlover.com examples section, and many still are there. But as the site grew and I really enjoyed making the puzzles, I decided to offer a separate page dedicated to the puzzles.

Then we get to the fun part of it. How do we generate puzzles? There are basically two types of puzzles I’m thinking about here. One is where there is some final answer and none of the information that is needed for the answer is given. Instead, hints about the final answer are given. Some puzzles that offer this type of structure are Nonograms, Shade the Cells or the Magical Squares Puzzles. These are very fun and a bit easier to create.

An Image of the Shade the Cells Puzzle with Complete Information

The other type of puzzles I’ve been playing with are the ones where the final answer is generated according to some set of rules, then a subset of this final answer is revealed as a “hint” to direct the user towards the unique final answer. Some examples of these puzzles are Sudoku, Slitherlink, Binary Puzzles, and Corral. These puzzles have been more difficult for me to generate because the question that has puzzled (no I did not mean to have a play on words) me is how do we decide which puzzle cells to remove and still keep a unique solution?

An Image of a Corral Puzzle with Partial Information

I tried a number of techniques that all left me dissatisfied. Eventually I had left the problem alone and had a technique of removing a large number of cells (allowing for multiple solutions to exist) just added a “reveal” button to give more hints towards the solution if a user was stuck. This left me very unsatisfied as a) I was sure there was a way of doing this since I see it done on so many other sites so often and b) I would often start down a direction and press the reveal button, only to be told that I was headed towards the wrong one of the multiple solutions.

That is what brings me here today. I also spend a lot of time looking at programming challenges and practice exercises to help better understand data structures and algorithms. One of those problems was the maximum submatrix sum problem. The problem asks, given an m by n matrix of integer values (positive or negative) can we find the submatrix that has the maximum sum. I solved this problem years ago and had it sitting in my library as something I was going to develop as a game to play with my kids.

Then the thought hit me of using this to help decide on which cells to remove. The idea is that in most of these puzzles the neighbors of a cell have a direct influence on the contents of a cell. So in a Sudoku puzzle, we know that a cell containing a 9 inside a 3 by 3 subgrid cannot have any more 9’s. The maximum submatrix problem wouldn’t divide the original grid into the 3 by 3 subrids as Sudoku does, but it as still performed reasonably well.

Here is an overview of what we’re doing with the algorithm. Initially I set up a matrix with all positive values. For some puzzles, this is the contents of the cells, for other puzzles like Binary Puzzles I set the matrix to all 1s. Then the generate algorithm will search for the maximum sum of this matrix, and from that submatrix will select a random location. This random location will have its value removed from the puzzle and the value in this matrix will now be a large negative number. Then we simply check to see if there is a unique solution and continue.

That’s the gist of it. I have added a small quirk where I allow for a few misfires – that is, some attempts to remove a cell that leads to multiple solutions. On a misfire we simply put the value back and try again. The problem with misfires is that they are what generally slow down this process as allowing for too many misfires just leads to the generation algorithm repeatedly solving this puzzle.

So what type of results have I seen? I was getting normally about 75% of cells visible on most of these type two puzzles. That does not make a difficult puzzle. There would be the unique time where I would have about 60% of cells visible and those puzzles would be more challenging but they would normally take time to generate. Time is of the essence though so I didn’t like sitting around and waiting. Well, now I’m getting somewhere between 40-50% visibility on a fraction of the time. Sometimes its only a second or two (it was taking minutes under the old algorithm). This is not always true as I do still get sometimes a 75% visibility, but that is by far the exception rather than the norm.

The Beauty of Euler’s phi function

The recent conversation I had about number theory has brought it back into my awareness. In particular, the concept of beauty in numbers. I’m definitely not any kind of graphical designer or fashion expert but I do appreciate what I think of as beautiful, and there are certain areas of mathematics that are just beautiful.

But who am I to say what is beautiful? What really is beautiful? Rather than trying to talk about these things in terms of the abstract concept of beauty, I wanted to try to nail down some of the things I like about it.

In our early years we learn about shapes. Sometime later we learn about things like “regular polygons”. These are polygons where all sides have the same length. We also learn about stars, but the stars we learn to draw most often is the 5 point star that we can draw without lifting the pencil.

A natural question becomes are there other stars we can draw without lifting a pen? A 4 point star? a six point star? a seven point star?

Before we go into the ? function, lets make sure we’re on the same ground. We need to talk about common divisors.

Suppose we have two numbers, lets call them m and n. A common factor of m and n is a number that divides into both of them. For example a common divisor of 4 and 6 is 2 since 4 = 2 * 2 and 6 = 2 * 3. Two numbers are called relatively prime if their only common factor is 1. Remember that 1 is a factor of every number.

Euler’s ? function (called the totient function) of a number n is defined as the count of numbers less than n that are relatively prime to n.

n12345678910111213
?(n)112242646410412

To understand what’s going on in that table above, lets look at a number like 10 and ask what are the numbers relatively prime to 10?

n123456789
Factor 101*102*51*102*52*52*51*102*51_9
Factor n1*11*21*32*21*52*31*72*41*10
GCF121252121

So from this example we see that the numbers relatively prime to 10 are 1, 3, 7, and 9, so ?(10) = 4.

A nice property of Euler’s phi function is that for any n > 3, if ?(n) is 3 or greater, then we can draw a star with that many (n) points without lifting the pencil.

To do this, we first need to talk about modular arithmetic. If we have two numbers, a and b and want to add them modulo some number, written
(a + b) mod n
We take the remainder of (a + b) when this number is divided by n.

For example, if we wanted to calculate (3 + 5) mod 7 we would first compute (3 + 5) to get 8 and then realize that 8 = 7 * 1 + 1. This gives a remainder of 1, so (3 + 5) mod 7 would be congruent to 1.

If we are considering drawing an n pointed star, we can start with a number that is not 1 and is relatively prime to n and continually add that number to itself. What will happen is that because this number is relatively prime to n, it will visit every other number before returning to the number 0.

What is more is that there may be more than one n pointed star that we can draw. The number of stars is (?(n) – 2) / 2. So for 10, it will be (4 – 2) / 2 = 1. This can be seen below.

I wanted to allow users to begin to see more of this beauty, so I wrote a script showcasing it.

Pascal’s Triangle

I had a recent conversation with a friend who asked me “what makes number theory interesting?”. I loved the question, mainly because it gave me an opportunity to talk about math in a positive manner. More importantly though, it was an opportunity to talk about one of my favorite courses in mathematics (along with discrete mathematics and set theory). As much as the current day seems to focus on joining Number Theory with Cryptography, when I answered this question I wanted to make sure I didn’t go that route. Numbers are beautiful in their own right, and one of the things about Number Theory that was so interesting was simply the ability to look at all the different questions and patterns and properties of numbers discovered.

To answer this question, I started listing numbers to see if she noticed a pattern, but I did it with a “picture”.

.
..

….
…..
……

and I asked two questions

  • How many dots will go on the next line
    and
  • After each line how many dots have been drawn in total?

Lets answer these questions:

Dots# on this line# in total
.11
..23
36
….410
…..515

There were a lot of directions I could have taken this conversation next, but I decided to stay in the realm of triangles and discuss Pascal’s triangle. This is a triangle that begins with a 1 on the first row and each number on the rows beneath is the sum of the two cells above it, assuming that cells not present have a value of zero.

So the first five rows of this triangle are

1
11
121
1331
14641

This is an interesting and beautiful triangle because of just the number of patterns you can see in it.

  • Obviously there are ones on the outside cells of the triangle.
  • One layer in, we get what are called the Natural or Counting numbers (1, 2, 3, 4, 5, …) .
  • One layer in, we can start to see the list of numbers that I was showing my friend (1, 3, 6, 10, 15, …).

There are several other properties of this triangle and I wanted to allow users to begin to see them, so I wrote a script highlighting some of these patterns.

Set Partition Problems

This is my first post of 2019 and my first post in a while. There was one posted a few months ago, but not really geared towards the algorithms and learning focus of the site. I have been doing a lot of coding in my spare time, but honestly life has just gotten in the way. Its not a bad thing, but life is life and sometimes I have to prioritize the things. In particular, I have been having ideas and actually coding things up but the time it takes to clean up code, write a blog entry and finding a nice way to visualize these things has been something that I haven’t been able to really focus on as much as I’ve wanted to.

That said, I want to talk to you about the Set Partition Problem today. You can go to Wikipedia to get more information about this problem, but I will give you a brief introduction to it and then talk about two different approaches to it. The problem assumes that we are given as input a (multi)-set S. The reason we say it is a multi-set and not a simple set is because we can have the same element appear multiple times in the set. So if S1 = {2} and S2 = {2, 2}, then although as sets they are both equal to the set {2} = S1, as multi-sets allow for multiple instances of an element. The elements of S are assumed to be positive integers.

So given this multi-set S, we ask the question of can the elements of S be divided into two smaller multi-sets, C1 and C2 where

  • C1 [union] C2 = S
  • C1 [intersect] C2 = [empty set]
  • [Sigma]_[x in C1] = [Sigma]_[x in C2].C1 [union] C2 = S, C1 [intersect] C2 = [empty set], and [Sigma]_[x in C1] = [Sigma]_[x in C2]

The first two bullets above say that the sets C1 and C2 form a partition of S. The third bullet says that the sums of the elements in the two children multi-sets are equal.

This problem is known to be NP Complete. This means that it is one of the more difficult decision problems. Because of this finding an algorithm that solves this problem exactly will generally take a long running time. And finding an algorithm that runs quickly will more than likely be incorrect in some instances.

I will show you two approaches to this problem. One is based on Dynamic Programming (DP) and one is based on Greedy Algorithms. The DP version solves the problem exactly but has a slow running time. The greedy algorithm is fast but is not guaranteed to always give the correct answer.

Dynamic Programming is based on the principle of optimality. This says that in order to have a correct solution to the overall problem, we need optimal solutions to all subproblems of this problem. This is done by keeping track of a table which can be used for looking up these subproblems and the optimal solutions to these subproblems.

For this problem, we will build a table where the rows represent the final sums and columns represent subsets of the given multi-set (containing the first 0…n elements). The question we are repeatedly asking is “can we find a subset of the set in this column whose sum is exactly the given rowsum?” Here is an example of the DP algorithm on the multi-set {5, 6, 5, 6, 7}.

Greedy Algorithms are generally based on sorting the elements based on some principle and using that to try to answer the underlying question. The main problem with this approach is that it is very short sided because they do not look at the overall picture. Such algorithms are known for finding local optima that are not always globally optimal. The benefit to these problems though is that they are generally easier to code and easier to understand.

For the Set Partition Problem , the Greedy approach is to sort elements in descending order. Once this is done, the goal is to keep two subsets while iterating through the array, adding the element to the smaller of the two sets whenever possible.

For more examples, check out Set Partition Problems