32

4

### 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.

7So the question just boils down to using the formulas in the page you linked... – nicael – 2016-01-06T18:51:46.727

2Related post over on Math. – AdmBorkBork – 2016-01-06T18:52:09.407

7@nicael As far as I can see, the OEIS article only contains lower bounds. – Martin Ender – 2016-01-06T18:57:11.260

@PeterTaylor I do know that

`100`

is correct for`14`

. I don't know the result for`13`

though. – Adnan – 2016-01-07T16:12:43.877The challenge would be a lot more interesting in my opinion if it could be a rectangular board with an input for height and width, but it's probably too late for that. – DanTheMan – 2016-01-07T18:08:57.900

@PeterTaylor Well, after some research, it can be seen that if the size of the board can be expressed in the form 3k-1, the maximum amount of crosses would be ((N+1)/3)^2 * 4, with N being the size of the board. This can also be seen at N = 2, 5, 8, 11. These can be seen in the sequence: 1,

4, 6, 9,16, 20, 26,36, 42, 52,64, 74, which are 2^2, 4^2, 6^2, 8^2, and so on. – Adnan – 2016-01-07T23:54:22.487The reason behind this is that the grid can be perfectly filled in with 2 x 2 squares of crosses, or a zigzag pattern, which fills half the board with crosses. Here is my solution for N = 14 (but not entirely proven).

– Adnan – 2016-01-07T23:58:36.417Do you realise that your previous two comments contradict each other, because the zigzag pattern gives a counterexample to the 4/9(N+1)^2 at N=17? – Peter Taylor – 2016-01-08T09:10:28.933

@PeterTaylor I can't remember why I included the zigzag example, but it is wrong. That gives 98 for N=14. The reason behind is that the grid can be filled in with 2 x 2 squares, not the zigzag pattern. – Adnan – 2016-01-08T09:27:37.287

I'm not sure how effective it may be, but an optimal game on a 3x3 board is played by playing a night's move away from your opponent's move – Conor O'Brien – 2016-01-08T16:42:53.117

@CᴏɴᴏʀO'Bʀɪᴇɴ Yes, that also seems to be the case at the 12 x 12 board. With a knight starting at the top-left corner and ending at the bottom-right. – Adnan – 2016-01-09T08:56:31.510

@Adnan Interesting... I wonder if there is any pattern in the boards that satisfy this problem? – Conor O'Brien – 2016-01-09T17:44:21.450

Has anyone proven a result for input

`15`

? – KSFT – 2016-01-10T16:18:59.507@KSFT Not that I know of – Adnan – 2016-01-10T16:19:30.280

6Would be cool to see this as a fastest code challenge. – Luke – 2016-01-10T19:04:42.613

Do we need to be able to prove answers correct? – KSFT – 2016-01-10T22:01:25.943

And yes, you need to be able to prove your answer correct. – Peter Taylor – 2016-01-10T22:22:52.367

@PeterTaylor would the only way to prove that an answer is correct is to wait till the bruteforce programs finish? – JuanPotato – 2016-01-10T23:27:13.207

1@JuanPotato, exactly the opposite. No brute force program is ever going to prove that any other program is correct (although one might prove another answer

incorrect). The only way to prove that an answer is correct is by demonstrating that it takes into account every configuration which can't be proven suboptimal. – Peter Taylor – 2016-01-11T00:08:28.363@Luke Yeah, I realised that a while after I've posted the challenge, but the problem is that if there exists a formula for this, it would make no sense anymore. – Adnan – 2016-01-11T07:36:22.143

4

Not a codegolf solution, but I have been playing with a "visual" solver the past few days. You can access the jsfiddle here: http://jsfiddle.net/V92Gn/3899/ It attempts to find solutions via random mutations. It won't stop if it finds the "correct" answer, but it can get to many of the correct solutions much quicker than those answers below.

– styletron – 2016-01-12T14:31:09.833@styletron That actually looks pretty amazing. This will probably simplify pattern recognition for certain grids. Thanks :) – Adnan – 2016-01-12T14:52:45.767

Is an answer considered valid only if it passes all test cases up to 9 in a reasonable time? – Sleafar – 2016-01-12T18:29:34.200

1@Sleafar It is considered valid if your program calculates the correct value for any N in '

unlimited' time. Sotheoretically, it should solve all N. – Adnan – 2016-01-12T18:49:00.800@Adnan disagree. And

unlimitedmemory too?. My answer use a memory area of 999+999+99 integers. I can use some more chars and have 100000+100000+1000 integers, but what for? It will never use all this memory during our lifetime – edc65 – 2016-01-12T20:04:25.0331@edc65 Yes, that is what I meant with theoretically solving the problem. Although in practice, we probably won't even reach the answer, if you have unlimited memory and unlimited time, it should be able to calculate the answer. – Adnan – 2016-01-12T20:07:52.803

Thanks for the props on the fiddle I posted yesterday. Using that code for N=20, I can prove that that

– styletron – 2016-01-13T15:37:39.113`((N+1)/3)^2 * 4`

formula is broken for at least N=20 which should have a max of 196 if that formula were correct. I have at least 201 on a 20x20 grid here (png image). I noticed a pattern trying to emerge of z tetriminos, so I manually tried that out and was able to fit 200 (png image) in the 20x20 grid.Following up with my previous comment, removing 3 rows and columns from the manual job above yields 145 count for N=17 which also invalidates the formula since N=17 should have maxed out at 144. – styletron – 2016-01-13T15:57:08.340

@styletron It seems that the z-pattern is more efficient than the 2 x 2 square. I did not expect this, but this is very interesting! – Adnan – 2016-01-13T17:40:53.820

@styletron, the alternating pattern in the OEIS comments also gives 145 for N=17. – Peter Taylor – 2016-01-13T21:03:05.117

@PeterTaylor Doh! You're right. Using that pattern also yields 200 for N=20. – styletron – 2016-01-13T21:19:26.293

Still waiting for the second review of my suggested changes to OEIS A181018, but the next few terms are

`a(13) = 86, a(14) = 100, a(15) = 114, a(16) = 130`

. I speculate that`a(17) =? 146`

, but unless I find a major optimisation the calculation would take a month. – Peter Taylor – 2016-01-16T22:37:42.243