# The SQL of the Game – Conway’s Game of Life

Joe Celko recently published a challenge to implement Conway’s Game of Life in SQL. At the start of this game, each cell of a 10×10 grid is either occupied or unoccupied by an imaginary creature that Celko calls a Merkle. Each turn, Merkles that have fewer than two neighbors die of loneliness while Merkles that have more than three neighbors die of overcrowding. Unoccupied cells that have Merkles in exactly three neighboring cells grow a Merkle. This game is a form of cellular automaton.

One of the main obstacles to implementing a model like this in SQL is that the new state of each cell depends on the state of the adjoining cells. One common method of solving this problem is to join the table representing the cells to itself eight times, as seen in the first comment to the Celko article. However, eight self-joins can get very costly. The solution I outline below solves the  problem with a single join.

My solution depends on three premises: (1) we know the size of the grid; (2) we can represent each square in the grid by a single address (instead of an (x,y) coordinate pair), and (3) given the first two premises, we can derive the addresses of all neighboring squares for any given grid square by mathematical operations on its address.

Of course, we know the grid size for this Game of Life exercise: 10X10. We can represent the squares in the grids by numbering them sequentially starting in the lower left corner (it really doesn’t matter which corner is number 1 – I do it this way because it reflects the standard Cartesian coordinate system with the origin (0,0) at lower left):

With a little study of this grid, the mathematical relationships between a cell address and the addresses of its neighbors become clear. For most cells, the addresses of the eight neighboring cells can be established by the following formulae (where c = cell address), based on the known y dimension of the grid (10):

``` c + 1 (the cell to the "north") c + 10 + 1 (the cell to the "northeast") c + 10 (the cell to the "east") c + 10 - 1 (the cell to the "southeast") c - 1 (the cell to the "south") c - 10 - 1 (the cell to the "southwest") c - 10 (the cell to the "west") c - 10 + 1 (the cell to the "northwest") ```
Some special conditions have to be applied for cells along the “north” and “south” edges of the grid, though, because cells on the north edge won’t have neighbors to the north (for example, cell 10 does not have cell 11 as a neighbor) and, likewise, cells on the south edge won’t have neighbors to the south. Cells on the north edge of the grid share a distinct characteristic – dividing their addresses by 10 leaves a remainder of 0. Cells that meet this condition will have no northern neighbors. Likewise, cells on the south edge of the grid share a distinct characteristic – dividing their addresses by 10 leaves a remainder of 1. Cells that meet this condition will have no southern neighbors. Similar conditions could be applied to the cells on the “east” and “west” edges of the grid (using whole number portion of the quotient of the cell address divided by 10, instead of the remainder, to identify the affected cells), but since the grid numbers for their eastern and western neighbors don’t actually exist,  this isn’t necessary (the fact that the formula yields the nonexistent cell -6 as the western neighbor of cell 6 will not affect the outcome). The code below shows how to implement these conditions.

Now that we can identify the addresses of neighboring cells, we can join each cell to its neighbors in one self-join, and, if we represent the status of each cell as a 1 for occupied and a 0 for unoccupied, determine the number of neighbors for each cell with the SUM aggregate function. From this result set, we can then determine how to update each cell to represent the outcome of a turn. The following code shows how to do this. As a little bonus, the stored procedure includes a bit of code that displays the starting state and the result of each turn in a grid with (x,y) coordinates – it uses the same principles to identify which row and column a cell belongs to based on its address as the code that identifies the cells on the northern and southern edges of the grid.

NOTES ABOUT THIS CODE: This code uses a tally table, which is simply a table of integers, and a function to generate random numbers within defined bounds developed by Jeff Moden to create and populate the table representing the 10×10 grid. This code also uses T-SQL syntax for declaring the temporary table since I have easiest access to a Microsoft SQL Server instance for testing the code; I tried to use ANSI standard SQL for all other purposes.

``` CREATE PROCEDURE dbo.GameOfLife @nRounds int ```

