## Synopsis

My name is Kirk. I like making small games with code. And today's game is Tic-Tac-Toe. Specifically, this is a post about an alternative algorithm for finding winning combos in Tic-Tac-Toe using a concept called *Magic Squares*, but also about burnout, productivity, and finding joy in code. The code is all done in React and Typescript, and as always, full links and examples will be provided. If you just want to see the final solution, visit the sandbox here.

## 1. Starting from the end with sensible solutions.

Now, normally we'd start a post like this at the beginning; we'd talk about the domain of the physical game, and what elements we'd need in our digital solution. But today we're gonna start at the end; we're gonna take an existing solution and look at what if we just changed a small bit in an interesting way. Like Marvel's What-If, but with a smaller animation budget.

So what do we have going on?

My take on Tic-Tac-Toe. Does it work? Yes. A bit plain? Also yes.

This is our basic Tic-Tac-Toe implementation in React. Each turn a user clicks a cell in the grid, and the game checks to see if they've won.

Under the hood, our "grid" is just an object whose fields are the numbers of the cells and who's values are "X"s, "O"s, and `null`

s (for empty cells).

```
type Grid = { [key: number]: "X" | "O" | null };
const grid:Grid = {
1: "X",
2: null,
3: null,
4: "X",
5: "O",
6: "O",
7: null,
8: "X",
9: null
}
// this grid would be rendered as the following
x | |
x | o | o
| x |
```

For our Tic-Tac-Toe implementation, we need a function that checks whether a player has won after each turn, `hasWinner()`

. That function can accept a grid and determine if there's a winning set of moves in the grid.

The win function looks like this:

```
const winningCombos = [
[1,2,3], // top row
[4,5,6], // middle row
[7,8,9], // bottom row
[1,4,7], // left column
[2,5,8], // middle column
[3,6,9], // right column
[1,5,9], // descending diagonal
[3,5,7] // ascending diagonal
]
const hasWinner = (grid: Grid): boolean => {
// map the grid values to the combo keys
const comboValues = winningCombos.map(
(comboKeys) => comboKeys.map(
(key) => grid[key]
)
)
// find returns a value or undefined
const maybeWinner = comboValues
.find(
(comboValues) =>
comboValues.every((v) => v === "X") ||
comboValues.every((v) => v === "O")
);
// convert this value to a boolean
return !!maybeWinner
}
```

So what's happening here?

First, we create a list of lists representing all the potential winning sequences of cells, all the rows and columns and the two diagonals.

In the `hasWinner()`

function:

- We use
`map()`

over our combos to get the grid values for every cell - Then we use
`find()`

to look for a group which has all X's or all O's - If we find one, that means there's three of the same value in a row on the board, and we have a winner.

And this **works** and performs fine. It does the job. But maybe we can do something a bit more fun that does the job. Not with how `hasWinner()`

works, but with how we get those `winningCombos`

.

Here, we basically just wrote them out by hand. And eight wasn't really so bad.

**But what if we had a 4x4 board?** That's 10 solutions. And a 5x5 board is twelve. It would be *nice* if there was a way to just *know* the ways to solve without having to look at the grid and then write them all out.

And luckily, there just so happens to be a way (or this would be the end of this blog post).

And that solution, involves **magic squares**

## 2. Answers with no questions.

Now, this is meant to be a technical article, but it's worth taking a bit of time to talk about *why* this is an article about Tic-Tac-Toe, and why this solution even exists.

I tend to think that **Human being like patterns.** We're designed to find patterns and solve problems. Sometimes, our brains pattern matching inclinations can get us in trouble; conspiracies are essentially just us finding patterns even when they aren't there. Some patterns we've been picking apart and working on for thousands of years.

One such pattern discovered at least as early as 190 BCE by Chinese mathematicians is the concept of a *Magic Square*.

Tada? Yes it's just a box.

*"But Kirk," you ask, "what's so special about this square?"*

Well you see, all magic squares (including this one) have **three (3)** very interesting properties.

- All the digits in the
**rows**of the square add to a particular number. - All the digits in the
**columns**of the square must add to that same number. -
*And*all the digits in the**diagonals**add to that number too!

Do these rules feel familiar?

**Magic Squares care about the same patterns in grids made from squares that Tic-Tac-Toe does!**

And the best part is, they have nothing to do with each other! When Tic-Tac-Toe started showing up in Ancient Egypt, it didn't have anything to do with Magic Squares. Humans have just been enjoying patterns of squares in squares forever.

**Magic Squares** fall into the realm of Recreational Mathematics, which is maths done at least partially for the purposes of entertainment, as opposed to research of practical application. It's also the maths most frequently done by amateur (unpaid mathematicians). Throughout history though, Mathematicians, Philosophers, and even Religious figures have studied and teased apart the nature of magic squares. Beyond 3x3 grids, they've looked at 4x4 and larger magic squares. They've looked at semi-magic squares and pseudo magic squares, and even some things given the brilliant name of *Most-Perfect Magic Squares*.

