Not for humans, really. Just shade in the territories and do some math. For a computer, scoring is hard. At least it is for the computer I’m working with ;-).
I’m now at the point where my code can reliably detect territories and identify all the posts within them. An example is shown to the right. If I were doing post scoring, I’d be done.
Now I have to take what I have and translate it into visibly shading those territories, and reporting the (area-based) score. Shouldn’t be too hard, should it? (famous last words)
Here’s the algorithm I’m using (roughly):
- Create an array C of the colored posts.
- Strip from C all posts that are attached to only one other post.
- Repeat 2 until the list stops changing. This leaves only loops (potential territories). Note that the edges of the board count as one connection, so a lone post there will go away, but a post connected to any other post won’t.
- Create an array N of all the intersections, identifying their eight neighbors orthogonally and diagonally.
- Iterate through all the fences and remove from N the neighbors that the fences cut off. So 1,1 and 2,2 start off as a neighbors, but the fence from 2,1 to 1,3 separates them.
- For each post in C, split the entry in N and create one separate entry for each set of neighbors separated by the fences attached to the post. So for example, the red post at 2,1 in the diagram above would have two sets of neighbors: 1,1 and 2,2; 3,1. The red post at 9,7 would have three sets of neighbors: 8,8 and 9,8; 10,8; 10,7 and 10,6; 9,6; 8,6; 8,7. At the same time, split the entry in C as well, giving each new entry the same color as the original.
- Now go through C and color each post’s neighbors:
- If the neighbor is empty, give it C’s color.
- If C is gray (no one’s territory) then color the neighbor gray.
- If the neighbor is gray, color C gray.
- If C and the neighbor are different colors (not gray) then make both gray.
- Repeat 7 until the board stops changing.
I had originally thought to identify loops and then figure out which loops were in other loops, invalidating them. That was tough. I did manage to re-use some of the code for identifying loops in step 2 above. Before I added that step, a lone red post inside a blue territory would invalidate the blue territory.
When I started on this algorithm I only used the four orthogonal neighbors, which failed with territories like the large blue one above — the empty space within it that isn’t blue territory can’t be reached from the outside using only orthogonal connections.
My first attempts at this algorithm didn’t include step 6, and therefore tried to make posts unchangeable while leaving the intersections around them free to be updated. That didn’t work because of trying to identify the appropriate neighbors to change.
In all I’d say this is one of the hardest algorithms to get right that I’ve coded. I’m thinking about submitting it to Project Euler to see if they’d be interested in putting it up.