# A Chessboard Game

# A Chessboard Game

+ 0 comments Easiest code in java

public static String chessboardGame(int i, int j) { i--;j--; if(i==15 && j==15) return "Second"; if((i%4==0 || i%4==1) && (j%4==0 || j%4==1)) return "Second"; else return "First"; }

+ 0 comments public static String chessboardGame(int x, int y) { x--;y--; if((x/2)%2==0 && (y/2)%2==0) return "Second"; return "First"; }

+ 0 comments def chessboardGame(x, y): return 'First' if ((x-1)//2)%2 or ((y-1)//2)%2 else 'Second'

+ 0 comments js

function chessboardGame(x, y) { return !(x%4%3) || !(y%4%3) ? "First" : "Second" }

+ 0 comments A solution in Python that can generalize to any n x n board, by exploiting the fact that the chessboard is symmetrical and the player moves from (x,y) to (x - 2, y - 1), (x - 2, y + 1) are symmetrical to the moves from from (x,y) to (x + 1, y - 2), (x - 1, y - 2), with respect to the main diagonal. With that in mind, we only need to understand the outcomes (win or lose) for each position on a given column up to row {column number}. These are called 'layers' in the code below. The layers list start at column 1 with the coordinate (1,1) with outcome '0' (lose), and moves on to column 2 with coordinates (2,1) and (2,2) with outcomes '0' and '0', and so on, until the last column. Iterating from the top left, we can fill all positions outcomes and use that to determine which player wins or loses.

def gen_eligible_moves(x, y, n): """Returns a list of moves that end within the chessboard bounds""" moves = [(x + 1, y - 2), (x - 1, y - 2), (x - 2, y - 1), (x - 2, y + 1)] moves = list(filter(lambda t: 1 <= t[0] <= n and 1 <= t[1] <= n, moves)) return moves def get_layer_coords(x, y): """Returns the layer and layer position for a given board coordinate""" return {'layer': max(x, y) - 1, 'height': min(x, y) - 1} def is_winning_pos(x, y, layers, n): losing_moves = 0 # number of eligible moves that lead to a loss of the current player outer_moves = [] moves = gen_eligible_moves(x, y, n) for move in moves: layer_coords = get_layer_coords(*move) # If layer has been seen, ... if layer_coords['layer'] < len(layers): # ... and there is at least one target position that leads to a loss, the current player will throw the other player into it and the current player will win if layers[layer_coords['layer']][layer_coords['height']] == 0: return 1 # ... else it's a move that leads to a loss else: losing_moves += 1 # if the layer has not been seen, the move is stored in a variable which will be used later else: outer_moves += [layer_coords] # if all moves lead to a loss, the current position leads to a loss if losing_moves == len(moves): return 0 else: # If the current player could not find a winning move and was not limited to only losing moves, call the function recursively on any outer possible move. As we'll reach all positions, it does not matter which outer move we chooose at this position, so the first one is chosen for simplicity. Note that the outcome of that position will be the opposite of the outcome of the current position, as the other player will be playing the next position. return abs(1 - is_winning_pos(outer_moves[0]['height'] + 1, outer_moves[0]['layer'] + 1, layers, n)) def gen_results_by_pos(n): layers = [[0], [0, 0]] for c in range(3, n+1): layers += [[]] for r in range(1, c + 1): layers[c - 1] += [is_winning_pos(r, c, layers, n)] return layers def chessboardGame(x, y): n = 15 layers = gen_results_by_pos(n) layer_coords = get_layer_coords(x, y) result = layers[layer_coords['layer']][layer_coords['height']] return 'First' if result == 1 else 'Second'

Sort 62 Discussions, By:

Please Login in order to post a comment