Tic-tac-toe with only crosses

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 , so the submission with the least amount of bytes wins!
  • You may provide a function or a program.

Adnan

Posted 2016-01-06T18:15:11.410

Reputation: 41 965

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

The 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.487

The 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.417

Do 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. So theoretically, it should solve all N. – Adnan – 2016-01-12T18:49:00.800

@Adnan disagree. And unlimited memory 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.033

1@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 ((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.

– styletron – 2016-01-13T15:37:39.113

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

Answers

11

Pyth, 57 51 49 bytes

L.T.e+*]Ykbbsef!s.AMs.:R3ssmyBdsm_BdCBcTQsD^U2^Q2

Like @PeterTaylor's CJam solution, this is brute-force, so it runs in O(n22n2) time. The online interpreter doesn't finish within a minute for n=4.

Try it here for N<4.

Try the diagonals function.

L.T.e+*]Ykbb         y(b): diagonals of b (with some trailing [])
s e                  sum of the last (with most ones) array such that
f                    filter lambda T:
 ! s .AM                none of the 3 element sublists are all ones               
   s .:R3               all 3 element sublists
   s s                  flatten
   myBd                 add the diagonals
   sm_B d               add the vertically flipped array and transpose
   CBcTQ                array shaped into Q by Q square, and its transpose
 sD ^U2 ^Q2             all binary arrays of length Q^2 sorted by sum

lirtosiast

Posted 2016-01-06T18:15:11.410

Reputation: 20 331

13

CJam (58 56 bytes)

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

This is incredibly slow and uses a lot of memory, but that's 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
&              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>            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 < 14; i++) {
            System.out.format("%d:\t%d\n", i, calc(i));
        }
    }

    private static int calc(int n) {
        if (n < 0) throw new IllegalArgumentException("n");
        if (n < 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 < rows.length; j++) {
            int qsc = Integer.bitCount(rows[j]);
            for (int i = 0; i < rows.length; i++) sc[k++] = (byte)(qsc + Integer.bitCount(rows[i]));
        }

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

                        int pqrsc = (sc[i + rows.length * j] & 0xff) + Integer.bitCount(r);
                        int off = j + rows.length * k;
                        if (pqrsc > nsc[off]) nsc[off] = (byte)pqrsc;
                        if (pqrsc > 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 < n; i++) c = a + (a = b) + (b = c);

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

        return rows;
    }
}

Peter Taylor

Posted 2016-01-06T18:15:11.410

Reputation: 41 901

What does the efficient approach run in? – lirtosiast – 2016-01-11T01:03:01.950

@ThomasKwa, oh, it's still exponential, but I think it's justified to call it efficient because it's allowed me to extend the OEIS sequence by 3 terms. – Peter Taylor – 2016-01-11T07:26:03.680

@ThomasKwa, to be precise, it's O(n a^n) where a ~= 5.518. – Peter Taylor – 2016-01-11T19:00:21.423

4

C, 460 456 410 407 362 351 318 bytes

This is a really bad answer. It's an incredibly slow brute force approach. I'm trying to golf it a bit more by combining the for loops.

#define r return
#define d(x,y)b[x]*b[x+y]*b[x+2*(y)]
n,*b;s(i){for(;i<n*(n-2);++i)if(d(i%(n-2)+i/(n-2)*n,1)+d(i,n)+(i%n<n-2&&d(i,n+1)+d(i+2,n-1)))r 1;r 0;}t(x,c,l,f){if(s(0))r 0;b[x]++;if(x==n*n-1)r c+!s(0);l=t(x+1,c+1);b[x]--;f=t(x+1,c);r l>f?l:f;}main(c,v)char**v;{n=atol(v[1]);b=calloc(n*n,4);printf("%d",t(0,0));}

Test Cases

$ ./a.out 1
1$ ./a.out 2
4$ ./a.out 3
6$ ./a.out 4
9$ ./a.out 5
16$

Ungolfed

n,*b; /* board size, board */

s(i) /* Is the board solved? */
{
    for(;i<n*(n-2);++i) /* Iterate through the board */
            if(b[i%(n-2)+i/(n-2)*n]&&b[i%(n-2)+i/(n-2)*n+1]&&b[i%(n-2)+i/(n-2)*n+2] /* Check for horizontal tic-tac-toe */
                    || b[i] && b[i+n] && b[i+2*n] /* Check for vertical tic-tac-toe */
                    || (i%n<n-2
                            && (b[i] &&b [i+n+1] && b[i+2*n+2] /* Check for diagonal tic-tac-toe */
                                    || b[i+2*n] && b[i+n+1] && b[i+2]))) /* Check for reverse diagonal tic-tac-toe */
                    return 1;
    return 0;
}

