While solving sudoku manually is enjoyable, its inherent combinatorial nature presents an interesting algorithmic challenge. As such, with newfound freedom during the winter break, I decided to take on the task of developing a generalized solution to automatically solve sudoku puzzles. In this article, I’ll pull back the curtain and show how the sausage gets made, walking you through the ideas and techniques behind my attempt at a sudoku-solving solution.

a naive and terrible approach

As with most puzzles, sudoku has a wide variety of tricks and strategies that make solving it slightly easier than coming up with a novel technique each time a person attempts to solve it. One such techniques is called the “naked single,” where a certain cell is ‘predetermined’ in that there is only one possible candidate for that cell. For example, in the puzzle above, the cell in the 8^th column and 8^th row can only be satisfied with 3:

Such cells are effectively ‘freebies’ and my original idea was simple, given a puzzle state, fill out all naked singles, recompute the list of naked singles for the modified graph, and start again. For easy (foreshadowing!) sudoku puzzles, this works fairly well as solving the forced cells clears up collisions for some of the other cells, potentially making them forced and as such, leading to an entirely solved state. If only, all sudoku puzzles were this trivial.

To put my implementation to the test, I optimistically dove straight into the ‘Hard’ level of the New York Times’ sudoku of the day and realized a massive flaw: not every puzzle is guaranteed to have a naked single and faced with that situation, my implementation dies an inglorious death.

I attempted to resolve this situation through two methods, each of which yielded no meaningful results though they still provided valuable insight. At first, I attempted to solve this problem by turning it into a massive recursion tree that explored every avenue for each of the 2-value cells, that is, cells that, in their initial state, could be satisfied with one of two values however this proved to be fairly slow and unreliable especially since, again, 2-value cells are not guaranteed. My other approach was to introduce randomness when attempting to resolve some cell collisions, which does appear to be a valid approach but I was not able to figure out the specifics needed to get it to work. Instead, I had set my sights on approaching this problem as a graph coloring problem.

a vibrant approach

Much like John Coltrane’s Giant Steps or David Bowie’s Starman, vertex coloring is one of graph theory’s greatest hits. Simply, given a set of connected vertices in a graph, vertex coloring is a way of labeling the vertices such that two neighbor vertices, that is, vertices that share an edge, are labeled with different colors. One of its more famous results is the Four Color Theorem which states that no more than four colors are required to color any arbitrary graph with the aforementioned restrictions on neighbor vertices sharing colors. However, this isn’t necessary for solving sudoku puzzles with graph theory. Solving sudoku requires reducing the puzzle to a vertex problem.

The goal of Sudoku is that each row, column, and sub-grid must contain each of the digits from 1 to 9 exactly once. Alternatively, this can be understood as: for every cell, no other cell within the same row, column, or sub-grid may have the same value. Viewing each cell as a vertex and the values as colors, it’s easy to create a bijection between a sudoku grid and a graph.

Edges are created between nodes if they share a row, a column, or a sub-grid. The graph does not look very dense in terms of edges because a lot of them overlap in the preceding visualisation but trust me, it’s dense:

Now, the idea is to look at each vertex and start coloring them in with one of 9 colors. If a certain coloring results in a vertex color violation, that is, two neighbor vertices share a color, the algorithm learns that the current coloring is unviable and ‘backtracks‘ to a previous state to attempt another coloring. If this sounds like brute-force to you, then your suspicions are correct! However, in a way, this is a ‘smart’ brute force algorithm as it builds towards a better candidate iteratively instead of blindly checking each one of the 6,670,903,752,021,072,936,960 filled sudoku grids.

Eventually, following the aforementioned backtracking algorithm, a valid coloring is found which represents a solved sudoku puzzle:

Looks neat doesn’t it. Each color in the representation corresponds to a value that can be used to solve the puzzle. Interestingly, this highlights an underlying property of Sudoku: for a given puzzle layout, there are 9! distinct ways to arrange the numbers, resulting in puzzles that are equivalent up to permutation of the values. Some fun group theory at play here.

Regardless, I was confident that backtracking always produces a valid solution and, again, to test, I tried my implementation against the ‘Hard’ puzzle for today’s New York Times sudoku puzzle and I’m glad to report that I was able to solve it!

conclusion

The backtracking approach is fairly efficient and reliably solves classic sudoku puzzles in a way my original attempt could only hope for. In a way, backtracking is similar to an improvisational jazz solo that attempts to stick the landing by constantly improving and hiding mistakes so well that you’d never realize they were mistakes in the first place. Personally, this was a fun exercise in problem-solving, and I thoroughly enjoyed learning applications of graph theory in the context of combinatorial algorithm design. Ultimately, this project has reinforced my belief that sometimes the most elegant solutions come from the simplest yet most powerful algorithms, proving that with a little creativity, even the most challenging puzzles can be solved step by step.

references