``` AS BEGIN --Create and populate 10x10 grid table: CREATE TABLE #Merkles (GridNbr smallint, Merkle smallint) INSERT INTO #Merkles SELECT t.N, r.randomNumber FROM DNA.dbo.tally t OUTER APPLY dbo.RandomNumberSeries(0, 1, 1) r WHERE t.N BETWEEN 1 AND 100 -- Display starting state: SELECT m.y ,SUM(CASE WHEN m.x = 0 THEN m.Merkle ELSE 0 END) AS [1] ,SUM(CASE WHEN m.x = 1 THEN m.Merkle ELSE 0 END) AS [2] ,SUM(CASE WHEN m.x = 2 THEN m.Merkle ELSE 0 END) AS [3] ,SUM(CASE WHEN m.x = 3 THEN m.Merkle ELSE 0 END) AS [4] ,SUM(CASE WHEN m.x = 4 THEN m.Merkle ELSE 0 END) AS [5] ,SUM(CASE WHEN m.x = 5 THEN m.Merkle ELSE 0 END) AS [6] ,SUM(CASE WHEN m.x = 6 THEN m.Merkle ELSE 0 END) AS [7] ,SUM(CASE WHEN m.x = 7 THEN m.Merkle ELSE 0 END) AS [8] ,SUM(CASE WHEN m.x = 8 THEN m.Merkle ELSE 0 END) AS [9] ,SUM(CASE WHEN m.x = 9 THEN m.Merkle ELSE 0 END) AS [10] FROM (SELECT *, ((GridNbr - 1) % 10) + 1 as y, (GridNbr - 1) / 10 AS x FROM #Merkles) m GROUP BY m.y ORDER BY m.y DESC --Loop through @nRounds: DECLARE @Counter smallint = 1 WHILE @Counter <= @nRounds BEGIN UPDATE z SET z.Merkle = CASE WHEN z.Merkle = 1 AND (zx.nNeighbors 3) THEN 0 WHEN z.Merkle = 0 AND zx.nNeighbors = 3 THEN 1 ELSE z.Merkle END FROM #Merkles z LEFT OUTER JOIN ( SELECT a.GridNbr, a.Merkle, ((a.GridNbr - 1) % 10) + 1 as y, ((a.GridNbr - 1) / 10) + 1 AS x, SUM(a.AdjoiningMerkle) AS nNeighbors FROM ( SELECT m.*, mx.GridNbr AS AdjoiningGridNbr, mx.Merkle AS AdjoiningMerkle FROM #Merkles m LEFT OUTER JOIN #Merkles mx ON mx.GridNbr IN (CASE WHEN m.GridNbr % 10 > 0 THEN m.GridNbr + 1 ELSE NULL END -- N ,CASE WHEN m.GridNbr % 10 > 0 THEN m.GridNbr + 11 ELSE NULL END -- NE ,m.GridNbr + 10 -- E ,CASE WHEN m.GridNbr % 10 1 THEN m.GridNbr + 9 ELSE NULL END -- SE ,CASE WHEN m.GridNbr % 10 1 THEN m.GridNbr - 1 ELSE NULL END -- S ,CASE WHEN m.GridNbr % 10 1 THEN m.GridNbr - 11 ELSE NULL END -- SW ,m.GridNbr - 10 -- W ,CASE WHEN m.GridNbr % 10 > 0 THEN m.GridNbr - 9 ELSE NULL END -- NW ) ) a GROUP BY a.GridNbr, a.Merkle, ((a.GridNbr - 1) % 10) + 1, ((a.GridNbr - 1) / 10 ) + 1 ) zx ON z.GridNbr = zx.GridNbr -- Display resulting state: SELECT m.y ,SUM(CASE WHEN m.x = 0 THEN m.Merkle ELSE 0 END) AS [1] ,SUM(CASE WHEN m.x = 1 THEN m.Merkle ELSE 0 END) AS [2] ,SUM(CASE WHEN m.x = 2 THEN m.Merkle ELSE 0 END) AS [3] ,SUM(CASE WHEN m.x = 3 THEN m.Merkle ELSE 0 END) AS [4] ,SUM(CASE WHEN m.x = 4 THEN m.Merkle ELSE 0 END) AS [5] ,SUM(CASE WHEN m.x = 5 THEN m.Merkle ELSE 0 END) AS [6] ,SUM(CASE WHEN m.x = 6 THEN m.Merkle ELSE 0 END) AS [7] ,SUM(CASE WHEN m.x = 7 THEN m.Merkle ELSE 0 END) AS [8] ,SUM(CASE WHEN m.x = 8 THEN m.Merkle ELSE 0 END) AS [9] ,SUM(CASE WHEN m.x = 9 THEN m.Merkle ELSE 0 END) AS [10] FROM (SELECT *, ((GridNbr - 1) % 10) + 1 as y, (GridNbr - 1) / 10 AS x FROM #Merkles) m GROUP BY m.y ORDER BY m.y DESC SET @Counter = @Counter + 1 END DROP TABLE #Merkles END ```