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
The task is simple, given an integer greater than 0, output the maximum amount of crosses that can be placed with no three X's adjacent in a line along a row, column or diagonally.
Test cases
N Output
1 1
2 4
3 6
4 9
5 16
6 20
7 26
8 36
9 42
More information can be found at https://oeis.org/A181018.
Rules
- This is code-golf, so the submission with the least amount of bytes wins!
- You may provide a function or a program.