• My repository for this project: [Github link]
• Ishaan Gupta’s Medium Article on the same topic that focuses a lot more on the implementation details
• Solving Sudoku puzzles with Graph Theory by Alejandra Ortiz Duran for good theoretical explanations

Addressing the first question: ‘Is it possible for an audience to explicitly recognize when they are receiving a message incorrectly?’ In a way, the solution is trivial: when they receive your message, you stand next to them as they read it and tell them if it matches the message you sent.

Or perhaps, flood the receiver the copies of the message so that they can look at all of them and pick the most consistent message between them. Both of these approaches are hilariously flawed.

The idea of sending something else to verify the message on the other hand is a step in the right direction. Consider this idea: for a message m, say “cow,” I compute a number s where is the sum of the positions of the letters of m in the alphabet, so for “cow,” it would be 3 + 15 + 23 = 41. The sender could send this sum along with their message and the receiver could check (almost like it’s a checksum) if their computed value matches s. For instance, if the message was miraculously smudged to be received as “pig” then the receiver would compute 16 + 9 + 7 = 32 and see that it does not match s = 41 and ignore the faulty message. This looks promising however it has a fatal and perhaps obvious flaw, anagrams.

Consider “dog,” the checksum for m is 26 given from 4 + 15 + 7 however if the receiver reads it as “god,” they compute the checksum to also be 26. This a problem! The message received does not match the one that was sent however the receiver is convinced that it’s the correct message however, they’re probably baffled as to why you asked them to take god out for a walk.

The goal now is to encode both the characters and the location of the characters. When I was presented with this problem for the first time, my attempt at a solution was to encode ordering by raising each character to a prime. For example, “dog” would go from 4 + 15 + 17 = 26 to 4 + 15² + 7³ = 572 which would differentiate it from “god” with 7 + 15² + 4³ = 296. This approach however, gets unwieldy fairly quickly, imagine a ‘z’ as the 100th character of a message (26⁵²³ has 741 digits). Evidently, a terrible idea but it does help characterize what a good checksum should do, that is, efficiently identify a message. Enter hash functions: a powerful tool for error detection.

A hash function is any function that takes some arbitrary length message as input and outputs a fixed length value. An additional property that some hash functions have (or at least strive for) is that given a hash function, you should not be able to efficiently find two unique values such that they have the same output value. Note: hash functions are guaranteed to have collisions given that they map values from a bigger set to a smaller set and as such, cannot be injective and this is formalized through the birthday attack. The birthday attack is a phenomenon where, due to the limited size of possible outputs, collisions become more likely as more messages are hashed—like how two people in a group of 23 have a high probability of sharing a birthday. This, however, is not a problem as some hash functions make collisions statistically infrequent.

Backing up to the dog-god example and using MD5 to hash them, I get “dog” = 06d80eb0c50b49a509b49f2424e8c805 and “god” = a4757d7419ff3b48e92e90596f0e7548 which are unique and can be computed deterministically by the reciever suggesting correctness with high confidence.

To answer the first question, yes, it is possible for an audience to explicitly recognize when they are receiving a message incorrectly. A simple setup involving hash functions would go as follows: take message m and pass it through the hash function H(x) to get the checksum H(m) = s and send (m, s) as the message. Upon receiving the message, the receiver computes H(m), and if the output matches s, they can have high confidence that the message they received was the same as the one that was sent.

This setup works wonderfully and there are many different families of hash functions that are used for error detection including but not limited to MD family, SHA family, and CRC. It should noted that there are other ways to detect errors that do not involve hash functions and checksums but for brevity, I’ve chosen not to highlight them here.

This leads to the second question, is it possible to fix a message that is known to be corrupted in some manner? The answer: yes, but up to a limit. To explore this, I will abandon the abstraction of using words to represent messages and instead rely on bit streams.

Consider m = 110001000101 and consider corruption as a bit flip, that is, 1 -> 0 or 0 -> 1 for some arbitrary bit in m. If I receive m’ which is not the same as m, then I want to somehow get m without knowing m. This is a conundrum to be sure but Richard Hamming had a key insight: if you know where the error is, then you know the corrected message given that the message is just 0s and 1s. He used this insight to create one of the first error-correcting codes, now called Hamming codes.

The idea with the encoded message is that if a bit is flipped in it, then upon using a checking process, the output would be the index of the bit that is incorrect allowing the receiver to correct the bit and thus obtain the correct message. For instance, I encoded my original message as the first matrix above and m’ represents a corrupted matrix. Using the checking process, I get that the value at the 2nd index (1-indexing) is incorrect which is visually apparent as well. The details of the checking process are a bit beyond the scope of this article but I would highly recommend checking out 3Blue1Brown’s video on this topic if you’re interested!