t(x,c,l,f) /* Try a move at the given index */
{
    if(s(0)) /* If board is solved, this is not a viable path */
            return 0;
    b[x]++;
    if(x==n*n-1) /* If we've reached the last square, return the count */
            return c+!s(0);

    /* Try it with the cross */
    l=t(x+1,c+1);

    /* And try it without */
    b[x]--;
    f=t(x+1,c);

    /* Return the better result of the two */
    return l>f?l:f;
}

main(c,v)
char**v;
{
    n=atol(v[1]); /* Get the board size */
    b=calloc(n*n,4); /* Allocate a board */
    printf("%d",t(0,0)); /* Print the result */
}

Edit: Declare int variables as unused parameters; remove y coordinate, just use index; move variable to parameter list rather than global, fix unnecessary parameters passed to s(); combine for loops, remove unnecessary parentheses; replace && with *, || with +; macro-ify the 3-in-a-row check

Cole Cameron

Posted 2016-01-06T18:15:11.410

Reputation: 1 013

How slow is it? – Loovjo – 2016-01-09T12:31:48.740

@Loovjo tried on my PC with some small changes to make it faster, 15ms for n=5, 12 sec for n=6 (input +1, time * 800)! – edc65 – 2016-01-09T14:26:17.843

@edc65 That was my experience. Anything greater than 5 the performance was dramatically slower. I didn't bother with trying inputs greater than 6. – Cole Cameron – 2016-01-09T14:50:25.243

I started with 7 when I posted my comment. We'll see – edc65 – 2016-01-09T14:53:33.210

You can squeeze out a few more chars with #define d(x,y)b[x]*b[x+y]*b[x+y+y]; by changing the start of s to s(i,m){for(m=n-2; and replacing all instances of n-2; and by changing b[x]++ to b[x++]++ and then replacing x==n*n-1 with x==n*n, x+1 with x, and x with x-1. – Peter Taylor – 2016-01-16T22:33:41.173

4

C 263 264 283 309

Edit A few bytes saved thx @Peter Taylor - less than I hoped. Then 2 bytes used to allocate some more memory, now I can try larger size, but it's becoming very time consuming.

Note While adding the explanation, I found out that i'm wasting bytes keeping the grid in the R array - so that you can to see the solution found ... it's not requested for this challenge!!
I removed it in the golfed version

A golfed C program that can actually find the answer for n=1..10 in reasonable time.

s,k,n,V[9999],B[9999],i,b;K(l,w,u,t,i){for(t=u&t|u*2&t*4|u/2&t/4,--l; i--;)V[i]&t||(b=B[i]+w,l?b+(n+2)/3*2*l>s&&K(l,b,V[i],u,k):b>s?s=b:0);}main(v){for(scanf("%d",&n);(v=V[i]*2)<1<<n;v%8<6?B[V[k]=v+1,k++]=b+1:0)V[k]=v,b=B[k++]=B[i++];K(n,0,0,0,k);printf("%d",s);}

My test:

7 -> 26 in 10 sec
8 -> 36 in 18 sec
9 -> 42 in 1162 sec

Less golfed and trying to explain

#include <stdio.h>

int n, // the grid size
    s, // the result
    k, // the number of valid rows 
    V[9999], // the list of valid rows (0..to k-1) as bitmasks
    B[9999], // the list of 'weight' for each valid rows (number of set bits)
    R[99],  // the grid as an array of indices pointing to bitmask in V
    b,i; // int globals set to 0, to avoid int declaration inside functions

// recursive function to fill the grid
int K(
  int l, // number of rows filled so far == index of row to add
  int w, // number of crosses so far
  int u, // bit mask of the preceding line (V[r[l-1]])
  int t, // bit mask of the preceding preceding line (V[r[l-2]])
  int i) // the loop variables, init to k at each call, will go down to 0
{
  // build a bit mask to check the next line 
  // with the limit of 3 crosses we need to check the 2 preceding rows
  t = u&t | u*2 & t*4 | u/2 & t/4; 
  for (; i--; )// loop on the k possibile values in V
  {
    R[l] = i; // store current row in R
    b = B[i] + w; // new number of crosses if this row is accepted
    if ((V[i] & t) == 0) // check if there are not 3 adjacent crosses
      // then check if the score that we can reach from this point
      // adding the missing rows can eventually be greater
      // than the current max score stored in s
      if (b + (n + 2) / 3 * 2 * (n - l - 1) > s)
        if (l > n-2) // if at last row
          s = b > s ? b : s; // update the max score
        else  // not the last row
          K(l + 1, b, V[i], u, k); // recursive call, try to add another row
  }
}

int main(int j)
{
  scanf("%d", &n);

  // find all valid rows - not having more than 2 adjacent crosses
  // put valid rows in array V
  // for each valid row found, store the cross number in array B
  // the number of valid rows will be in k
  for (; i<1 << n; V[k] = i++, k += !b) // i is global and start at 0
    for (b = B[k] = 0, j = i; j; j /= 2) 
      b = ~(j | -8) ? b : 1, B[k] += j & 1;
  K(0,0,0,0,k); // call recursive function to find the max score
  printf("%d\n", s);
}

