As per [Luke's request](http://codegolf.stackexchange.com/questions/68678/tic-tac-toe-with-only-crosses#comment168138_68678) and [Peter Taylor's addition](http://codegolf.stackexchange.com/a/69097/34388) to this challenge.
###Introduction
Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only going to use **crosses**. The first person who places three crosses in a row loses. An interesting fact is that the maximum amount of crosses before someone loses, is equal to **6**:
X X -
X - X
- X X
That means that for a 3 x 3 board, the maximum amount is **6**. So for N = 3, we need to output 6.
Another example, for N = 4, or a 4 x 4 board:
X X - X
X X - X
- - - -
X X - X
This is an optimal solution, you can see that the maximum amount of crosses is equal to **9**. An optimal solution for a 12 x 12 board is:
X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X
This results in **74**.
###The task
Your task is to compute the results as fast as possible. I will run your code on the test case `13`. This will be done 5 times and then the average is taken of the run times. That is your final score. The lower, the better.
###Test cases
N Output
1 1
2 4
3 6
4 9
5 16
6 20
7 26
8 36
9 42
10 52
11 64
12 74
13 86
14 100
15 114
More information can be found at https://oeis.org/A181018.
###Rules
- This is [tag:fastest-code], so the fastest submission wins!
- You must provide a *full program*.
- Please also provide how I have to run the program. I am not familiar with all programming languages and how they work, so I need a little bit of help here.
- Of course, your code needs to compute the *correct* result for each test case.
###Submissions:
- **Peter Taylor** (Java): 14m 31s