This was an example of an error correction code that can fix corrupted messages. They almost seem like magic however, this is just clever mathematics and they do have limits, notably, if you flip enough bits, the original message is entirely unrecoverable. Certain algorithms like Reed-Solomon have higher tolerances for bit flips but even then, you cannot turn any arbitrary message back to the original message. Additionally, the error-correcting algorithm does not know the original message and instead, it does its best to fix a corrupted message. As such, there is no guarantee that a ‘fixed’ message makes sense at all.

This brings the dilemma of picking between error detection and error correcting codes. Error detection serves to discard corrupted messages and in some cases, like in scientific computing this is preferable as wrong data is usually considered worse than null or missing data, and given higher tolerances, it’s possible to figure out when a message has been corrupted under most conditions. On the other hand, error-correcting codes are useful when they can be applied as fixing data means potentially lossless communication (though, this is obviously far from reality). They have their benefits but in theory, they offer solutions to the questions posed at the start of this article, is it possible for an audience to explicitly recognize when they are receiving a message incorrectly? If so, could the received message be corrected? The answer: a resounding yes!

While human communication remains inherently flawed, technologies like error detection and correction remind us that with the right tools, even the most chaotic systems can achieve clarity.

In fact, given how scientists understand the world as it is today, traveling back in time seems almost impossible. If it was, I’d say it was incredibly rude for our future time travelers to not show up to Stephen Hawking’s Time Traveler party. There remains one possibility then, the future. The answer, of course, is really simple: we’re doing it all the time, in the 196 words I had written up to this point, I’ve traveled about 30 minutes into the future. However, I’ll gladly admit this is the rather boring answer because there’s one other answer, and to talk about it I have no choice but to bring up the king of modern physics himself, Albert Einstein.

In 1905, a 26-year-old Einstein would author 4 papers, known today as the annus mirabilis papers, that would shape most of modern physics. Of those papers, his third paper would introduce the world to special relativity. While relativity as a concept predates Einstein’s special relativity by a few centuries (Galilean invariance), his theory is unique in that it fundamentally ties the idea of space (the area we move around in) to time which was not the case before him. Before Einstein’s paper, the assumption was that if two events, say firing two guns, happened at the same time for one observer moving at some velocity, they will also appear simultaneous to another observer moving at some other velocity but according to special relativity, firing the two guns can be simultaneous for one observer and asynchronous for another. It boils down to this: the way we perceive time and distance does funky things as objects approach the speed of light.

While changes to length are interesting in their own right, what I’m interested in here is the way time changes at high velocities. First, let’s establish some terms, starting with proper time: the time interval I, as the moving observer, measure. For example, if I use a stopwatch to measure the time it takes me to drive between two places, that time interval would be the proper time. This time is invariant, that is, irrespective of what velocity I travel at, this interval of time does not change; it is how I while moving perceive time. However, if a stationary observer attempted to find the time it took for me to drive between two points from their non-moving perspective, that would be dilated time, and this time interval will never be shorter than the proper time.

With this in mind, you could, in theory, travel for 15 minutes in your car but someone outside the car could perceive it as 30 minutes; you effectively travel through time faster than someone else. I think that’s pretty cool but I must admit, I’ve exaggerated the time travel aspect by quite a bit. The relationship between the proper time and the dilated time is represented by the following equation:

Where t₀ is the proper time, t is the dilated time, and γ (gamma) represents the Lorentz factor. This factor is a part of a larger set of transformations between frames of motion, usually two with one moving at velocity v and the other being stationary, known as Lorentz Transformations and essentially, define how positions and time would be perceived between two frames that are moving relative to one another dependent on the velocity of the moving frame.

This graph represents the value of the Lorentz factor as the (v/c)² approaches 1. Given the shape of the curve, it’s evident that you would have to travel at a significant fraction of the speed of light to experience any measurable effects of relativity. For reference, the other day I had to take an 8-hour flight in a Boeing 747 which travels at about 274m/s (~300m/s), and at that speed, the Lorentz factor would be 1.0000000000005, which means that across the entire 8-hour flight, I would experience 1.4999 * 10^-8 fewer seconds than if I was not on the flight. That is almost unperceivable, that too on one of the fastest modes of transport that most people can access. I did travel 1.4999 * 10^-8 seconds into the future but to experience any significant time dilation, I would have to travel at a higher velocity, a MUCH higher velocity.

Is that it then? Well, there is another way to bend time but unlike this method, where we can make a body move at a high enough velocity, we cannot control the effects of General Relativity. Special relativity assumes a flat space but due to large masses, like stars and black holes, spacetime is curved and this does even funkier things to how time is perceived and this is known as general relativity. As much as I’d like to delve into that right now, I do not think I can do it justice in the same article so for now, I will end my discussion on time travel.

I had this idea while I was sitting at O’Hare International in Chicago, waiting for my flight which had so kindly been delayed multiple times. I did make it home, eventually but with no internet access, a few downloaded articles and music, and Wolfram Mathematica, I found a way to kill time which I think is ironic considering the content of the article. Regardless, as the new year begins, I hope to write more if time permits and as always, thanks for reading!

