Check whether Bob can force a zero pattern against Alice in a game of determinants; see

Question216503.java

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

public class Question216503 {
    final static int n = 5;
    final static int [] weights = {0,1,n+1};

    static class State {
        int ntypes [] = {n*n,0,0};

        byte [] [] matrix = new byte [n] [n];
        int [] [] order = new int [2] [n];
        int [] [] sums = new int [2] [n];

        {
            for (int i = 0;i < n;i++)
                order [0] [i] = order [1] [i] = i;
        }

        public boolean isValid () {
            int diff = ntypes [1] - ntypes [2];
            return diff == 1 || diff == 0;
        }

        public long toCode () {
            long code = 0;
            for (int i = 0;i < n;i++)
                for (int j = 0;j < n;j++) {
                    code <<= 2;
                    code += matrix [order [0] [i]] [order [1] [j]];
                }
            return code;
        }

        public long toCode (int [] rows,int [] cols) {
            long code = 0;
            for (int i = 0;i < n;i++)
                for (int j = 0;j < n;j++) {
                    code <<= 2;
                    code += matrix [order [0] [rows [i]]] [order [1] [cols [j]]];
                }
            return code;
        }

        public void fromCode (long code) {
            for (int i = 0,shift = 2 * (n * n - 1);i < n;i++)
                for (int j = 0;j < n;j++,shift -= 2)
                    set (i,j,(int) ((code >> shift) & 3));
        }

        public byte get (int i,int j) {
            return matrix [i] [j];
        }

        public void set (int i,int j,int value) {
            ntypes [matrix [i] [j]]--;
            ntypes [value]++;

            int change = weights [value] - weights [matrix [i] [j]];
            matrix [i] [j] = (byte) value;
            sums [0] [i] += change;
            sums [1] [j] += change;

            if (reordering)
                fix (i,j);
        }

        private int rank (int i,int dir) {
            for (int j = 0;j < n;j++)
                if (order [dir] [j] == i)
                    return j;
            throw new Error ();
        }

        private int [] r = new int [2];

        final static boolean testing = false;
        final static boolean reordering = true;

        private void fix (int i,int j) {
            r [0] = rank (i,0);
            r [1] = rank (j,1);

            for (int k = 0;k < 2;k++) {
                while (r [k] != 0 && sums [k] [order [k] [r [k]]] > sums [k] [order [k] [r [k] - 1]]) {
                    int tmp = order [k] [r [k]];
                    order [k] [r [k]] = order [k] [r [k] - 1];
                    order [k] [r [k] - 1] = tmp;
                    r [k]--;
                }

                while (r [k] != n - 1 && sums [k] [order [k] [r [k]]] < sums [k] [order [k] [r [k] + 1]]) {
                    int tmp = order [k] [r [k]];
                    order [k] [r [k]] = order [k] [r [k] + 1];
                    order [k] [r [k] + 1] = tmp;
                    r [k]++;
                }
            }

            if (testing)
                check ();
        }

        private void check () {
            for (int k = 0;k < 2;k++) {
                boolean [] done = new boolean [n];
                for (int l = 0;l < n;l++) {
                    if (done [order [k] [l]])
                        throw new Error ();
                    done [order [k] [l]] = true;
                    if (l != 0 && sums [k] [order [k] [l]] > sums [k] [order [k] [l - 1]])
                        throw new Error ();
                    if (l != n - 1 && sums [k] [order [k] [l]] < sums [k] [order [k] [l + 1]])
                        throw new Error ();
                }
            }
        }

        public String toString () {
            StringBuilder builder = new StringBuilder ();
            builder.append ('\n');
            for (int i = 0;i < n;i++) {
                for (int j = 0;j < n;j++) {
                    if (j != 0)
                        builder.append (' ');
                    builder.append (get (i,j));
                }
                builder.append ('\n');
            }
            return builder.toString ();
        }
    }

    static Map<Long,Boolean> valueMap = new HashMap<Long,Boolean> ();
    static List [] lists = {new ArrayList (),new ArrayList ()};
    static int [] [] permutations = Permutations.getPermutations (n);

    static boolean put (State state,boolean result) {
        if (valueMap.put (state.toCode (),result) != null)
            return true;

        for (int k = 0;k < 2;k++) {
            List<int []> list = (List<int []>) lists [k];
            list.clear ();
            outer:
            for (int [] permutation : permutations) {
                for (int i = 0;i < n;i++)
                    if (state.sums [k] [state.order [k] [i]] != state.sums [k] [state.order [k] [permutation [i]]])
                        continue outer;
		list.add (permutation);
            }
        }

        for (int [] p0 : (List<int []>) lists [0])
            for (int [] p1 : (List<int []>) lists [1])
                valueMap.put (state.toCode (p0,p1),result);

	return false;
    }

    static void add (State state) {
        add (state,new int [2]);
    }

     static void add (State state,int [] index) {
        if (state.isValid () && put (state,false))
            return;

        int type = state.ntypes [1] > state.ntypes [2] ? 2 : 1;
        int k = type - 1;
        int was = index [k];

        for (;index [k] < n * n;index [k]++) {
            int i = index [k] % n;
            int j = index [k] / n;

            if (state.get (i,j) == 0) {
                state.set (i,j,type);
                add (state,index);
                state.set (i,j,0);
            }
        }

        index [k] = was;
    }

    static boolean play (State state,boolean first) {
        Boolean known = valueMap.get (state.toCode ());
        if (known != null)
            return known;

        boolean result = compute (state,first);
        put (state,result);
        return result;
    }

    static boolean compute (State state,boolean first) {
        if (state.ntypes [0] == 0)
            return true;

        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
                if (state.get (i,j) == 0) {
                    state.set (i,j,first ? 1 : 2);
                    boolean result = play (state,!first);
                    state.set (i,j,0);

                    if (result == first)
                        return first;
                }

        return !first;
    }

    public static void main (String [] args) {
        for (int k = 1;k <= n;k++) {
            State state = new State ();
            for (int i = 0;i < k;i++)
                for (int j = 0;j < n + 1 - k;j++)
                    state.set (i,j,2);
            add (state);
        }

	State state = new State ();
        state.set (0,0,1);
        System.out.println ("value : " + play (state,false));
    }
}