We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Chessboard Game, Again!
  5. Discussions

Chessboard Game, Again!

  • xdavidliu
     + 0 comments

    java solution, passes all test cases in O(k) time and O(1) space. First compute the nimber (e.g. Grundy number) for all 15 x 15=225 spots on the chess board. The nimber of a spot (x,y) is the smallest non-negative integer not equal to the grundy numbers of any of the up to four spots reachable from (x,y) in a single jump. This can be done in O(m^2) time, where m=15=O(1) in this problem, by filling in successive diagonals of the matrix of nimbers.

    Once we have the nimbers of every spot on the chessboard, simply take cumulative XOR of all k nimbers. If 0, the first player loses, and if nonzero, the first player wins.

    import java.util.Scanner;

class Solution{
    static int[][] nimbers(final int side){
	int[][] nb=new int[side][side];
	for(int j=2;j<2*side-1;++j){
	    int i=j<side?0:j-side+1;
	    int k=j<side?j:side-1;
	    while(i<=k){
		boolean[] seen=new boolean[4+1];
		if(i>1){
		    seen[nb[i-2][k-1]]=true;
		    if(k!=side-1) seen[nb[i-2][k+1]]=true;
		}
		if(k>1){
		    if(i!=0) seen[nb[i-1][k-2]]=true;
		    if(i!=side-1) seen[nb[i+1][k-2]]=true;
		}
		int l=0;
		while(seen[l]) ++l;
		nb[i][k]=l;
		nb[k][i]=l;
		++i;
		--k;
	    }
	}
	return nb;
    }
    static boolean win(int nCoin, Scanner sc, int[][] nb){
	int nimSum=0;
	while(nCoin-- != 0){
	    int x=sc.nextInt(), y=sc.nextInt();
	    nimSum ^= nb[x-1][y-1];
	}
	return nimSum!=0;
    }
    public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
	int nCase=sc.nextInt(), side=15;
	int[][] nb=nimbers(side);
	while(nCase-- != 0){
	    int nCoin=sc.nextInt();
	    System.out.println(win(nCoin,sc,nb)?"First":"Second");
	}
	sc.close();
    }
}