While the dartboard was just an example, and a rough one at that, this is a very real method used by statisticians, physicists, and economists to model complicated relationships between variables when analytical methods do not yield an appropriate answer and it is known as the Monte Carlo method. By definition, the method refers to a statistical technique to model probabilistic systems and establish the odds for a variety of outcomes.

I first read about it when reading about Riemann sums as a method of approximating definite integrals which takes the area under the curve of the function that is to be integrated and ‘fills’ it up with rectangles with constant width and length dependent on the y-value of the function for a domain and then adds the areas of the rectangles which would result in a value pretty close to the value obtained from using analytical methods to obtain an integral function and then use it to find the area under the curve.

It should be pretty apparent that with thinner slices, the area under the curve can be approximated better, and if you ditch the necessity for rectangles and opted instead for trapezoids, you could come pretty close to the real value of the area under the function and the Monte Carlo method operates similarly, however, instead of having progressively thinner rectangles, researches opt to use randomly placed points to ‘fill’ out an area and then using it to come to a solution. It should be noted that even though approximations made using the method can be very accurate, like Riemann sums, they are and will always remain approximations and thus not the true solution to any problem being attempted.

To illustrate, I will now calculate the value of π (Pi) using the Monte Carlo method by establishing the ratio between a unit square and a circle inscribed inside of it:

 Since the side length of the square is equal to the diameter of the circle, that is, s = 2r:

By rearranging and canceling terms:

The derived expression for π is pretty neat but effectively useless to calculate the value itself because all I have done here is effectively establish a theoretical relationship. This is where I can use the Monte Carlo method to approximate the areas of the circle and the square with dots.

If I randomly place dots on the square and count the number of dots that were inside the circle as compared to the number of dots placed in total within the confines of the square, I am, essentially, calculating the area albeit by a very tedious and slow process. Thankfully for me, I have a working knowledge of Python and I wrote this script to place points for me and then use it to find the value of π.

It takes over 10⁴ dots to arrive at the commonly accepted 3.14 which takes a while to compute and quite honestly, this is not the most efficient method of calculating π, especially when infinite series like the Madhava-Leibniz Series exist that can achieve this level of accuracy within a few terms but that’s exactly how it’s supposed to be. This should never be the first method used to find a solution or a relationship between variables but rather a last resort. A constant as important and common as π in mathematics has many, MANY, different ways to be calculated, ranging from calculus to complex numbers, and that’s why using this method doesn’t really make sense however when trying to establish a new relationship, this method at least provides an approximate which can be verified and perfected over time.

Attempting to use the Monte Carlo method is, fittingly, like rolling dice in a casino such that as you spend more, computationally or financially, you are more likely to get to the solution/prize you want, however, beyond a point, it just results in diminishing returns since the cost does not justify the end and you’re probably better off trying to find other methods to get whatever you desire.

With that, I bid you adieu!

Okay, first: I must define what sorting is and what I intend to talk about in my article. Sorting, put simply is just arranging things in an order according to some value attached to each item (in the case of the Magic cards, the mana value) or by putting them in groups or subsets on the basis of some common property (Magic cards could be sorted by their color, for instance) and while both are pretty cool in their own right, I’m more interested in the former type in this article.

I’ll start with defining my set of objects that I want to sort—these 5 towers of white squares:

With these 5 towers, my aim is to sort them according to the number of squares each of them contain, the smallest the biggest from left to right. Simple enough, right? Now, there are many ways to do this, but one of the most basic algorithms is called bubblesort or sinking sort, which involves comparing adjacent objects, and if the item on the left is greater in value than the object on the right, they will swap places otherwise, the algorithm will compare the next pair of objects for the same test. In the context of my set, the first object has 5 squares while the second object has 3 squares, so they will swap positions like this:

After the swap takes place, the algorithm moves on to the next pair, the 5-square tower, and the 1-square tower; here, again, since 5 > 1, a swap takes place and if you understand the logic here, you’ll see that eventually, the largest tower, in this case, the 5-square will end up at the end like this:

After the algorithm goes through the set once, the largest object will end up at the right end and we have the beginnings of an ordered set. If the algorithm is repeated, eventually, it will spit out the following ordered set:

Well, there I have it, a sorted list. I’m done, right? Nope, not really: I had to do so many steps to reach my desired goal, 7 swaps to be exact. Okay, on second thought, that’s not too much but that is more down to the fact that I was making a list of 5 towers. This would take an insane number of steps had I done this with my Magic cards, of which I own more than a thousand. What is the most number of swaps I have to carry out given I have a list of objects with n items if you think for a bit, you’ll realize that the number of swaps is n² which is quite a bit: if you took a thousand Magic cards, I could be forced to do up to a million swaps!

