Tic-tac-toe with only crosses 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.
CJam (58 56 bytes)

2q~:Xm*{7Yb#W=}:F,Xm*{ee{~0a@*\+}%zS*F},_Wf%:z&amp;Mf*1fb:e&gt;


This is incredibly slow and uses a lot of memory, but that's code-golf for you.

Dissection

2q~:Xm*        e# Read input into X and find Cartesian product {0,1}^X
{7Yb#W=}:F,    e# Filter with a predicate F which rejects arrays with a 111
Xm*            e# Take the Cartesian product possible_rows^X to get possible grids
{              e# Filter out grids with an anti-diagonal 111 by...
  ee{~0a@*\+}% e#   prepending [0]*i to the ith row
  zS*F         e#   transposing, joining on a non-1, and applying F
},
_Wf%:z         e# Copy the filtered arrays and map a 90 degree rotation
&amp;              e# Intersect. The rotation maps horizontal to vertical and
               e# anti-diagonal to diagonal, so this gets down to valid grids
Mf*            e# Flatten each grid
1fb            e# Count its 1s
:e&gt;            e# Select the maximum


The number of valid rows is a tribonacci number and is \$\Theta(a^X)\$ where \$a\$ is the tribonacci constant, \$1.83928675\ldots\$. The number of grids generated in the Cartesian product is \$\Theta(a^{X^2})\$; the second filter will reduce the number somewhat, but the intersection is still probably \$\Theta(a^{X^4})\$.



An "efficient" approach ("merely" \$O(X a^{3X})\$) uses dynamic programming. Ungolfed in Java:

public class A181018 {
    public static void main(String[] args) {
        for (int i = 1; i &lt; 14; i++) {
            System.out.format("%d:\t%d\n", i, calc(i));
        }
    }

    private static int calc(int n) {
        if (n &lt; 0) throw new IllegalArgumentException("n");
        if (n &lt; 3) return n * n;

        // Dynamic programming approach: given two rows, we can enumerate the possible third row.
        // sc[i + rows.length * j] is the greatest score achievable with a board ending in rows[i], rows[j].
        int[] rows = buildRows(n);
        byte[] sc = new byte[rows.length * rows.length];
        for (int j = 0, k = 0; j &lt; rows.length; j++) {
            int qsc = Integer.bitCount(rows[j]);
            for (int i = 0; i &lt; rows.length; i++) sc[k++] = (byte)(qsc + Integer.bitCount(rows[i]));
        }

        int max = 0;
        for (int h = 2; h &lt; n; h++) {
            byte[] nsc = new byte[rows.length * rows.length];
            for (int i = 0; i &lt; rows.length; i++) {
                int p = rows[i];
                for (int j = 0; j &lt; rows.length; j++) {
                    int q = rows[j];
                    // The rows which follow p,q cannot intersect with a certain mask.
                    int mask = (p &amp; q) | ((p &lt;&lt; 2) &amp; (q &lt;&lt; 1)) | ((p &gt;&gt; 2) &amp; (q &gt;&gt; 1));
                    for (int k = 0; k &lt; rows.length; k++) {
                        int r = rows[k];
                        if ((r &amp; mask) != 0) continue;

                        int pqrsc = (sc[i + rows.length * j] &amp; 0xff) + Integer.bitCount(r);
                        int off = j + rows.length * k;
                        if (pqrsc &gt; nsc[off]) nsc[off] = (byte)pqrsc;
                        if (pqrsc &gt; max) max = pqrsc;
                    }
                }
            }

            sc = nsc;
        }

        return max;
    }

    private static int[] buildRows(int n) {
        // Array length is a tribonacci number.
        int c = 1;
        for (int a = 0, b = 1, i = 0; i &lt; n; i++) c = a + (a = b) + (b = c);

        int[] rows = new int[c];
        int i = 0, j = 1, val;
        while ((val = rows[i]) &lt; (1 &lt;&lt; (n - 1))) {
            if (val &gt; 0) rows[j++] = val * 2;
            if ((val &amp; 3) != 3) rows[j++] = val * 2 + 1;
            i++;
        }

        return rows;
    }
}