Here are some simple ideas. Take a board, fill it from it's empty position with an equal number of red and white stones equally distributed. That's easy to do by the way. If you are proficient in the use of the standard library, you will notice in the standard library that there is a pre-existing routine called the shuffle routine. And if you shuffle all the nodes and you have a data structure that's keeping track of the nodes of the hex board. And you shuffle them, and you fill the first half of them with white stones and the second half with black stones. Then you've accomplished your random placement on the board of the white and black stones. So let me suggest that that is the method you use. You don't have to use that method. You could use the method where okay, I'm going somewhere at random in the remaining empty squares that in placing a white and then placing a black and taking alternate turns and placing white to black stones. But then you're going to have to keep track of all the coordinates of what remains empty. And could do that readily but as they say might as well take advantage. One of the things you're benefiting from this class and we hope is a much better understanding and insight into the standard library and it has relevant routines that let you do this efficiently. So, The position is going to be one after you fill out the whole board. I've already mentioned that, that's an optimization, that's an important optimization. And then the test thing, the Dykstra's algorithm only needs to occur once. So rather than have to test 120 times on the 11 by 11 board, you pass once at the end. Even though you have to make more moves but making moves is cheap, really cheap. So this is a big computational way, it's a breakthrough computational way and it's not obvious. How do we specialize Dijkstra? We've already gone at length into the Dijkstra algorithm. And the Dijkstra algorithm is a critical path finding algorithm underpinning lots of stuff in computer science and it's a canonical greeting algorithm. So understanding it, understanding algorithms like it, that's a takeaway. I hope that's a real value though hopefully you came into the class knowing that background already. So winning amounts to seeing whether one player, you can just assume on this full-up board. If North/South hasn't won, let's call him player 1, then it had to be East/West that won. That's from the nature of Hex. So all we need to do is examine whether there is a complete path from the North boundary to the South boundary. So here's a basic hex graph that I suggest you try to use. Not required so if you write something that's as good or better or your own, fine and dandy, I'm not unhappy with that. But for those of you who need a little more guidance, this may be of value. So this is code that I generated to do the problem. And again, I have a general graph but I'm going to have a constructor. I'm not going to worry about other constructors for the graph. I'm going to have a constructor that's given the hex size of the graph. And that hex size is one dimension. So it's 11 when you have an 11 by 11 graph. Now don't forget when you have an 11 by 11 hex board, or a 5 by 5 hex board. Let's take the 5 by 5 case. You have 25 nodes, so the graph is really the hex size squared, the graph size. The number of nodes, the number of actual squares, is the side because it's basically this hexagonal square, square. And the other part of our interface is not only the constructor for the hex board, but who won. This is our specialized path algorithm. And then internally again, you can do this in other ways. I chose to use a vector or vectors and then that will be how I store my graph and the graph will be for each node there will be a vector of edges. So here's the zeroth node, and here's our vector of edges, all the edges out of that zero node, 3, 7, 9, whatever. 24, however we're, in our board size. This is the actual board size. So it's going in effect when initialized from this constructor, be A size squared. And then we're going to have a simple representation of, in each, square related to the graph node, each square can be either 0 meaning empty, 1 meaning a white stone, 2 meaning a black stone, or whatever colors you like. So we have those three states and indeed one suggestion is to turn this into an enumerator. So if I wasn't lazy in my own code I would have probably made this its own class and then had three values empty white black. To implement the who_won algorithm, we can either use a specialized form of Dykstra, that looks for a path between north and south or east and west. Or we can use classically the union find algorithm. Either one is appropriate, either one is okay for this project.