As I learned in my research, this value, n², is bubblesort’s worst complexity and this complexity is expressed by the Big O notation. In this case, it would be O(n²) since for a set with input size n, it can take up to n² steps to complete. Computer scientists and mathematicians spend a lot of their time optimizing algorithms so that their Big O value is as close to n as possible, which would be linear growth with input size unlike bubblesort here which grows exponentially.

As soon as I read about optimization, my first instinct, you might think, would be to find the most efficient algorithm, but you would be wrong. I chose to find the most inefficient algorithm and it’s called bogosort which is literally randomizing the list repeatedly until the list is sorted, which, as you can imagine, is quite possibly the worst idea I have ever read and mathematics backs me up, given its complexity is technically infinite since there’s no real upper bound for how many steps it can take to solve a set so on average, the number of steps would be O((n+1)!). Given the value uses a factorial, it should not be a surprise that the number of steps shoots up really fast; for reference, I was attempting to solve the 5 tower example with this method, bogosort would take 720 steps on average, 28.8 times the steps it would take bubblesort’s worst case.

Another algorithm that is famous for its inefficiency would be the aptly named bozosort which checks if the list is sorted and if not, swaps two random items in the list and checks again. This also has an infinite upper bound and an average of O((n+1)!). Needless to say, algorithms that make moves at random, that is, without a proper logic supporting their move, tend to do badly.

After satisfying my appetite for chaos, I moved over to the most efficient algorithms and here I learned a distinction that I feel I should point out. Multiple algorithms can have the same Big O value however this does not mean they would take the same number of steps for the same set, that is, some sorting methods are better suited for a set of data than others and thus there is no definite best algorithm because it really depends on the set at the end of the day.

With that out of the way, the optimized algorithm I liked the most throughout my research is called quicksort which really lives up to its name. In essence, it splits the sets by a pivot point and forces all values greater than the pivot to the right and all values lower than the pivot to the left. In my 5 tower example, it would have worked like this:

Once the swap takes place about one pivot, it moves on to repeat the process with the pivot situated somewhere in the middle of the divide sub-arrays. I found this gif on Wikipedia which illustrates it really well:

This process does the same sorting in considerably fewer steps even though its worst-case is the same as bubblesort, O(n²). The average Big O value is O(n * log (n)), with log base 10, which means with a list of 1000 items, on average it would take roughly 3000 steps which is really efficient in the context of sorting algorithms. If I had to sort something with a lot of items, I would probably use this algorithm because it is simple to understand and implement but also really efficient.

Another algorithm that I found interesting is selectionsort which is essentially a further optimization of bubblesort in that it reduces the number of checks by disregarding the values that have already been sorted at one end of the set. It’s a very obvious and surprisingly impactful optimization for an already pretty good sorting algorithm which shows that even seemingly good algorithms can be made better through clever trickery.

A further optimization of bubblesort is combsort which, like its inspiration, compares values of objects, however instead of checking adjacent starts with a gap between the objects and over time reduces the gap to fix all positions. Even though the average and the worst case are the same as bubblesort, it generally takes fewer steps to solve the same set of data than that of bubblesort.

I do want to highlight some other algorithms that I found interesting but do not understand well enough to confidently explain and they are mergesort and radixsort. They are incredibly efficient and perhaps just as complicated to explain in my article. If you find their names interesting, I implore you to explore them yourself.

With that, I conclude my dive into sorting algorithms and I should probably move on to sorting my cards. I should say that even though this research made me a tiny bit smarter, it left me worse off regarding my situation with Magic cards because the time I should have spent sorting them was spent looking at sorting algorithms. I’m left with an unsorted deck of cards and a clock that says 3:22AM. Great.

Thank you for reading this article! If you found this interesting in any manner, I would highly recommend checking out the following videos because they were among the first that popped up in my research and are sure to interest you! Thanks again!

I think, mathematics does seem extremely daunting and sometimes pointless, especially to those who’re maybe not as interested in the subject however, if social media is any representation, almost everyone enjoys reading about riddles and games that have come from the world of recreational mathematics. Not only because they’re generally fun but also because they’re not too complicated and built upon fundamental mathematical or sometimes purely logical concepts which encourage people who might be dissuaded by the complexities of math and just enjoy fiddling with stuff. While a lot of recreational mathematics might deal with puzzles or simple multiplayer games and the best way to win such games, what I wanna discuss in particular are zero player games, that is, games where the only thing that changes is the initial state of the game and the rest of the game is played through a set of predefined functions and to do that I have one in mind that I think you, the reader, might find interesting: John Conway’s Game of Life.

John Conway’s Game of Life or as I like to call it, GoL, is an example of a cellular automata, which yes, sounds complicated but honestly isn’t. Cellular automata refers to a variant within the automata theory which broadly studies and identifies systems that govern automated or self-acting machines. Cellular automata, as a name suggests, deals with such machines within a set of cells and each cell can have a ‘state’ which could be as simple as binary: 0 or 1; or be more complex like: up, down, left, right, a, b, start, end, et cetera; however however many the number of states, the number has to be finite. GoL is binary, 0s and 1s, with 0s representing ‘dead’ cells and 1s representing ‘live’ or ‘living’ cells.

