In this HackerRank Chessboard Game, Again! problem solution we have given the value of K coins and the initial coordinates of K coins, we need to determine which player will win the game. assume both players always move optimally.

HackerRank Chessboard Game, Again! problem solution


Problem solution in Python.

#!/bin/python3

import os
import sys

nimbers = dict()
def findNimber(x, y):
    if x < 1 or y < 1 or x > 15 or y > 15:
        return -1
    if (x, y) in nimbers:
        return nimbers[(x, y)]
    check = []
    check.append(findNimber(x - 1, y - 2))
    check.append(findNimber(x + 1, y - 2))
    check.append(findNimber(x - 2, y + 1))
    check.append(findNimber(x - 2, y - 1))
    i = 0
    while True:
        if i not in check:
            nimbers[(x, y)]=i
            return i
        i += 1

def chessboardGame(coins):
    grundy = 0
    for x, y in coins:
        grundy ^= findNimber(x, y)
    return "First" if grundy else "Second"

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        k = int(input())

        coins = []

        for _ in range(k):
            coins.append(list(map(int, input().rstrip().split())))

        result = chessboardGame(coins)

        fptr.write(result + '\n')

    fptr.close()


Problem solution in Java.

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();
    }
}


Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int a[15][15];
bool c[11];

void ch(int x, int y, bool z) {
    if (x > 1 && y > 0) c[a[x-2][y-1]] = z;
    if (x > 1 && y < 14) c[a[x-2][y+1]] = z;
    if (x > 0 && y > 1) c[a[x-1][y-2]] = z;
    if (x < 14 && y > 1) c[a[x+1][y-2]] = z;
}

int main() {
    int t, n, r, x, y;
    for (int i = 2; i < 15; i++) {
        x = 0, y = i;
        for (; y >= 0; x++, y--) {
            if (x == 1 && y == 1) continue;
            ch(x, y, true);
            for (int j = 0; j < 5; j++) if (!c[j]) { a[x][y] = j; break; }
            ch(x, y, false);
        }
    }
    for (int i = 1; i < 15; i++) {
        x = i, y = 14;
        for (; x <= 14; x++, y--) {
            //cout << x << " " << y << endl;
            ch(x, y, true);
            for (int j = 0; j < 10; j++) if (!c[j]) { a[x][y] = j; break; }
            ch(x, y, false);
        }
    }
    cin >> t;
    while (t--) {
        r = 0;
        cin >> n;
        while (n--) {
            cin >> x >> y;
            x--, y--;
            r ^= a[x][y];
        }
        
        if (r) cout << "First" << endl;
        else cout << "Second" << endl;
    }
}


Problem solution in C.

#include<stdio.h>
#include<stdbool.h>
#define N 15
int Grundy[N+1][N+1];
static inline int grundy(int x, int y)
{
    if( x < 1 || x > N || y < 1 || y > N )
    {
        return 10;
    }
    if( Grundy[x][y] >= 0 )
    {
        return Grundy[x][y];
    }
    bool Previous[10+1] = {};
    Previous[grundy(x-2, y+1)] = Previous[grundy(x-2, y-1)] = Previous[grundy(x+1, y-2)] =Previous[grundy(x-1, y-2)] = true;
    unsigned ret = 0;
    while(Previous[ret])
    {
        ++ret;
    }
    Grundy[x][y] = ret;
    return ret;
}
int main()
{
    memset(Grundy, 0xFF, sizeof(Grundy));
    int t, i, j;
    scanf("%d\n", &t);
    for( i = 0 ; i < t ; ++i )
    {
        int k, res = 0;
        scanf("%d\n", &k);
        for( j = 0 ; j < k ; ++j )
        {
            int x, y;
            scanf("%d %d\n", &x, &y);
            res ^= grundy(x, y);
        }
        printf("%s\n", res ? "First" : "Second");
    }
    return 0;
}