Novice Attempt at Tic Tac Toe using Graph Theory
I've always been fascinated by graph theory. Last year, I bought a beginner book (Introduction to Graph Theory) on it, and consumed it quickly. Since then, I've been reading articles and watching videos online to sate my curiosity.
In the beginning of the course at NSS, we have several challenges that we provide to students to let them explore their own knowledge and curiosity about JavaScript, CSS, and HTML. One of the exercises has the students implement a Tic Tac Toe game.
I've never done it myself. However, as my mind was wandering the other day, I realized that I could implement what I've learn about graphs with a solution for this challenge.
I just finished up a simple, brute force implementation yesterday that will require many refactors before I feel like I've done it somewhat efficiently.
I'll post to link to my code on Github below, but I'm going to show the code I started with to describe the nodes and edges on my graph. Hell, this may not even be even remotely correct, but it's how my beginner's brain looked at it.
I made an entry in a Map for each of the nodes (the squares of the game). The key is the node number and the value is another map of the neighboring nodes, and the weight of the edge. The weight is simply the angle to get to the neighboring node.
const adjacencyGraph = new Map()
adjacencyGraph.set(1, new Map([[2,0], [4,270], [5,315], [7,90], [9,135], [3,180]]))
adjacencyGraph.set(2, new Map([[3,0], [5,270], [8,90], [1,180]]))
adjacencyGraph.set(3, new Map([[5,225], [6,270], [9,90], [7,45], [1,0], [2,180]]))
adjacencyGraph.set(4, new Map([[5,0], [7,270], [1,90], [6,180]]))
adjacencyGraph.set(5, new Map([[6,0], [7,225], [8,90], [9,315], [1,135], [2,90], [3,45], [4,180]]))
adjacencyGraph.set(6, new Map([[4,0], [9,270], [3,90], [5,180]]))
adjacencyGraph.set(7, new Map([[8,0], [9,180], [1,270], [4,90], [3,225], [5,45]]))
adjacencyGraph.set(8, new Map([[9,0], [7,180], [5,90], [2,270]]))
adjacencyGraph.set(9, new Map([[1,315], [8,180], [5,135], [6,90], [3,270], [7,0]]))
When I finally got that data structure the way I wanted. It allowed me to implement a basic solution.
It was fun to explore a different way of solving this problem, even if the code is inefficient (for now).