Before starting each GoL, an initial state is defined, that is, some cells are defined to be live and others are defined to be dead and the game proceeds into generations where the new generation acts as the initial state for the following generations and on from that point on the basis of the following rules:

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

While this may seem rather boring on the surface because you’d assume a lot of these games just die off eventually, you’d be right… partially. While most of the basic initial states that you might come up with at the start will probably die off, if you keep trying out new patterns you might come across patterns that go on for infinity, either as static shapes or as moving objects on the matrix.

Some of the most interesting ones you could try are:

Glider

This set of cells will continue moving to the bottom right of the screen because according to the rules, the tail end of the glider keeps readjusting to force the other parts of the shape to move, forcing the tail end to move again, and repeat. On an infinite matrix, this would go on forever and it makes for some really cool spectacles. (John Conway regrets that he didn’t call this an ant in one of his interviews)

Block

Unlike the moving glider up above, this one just exists as it is forever because in this condition each of the cells live on for another day since they all have 3 neighbours, thus satisfying the condition to live.

Blinker

This one is dynamic in the sense that it never stops changing the shape across the dimensions however, it never moves. If you let your imagination guide you and squint hard enough, you might think that this constantly spinning on one defined centre cell.

While I have discussed some popular shapes that have interesting behaviours, these are barely scratching the surface of what’s possible within Conway’s Game of Life. There are insane machinations that are just amazing to look at and lucky for you, I’ve got some right here!

Gosper’s Glider Gun

If look up Conway’s Game of Life on Wikipedia, this is the first image/gif that appears on your screen and rightfully so, it’s a brilliant example of the complex things that can be created using such basic rules. What I have here is a constantly repeating generator which produces a glider every few generations and these gliders keep flying until the end of the simulation. If you think this is impressive, I think you’ll find the next one to be particularly mind blowing.

Life Breeder

What you saw before was a single generator making gliders however this; this is in an another league. The Life Breeder as it’s called makes many Gosper’s Glider Guns as it moves across a matrix which, as show before make gliders themselves.

I fortunately get to tell you that this is not even the coolest thing that you might find on internet for GoL machines, I found this video on YouTube that just blows everything I have just described to be out of the park:

Conway’s game of life made with Conway’s game of life; I really don’t think words do justice to describe how cool this is.

To see why these are, in any way, useful or important for us as just random people, I must go on a bit of a tangent and talk about Alan Turing.

Alan Turing is famous for many things such as his work on the Bombe to crack the German Enigma code and the Turing test for Artificial Intelligence however within computer science and math in particular, Turing machines. Turing machines aren’t physical machines but more of a conceptual or abstract machine that is supposed simulate computer algorithms. Imagine a machine that does just one thing on the basis of set of instructions all the time like one of these things:

As you might imagine, it would be impractical for us to make different Turing machines for each task we’d like to do, people came up with systems and machines that could simulate different Turing machines within the confines of the system’s rules. If you’re reading this article, you’ve used a mobile/desktop which are examples of such machines.

What this leads into is the concept of Turing completeness: the idea that a system, like the ones described before, can simulate any kind of Turing machine possible. That is, you could make anything within the bounds of the some system. Almost all programming languages are Turing complete and Conway’s Game of Life is no different.

Conway’s Game of Life is perhaps one of the best of examples of how the most simple rules can be used to create complex and functional machines, like for example, if you wanted to create a computer like the one you’re using right now, you could create one with GoL, given of course, you’re willing to put that time and effort into it. People have been obsessed with creating contraptions within GoL for decades now and it hasn’t reached its peak yet because in all honesty, it never will because the possibilities within bounds that this system set are limitless.

With that, I conclude my tangent and by extension this article which has dragged on quite a bit. Before I put down my usual end text, I have a few things to share if this topic interested you:

1. ConwayLife.com – A website with tons of documentation on, you guessed it, Conway’s Game of Life along with a decently active community where people share their creations/ideas
2. Golly – A software you can download to play around with GoL and other such systems if you don’t want to make your own engine
3. Wikipedia – This goes without saying but I’ll say it anyway: Wikipedia had tons of graphics and explanations for everything related to GoL and if you’re looking for a place to start, wikipedia is the way to go.
4. My GitHub – I made an environment to test out GoL and if you like you want to make one for yourself, you can look at my code for inspiration : )

That being said, I hope you enjoyed reading this article as much I enjoyed writing it. I will hopefully write more in the coming weeks with topics that are just as or even more fun to learn about. Until then however, thanks for reading as always.

//credits – Wikipedia for all gifs related to the structures

Well, what is tau then?