edc65

Posted 2016-01-06T18:15:11.410

Reputation: 31 086

This is essentially the same as my Java program but depth-first rather than breadth-first. I think you should be able to save at least a dozen characters by porting my buildRows method; maybe as many as 20 if for(scanf("%d",&n);(v=2*V[i++])<1<<n;v%8<6&&V[++j]=v+1)v&&V[++j]=v; is valid. (I don't have access to a C compiler right now). – Peter Taylor – 2016-01-13T10:18:38.340

1@PeterTaylor i'll give it a look ... just the word tribonacci is scaring me – edc65 – 2016-01-13T11:03:59.277

Your hard-coded 999 means that you would want to ignore that part. Although maybe you should really make it not hard-coded, so that in principle you can tackle larger inputs than 11 or 12. – Peter Taylor – 2016-01-13T11:14:59.837

@PeterTaylor it would work great if I had a .bitCount method in C to count bits. But in that initial fase I'compuitng the bit count in B, not only the bit masks in V – edc65 – 2016-01-13T15:25:35.577

2

Ruby, 263 bytes

This is also a brute force solution and faces the same problems as the C answer by Cole Cameron, but is even slower since this is ruby and not C. But hey, it's shorter.

c=->(b){b.transpose.all?{|a|/111/!~a*''}}
m=->(b,j=0){b[j/N][j%N]=1
x,*o=b.map.with_index,0
c[b]&&c[b.transpose]&&c[x.map{|a,i|o*(N-i)+a+o*i}]&&c[x.map{|a,i|o*i+a+o*(N-i)}]?(((j+1)...N*N).map{|i|m[b.map(&:dup),i]}.max||0)+1:0}
N=$*[0].to_i
p m[N.times.map{[0]*N}]

Test cases

$ ruby A181018.rb 1
1
$ ruby A181018.rb 2
4
$ ruby A181018.rb 3
6
$ ruby A181018.rb 4
9
$ ruby A181018.rb 5
16

Ungolfed

def check_columns(board)
  board.transpose.all? do |column|
    !column.join('').match(/111/)
  end
end

def check_if_unsolved(board)
  check_columns(board) && # check columns
    check_columns(board.transpose) && # check rows
    check_columns(board.map.with_index.map { |row, i| [0] * (N - i) + row + [0] * i }) && # check decending diagonals
    check_columns(board.map.with_index.map { |row, i| [0] * i + row + [0] * (N - i) }) # check ascending diagonals
end

def maximum_crosses_to_place(board, index=0)
  board[index / N][index % N] = 1 # set cross at index
  if check_if_unsolved(board)
    crosses = ((index + 1)...(N*N)).map do |i|
      maximum_crosses_to_place(board.map(&:dup), i)
    end
    maximum_crosses = crosses.max || 0
    maximum_crosses + 1
  else
    0
  end
end

N = ARGV[0].to_i
matrix_of_zeros = N.times.map{ [0]*N }

puts maximum_crosses_to_place(matrix_of_zeros)

Siim Liiser

Posted 2016-01-06T18:15:11.410

Reputation: 121

1

Haskell, 143 bytes

In some ways this is not done, but I had fun so here goes:

  • Because checking for the horizontal "winning" pattern returns invalid if applied across different rows, input of N<3 returns 0
  • The "arrays" are integers unpacked into bits, so easily enumerable
  • ((i ! x) y) gives the ith bit of x times y, where negative indices return 0 so the range can be constant (no bounds checking) and fewer parentheses when chained
  • Because the bounds are not checked, it checks 81*4=324 patterns for every possible maximum, leading to N=3 taking my laptop 9 seconds and N=5 taking too long for me to let it finish
  • Boolean logic on 1/0 is used for T/F to save space, for example (*) is &&, (1-x) is (not x), etc.
  • Because it checks integers instead of arrays, (div p1 L)==(div p2 L) is needed to make sure a pattern isn't checked across different rows, where L is the row length and p1, p2 are positions
  • The value of a possible maximum is its Hamming Weight

Here's the code:

r=[0..81]
(%)=div
s=sum
i!x|i<0=(*0)|0<1=(*mod(x%(2^i))2)
f l=maximum[s[i!x$1-s[s[1#2,l#(l+l),(l+1)#(l+l+2),(1-l)#(2-l-l)]|p<-r,let  a#b=p!x$(p+a)!x$(p+b)!x$s[1|p%l==(p+mod b l)%l]]|i<-r]|x<-[0..2^l^2]]

Michael Klein

Posted 2016-01-06T18:15:11.410

Reputation: 2 111