Throughout history the patterns of magic squares have been claimed to have use in astronomical calculations, and even occult powers. There's quite a large body of examples, computations, and algorithms based on them. We've taken them apart and put them together over and over in the pursuit of understanding what do these patterns of numbers mean? And that's been terribly fun for everyone involved, but for the most part, generally, they have absolutely **no purpose at all**.

They're just numbers in squares, with no more meaning than what we give them. Just some silly nonsense that we like to look at. Answers with no questions.

Except for today. Today they're helping us solve Tic-Tac-Toe.

## 3. Making winning magic combos

So now we know there are *magic squares*, which care about the same arbitrary patterns that Tic Tac Toe cares about. How does that help us get to a solution.

Well, let's look at the magic square for a 3x3 grid.

While magic squares get more complex in 4x4 grids and higher, with 3x3 grids we can confidently say a few things:

- All the rows, columns, and diagonals in a 3x3 magic square add to fifteen (15)
- As importantly, any other 3 number combo in a 3x3 magic square Does Not add up to 15.
- There's only
*one (1)*way to align the numbers in a 3x3 grid to get a magic square (You can rotate the numbers around the center or flip them on an axis but it's still the same arrangement).

This means if we can *programatically* get all the 3 digits combos that sum to 15, we can get all the relevant rows, columns, and diagonals in Tic-Tac-Toe.

The implementation of this ends up being far shorter that the lead up.

```
import { Combination } from "js-combinations"
const keys = [1, 2, 3, 4, 5, 6, 7, 8, 9]
const uniqueTriples = new Combination(keys, 3).toArray()
// [[1, 2, 3], [1, 2, 4], [1, 2, 5] ...
const winningCombos = uniqueTriples.filter(
(nums) => nums.reduce((acc, num) => acc + num) === 15
);
// [[1, 5, 9], [1, 6, 8], [2, 4, 9], [2, 5, 8]...
```

This is only a few lines of code but there's a lot going on here so let's break it down step by step.

The first thing we do is import the `Combination`

class from the js-combinatorics package. This package has a ton of useful tools for calculating permutations and combinations of items.

We're using to the Combination class to create all the valid, *unique* combinations of 3 numbers from the set of numbers from 1 to 9.

The `Combination`

class from this library is a Javascript Iterable.

Each value is the same shape as the ones we saw in one original winning combos; **an array of three (3) numbers.**

We convert our combination class to an array so we can do the next step; filtering those unique pairs down to just the values that add to 15. Thanks to magic squares we *know* those values will be the rows, columns, and diagonals of our solution.

To the filter method, we pass a callback inline that uses `reduce()`

to sum all the values in our triple and see if they add to 15.

And our `hasWinner()`

function is none the wiser.

The final part is the **arrangement of our cells in the UI**. The only way this method works is if on the UI side, our cells are displayed in the right order. There are a few ways to accomplish this but the simplest is just to order our keys in the magic square arrangement so whatever calls the API gets them out in the order they're meant to be displayed.

```
const keys = [2, 7, 8, 9, 5, 1, 4, 3, 6]
```

And that's all it takes. No more manually writing out winning combos. And we can scale this for 4x4, 5x5, 6x6 etc...

## 4. So What's the Takeaway

Honestly, I started this project planning to talk about object-oriented vs functional API design. And I might still do that. I had written the first version of this solution, and it worked really well, and that was going to be it.

But then, at **2:00 a.m. in the morning** when I should've been asleep, I was instead thinking about how tic-tac-toes remind me of tiny sudoku tables. And I remembered doing a cool sudoku once that had a *Magic Square*.

**I have always felt like coding is a creative endeavour.** I remember being told once, that *"creativity is just novel juxtapositions"*. I could've done this the regular way, but this way, with this weird fact about magic squares, it just seemed a little more fun.

It just felt like something to explore. I am far from the first person to make a Tic-Tac-Toe game. And I'm definitely not the first person to think of Magic Squares.

**But maybe I'm the first one to put them together like this.** With React. With Typescript. And that was *fun for me*.

So I hope this post and this code can provide you some measure of joy and insight. And even if you don't care about the squares stuff, I don't think it's a half bad implementation of Tic-Tac-Toe. It's got all the function composition and expression based logic I also enjoy. And I hope it inspires you to do things you enjoy as well. Not everything we do needs to have a direct purpose.

**You can just do things, and write code, because it makes you happy.** In between all the *React fundamentals, and AWS fundamentals, and Docker fundamentals*, and practicality and hireability, we should sneak in some time just for us.

And like me and the folks who first thought about Magic squares, maybe 2000 years from now, someone will find the things you did just for fun, and use them to have fun too.

Let me know if you have any questions about the code, the squares, or the strategy, or if there's anything else you'd like me to cover.

**Thank you for your time.**

*Special thank you to all my friends at Virtual Coffee for encouraging me to do this (and debugging my css!)

## Resources

- See here for the Github repo for this code.
- See here for the editable, runnnable codesandbox where I made this.
- The wikipedia article about magic squares has a lot more cool info about their history and properties.

And finally, here's the main code for the solution if you'd just like to see what's going on here.

App.tsx

```
import "./styles.css";
import Game from "./GameClass";
import { useState } from "react";
const initialGame = () => ({ game: new Game() });
export default function App() {
const [state, setState] = useState(initialGame());
// this is where we update the state of our application
const update = (value: number | "Restart") => {
if (value !== "Restart") {
state.game.setCell(value);
setState({ ...state });
} else setState(initialGame());
};
// our tiny little cell component
const Cell = (key: number) => (
<button key={key} id={`cell${key}`} onClick={() => update(key)}>
{state.game.getCell(key) ?? ""}
</button>
);
// I really dislike curly braces
const statusMessage = () => {
if (state.game.winner) return `${state.game.winner} won the game!`;
else if (state.game.isFull) return "The game is a draw!";
else return `${state.game.turn}'s turn to play!`;
};
// Putting it all together
return (
<div className="App">
<h1>ReacTacToe</h1>
<div id="gamebox">{state.game.cellNames.map(Cell)}</div>
<div id="status">{statusMessage()}</div>
<button onClick={() => update("Restart")}>Restart</button>
</div>
);
}
```

GameClass.ts

```
import { Combination } from "js-combinatorics";
type Grid = { [key: number]: "X" | "O" | null };
const keys = [2, 7, 6, 9, 5, 1, 4, 3, 8];
// get every unique combination of 3 numbers and only keep the ones that sum to 15
const winningCombos = new Combination(keys, 3).toArray().filter(
(nums) => nums.reduce((acc, num) => acc + num) === 15
);
const hasWinner = (grid: Grid) =>
!!winningCombos
// get the corresponding grid items
.map((comboNumbers) => comboNumbers.map((key) => grid[key]))
// if you find at least one with all Xs or all Os, there's a winner!
.find(
(comboValues) =>
comboValues.every((v) => v === "X") ||
comboValues.every((v) => v === "O")
);
export default class Game {
private _grid: Grid;
constructor() {
// using reduce to add all our keys to an object with initial values of null;
this._grid = keys.reduce(
(grid, key) => Object.assign(grid, { [key]: null }),
{}
);
}
get turn() {
// get the grid values
const counts = Object.values(this._grid)
// use reduce to make an object that counts all the Xs and Os
.reduce(
(acc, value) => {
if (value === "X") acc.Xs += 1;
else if (value === "O") acc.Os += 1;
return acc;
},
{ Xs: 0, Os: 0 }
);
// if there are more Xs on the board, it's O's turn.
return counts.Xs > counts.Os ? "O" : "X";
}
get winner() {
if (!hasWinner(this._grid)) return null;
// if there's a winner and it's X's turn, that means O just won. Otherwise, X just won.
else return this.turn === "X" ? "O" : "X";
}
get isFull() {
// no null values in the grid? board must be full
return Object.entries(this._grid).every(([_, value]) => !!value);
}
getCell = (key: number) => (key in this._grid ? this._grid[key] : null);
setCell = (key: number) => {
// no winner yet, a valid name and an empty cell? Set grid cell to whoever's turn this is.
if (!this.winner && key in this._grid && !this._grid[key])
this._grid[key] = this.turn;
};
get cellNames() {
return keys;
}
}
```

Styles.scss

```
.App {
display: flex;
flex-direction: column;
align-items: center;
justify-content: space-around;
}
#gamebox {
display: grid;
width: 80vw;
height: 80vw;
max-width: 600px;
max-height: 600px;
min-width: 150px;
min-height: 150px;
grid-template-areas:
". . ."
". . ."
". . .";
}
#status {
margin: 5px;
}
```

## Discussion (8)

I look forward to your Connect 4 game post. 😎

Connect four is actually a very interesting game from a dev perspective, since simple solvers would take... a long time to get to the right solution. So that could be really fun.

It'd be fun to pair on if you're up for it. 😎

Always down to pair with you, friend. We could even do it in Rust if you'd like :)

Everything looks great, one thing that I think you don't need to do is spread the array for filtering. Filter doesn't mutate the array, so it's a bit of a waste of memory.

Hey Rodrigo, do you mean the spread of the

`Combination`

object? IIRC, I spread into an array because the filter method isn't available on the combination directly.But maybe there's a more efficient way to do that?

You are right, this object doesn't generate a pure array.

it has the toArray function, but it does the same you did there.

I should have checked this before commenting

No worries. I didn't even check to see if it implemented

`toArray()`

. That's probably the clearer way to express that intent. I'll use that instead. Thanks!