Tau is a mathematical constant that is defined as 2 times Pi and it’s significant because some mathematicians believe that Tau has more uniformity within mathematics that Pi simply doesn’t have. Tau reached its current cult following because of an article written by Bob Palais in 2001 called Pi is Wrong! and the all-famous, The Tau Manifesto by Micheal Hartl (he manages a website called tauday.com which you should really check out if this interests you!)which serve as inspirations for this article.

Now please prepare as I begin to explain why you too should use Tau instead of Pi in your daily lives!

Let’s begin with a simple definition of Pi. In math, Pi is defined as the circumference of a circle over the diameter of the circle, as follows:

Pi = C/d

However, we define circles as a round plane figure with a boundary with points equidistant from the centre of the circle, or a radius r away from the circle. Radius and diameter are fundamentally not the same thing beyond the basic d = 2r point. Radius is used to define the very existence of a circle while diameter simply refers to the width of a shape. While circles are special in the sense that their width never changes irrespective of what angle or orientation they are in, many other geometric shapes also have that property but radius is fundamental to the circle and unique to it and its variants. Therefore, an argument is made that Pi, being the circle constant, should be defined using fundamental circle values like radius, like this.

Tau = C/r

Since r = d/2, Tau would be twice of Pi. ‘How is this relevant though?’ you may find yourself asking but you must realise that 2pi, as a set appears all too frequently within mathematics and physics. I’d love to delve into all the most significant places where you might find 2pi but I don’t think I could do them justice if I were to attempt to explain these so here are some that I personally know a decent bit about.

Gaussian normal distribution
I’ll be first to admit that statistics in isolation doesn’t excite me too much but normal distribution is a bit of an exception to this rule. I think it’s fascinating, especially the graph that it produces.

This graph is defined using an extremely peculiar looking function which is as follows:

If look at the denominator, you’ll see 2pi sitting right there. If you were to replace this with tau, it would look significantly better and more palpable to the reader.

Radians
While most of us do learn trigonometry with the help of degree angles, from 0 to 360, a common way to write angle is to write them in radians. The conversion goes as follows:

angle(d) * pi/180 = angle(r)

However, if you know your circle measurements, you’d see that for half a circle, that is 180 degrees, the corresponding value in radians is simply pi, which means that the angle in radians for a full circle is 2pi.

Also, due to conversion between angles and radians, there are some really unintuitive values that lead to many errors, for example, 1/4th of a circle corresponds to 90 degrees, which is, 1/4th of 360, simple right? But, 1/4th of a circle corresponds to 1/2 of pi, or pi/2, which is just weird. It might not seem strange to people who’re experienced in math but that’s because we’ve become conditioned to think this is okay which it most certainly is not.

This would also change how we look at trigonometric functions, specifically sin and cos, since those will complete oscillation at simply tau units away from the origin instead of 2pi units away from the origin.

I’m sure you can see where I’m going with this but to simply make it more obvious, 2pi is just a tedious expression when tau appears to be more useful due to the sheer frequency of times we have to use 2pi and it makes more sense on a fundamental for the circle constant.

There are so many more things that I’d like to discuss here but I risk not finishing this article in time for the day in question and simply because I think you should really check this out because Michael Hartl understands mathematics more than a high schooler.

I hope you enjoyed reading this article on tau on a special day; treat yourself with 2 round shaped meals instead of the normal 1 round shape meal for pi day. I’ll try and write more often but for now, this is it. As always, thanks for reading.

While there are many, MANY, different, methods of encrypting data, one of the most popular and oldest is the caesar cipher, named after the member of the First Triumvirate, Julius Caesar. It’s named after Caesar since he was, according to records, the first person to use such a cipher, mostly for strategies and private conversations with other upper class men.

This cipher is a staple example of a substitution cipher, which, in simple terms, means that each letter is replaced, or substituted, with another to encrypt text. While substitution ciphers do not need to have a pattern, caesar cipher is special since it uses a ‘shift’ as a pattern for encrypting messages. For example, the following table shows a shift of +1, which I will be referring to as n following this.

If you notice, each alphabet is represented by the alphabet that is right after in the general sequence and if the letter to be represented is ‘Z’, the letter at the start is chosen, that is, ‘A’; for example:

Can you tell I’m hungry?

The words in the second column seem like gibberish and only people who know that this has been encrypted using a caesar cipher with n = 1 will be able to figure out the true meaning behind the text. It should be noted that even though I’ve only used n = 1 for my example, caesar ciphers can have shifts all the way from -25 to 25, since |n| = 26 would mean that you’re back at the original text.

For reference, if the encryption key, or basic shift is n, then the decryption key is always n * – 1.

If you want to try out this cipher yourself, I’ve made a python equivalent which you can check out right here: Github link

As I alluded to before, even though this cipher was effective back in Caesar’s era, it’s practically worthless as an encryption system in today’s world. If someone wanted to check through all possibilities for this cipher, they alone could probably crack it in 10 minutes since there are only 50 possibilities to go through. This is considering the person trying to figure it out doesn’t have a computer, which would almost completely get rid of any time required to find the solution to the encryption. You could just choose to brute force the system, and have a computer print out all the possible solutions to the encrypted text, or you could try and guess the key used in encryption.

I want to talk more about the second option, so here it goes: English has a language, isn’t equal to all of its characters, that is, some are used with way more frequency than others. For a more definite spread, refer to the following graph that I found on Wikipedia:

With this information in mind, you must remember that this is merely a substitution cipher, which means, each alphabet is represented by another character, and always that character. In others words, if I had to represent the letter ‘A’, the encryption system would always replace it with ‘B’ if the shift was set to 1 or ‘C’ if the shift was set to 2. That means, the distribution in the graph hasn’t been altered, it’s just the values on the x-axis.

You could try and figure out the frequency of characters in the encrypted text and refer to the graph to see which letters have the same frequencies in both places and adjust the decryption key according to that. Through trial and error, it should give you the key used to encrypt efficiently. This could, naturally, be automated using some computer script and not only would you have to scour through the brute forced solutions but it’s also universal and it would work for all following encrypted texts.

I hope you enjoyed reading this article as much as I enjoyed writing it. I’ve been reading The Code Book by Simon Singh and have spent tons of time reading about r/A858 which made me curious about cryptography, encryption, and everything else along those lines. This was an extremely simple yet fun topic to explore and hopefully, I’ll write about the others that find interesting. I’ll see you soon, and as always, thanks for reading!

As division works, if you divide a number, for the sake of the example, 5, by 1, the answer would be 5. Now, if you divide 5 by 0.1, the quotient would be 50, and as follows:

5/1 = 5
5/0.1 = 50
5/0.01 = 500
5/0.001 = 5000

This suggests that the closer the denominator gets to 0, the larger the quotient is so a naive solution to x/0 would be infinity (∞) however, I’d like you to consider taking the following:

5/(-1) = -5
5/(-0.1) = -50
5/(-0.01) = -500
5/(-0.001) = -5000

According to this logic, as value of denominator approaches 0 from negative numbers the quotient starts to get closer to negative infinity (-∞).

What is 5/0 then? Is it positive infinity or negative infinity? This has pretty much all mathematicians stumped since we can’t define it as a single value.

Ok, you say, what if we just made a new notation or not define 1/0 as infinity, irrespective of what sign precedes it. Well, beyond the fact that this logic has a very clear loophole in it, there is actually a way to show that we cannot define 1/0 as infinity and it goes as follows.

If 1/0 = ∞, then ∞ * 0 = 1

However this fails since we know that anything multiplied by 0 is equal to 0 and since we know that 1 is not equal to 0, we can safely say that 1/0 is not equal to ∞.

While the actual logic behind what is 1/0 ends here, I really want to show you how the graphs for functions that approach x => 0 with x in the denominator look like and I’ll do that using desmos:

Hope you found this at least mildly interesting and I’ll write again (hopefully without the 2 week hiatus) and as always, thanks for reading!

Most people, on the basis of intuition, would say a number in the hundreds, while some might say in the thousands (which would be absurdly wrong) but the real answer is 23. Yup, 23; pretty small right? You might be wondering, how? Surely this doesn’t seem right? However, using the power of math, you’ll easily see how this is true.

How many pairs of people can we define in a room with 23 people? If your answer is 22, then you’re a tad bit selfish because we aren’t looking for pairs with you but rather, any pair. Therefore the real number of pairs that can exist in a room with 23 people would be 253 by the following calculation:

(23 * (23 – 1)) * (1/2) = 506/2 = 253

Well okay, 253 pairs, that’s one part of how we get to 50 percent, what’s next? Next, we’d have to define, what is the chance that someone’s birthday is not the same as the other. If there’s a (1/365) that they have the same birthday, the chance that they don’t have the same birthday would be 1 – (1/365) by the following logic:

P(A) + P(A’) = 1
P(A’) = 1 – P(A)
where P(A) is the chance they have the same birthday

1 – (1/365) is (364/365) and now that we have that, we can define the chance that given 253 pairs, what is the likelihood that there are no pairs with same birthdays and we can do that using the following expression:

P(A’) = (364/365)²⁵³ = 0.4995

Since P(A’) = 0.4995, P(A) would be 0.5005, that is, there’s a 50.05 percent chance that a pair of people would have the same birthday in a room with 23 people. Pretty cool right? The Birthday Paradox goes to show how sometimes our intuition betrays us and we should really put more thought to seemingly easy question statements.

For a more generalised solution to a problem with n people, the following logic works:

Pairs = ((n)(n – 1))/2 = p
Chance = 1 – (364/365)^p

I hope you enjoyed this strange little article on birthdays in my attempt to connect events in my life to mathematics. Once again, thanks for reading this one, and I’ll come back soon with other cool things I read about.