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.
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.
defgen_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(lambdat:1<=t[0]<=nand1<=t[1]<=n,moves))returnmovesdefget_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}defis_winning_pos(x,y,layers,n):losing_moves=0#numberofeligiblemovesthatleadtoalossofthecurrentplayerouter_moves=[]moves=gen_eligible_moves(x,y,n)formoveinmoves:layer_coords=get_layer_coords(*move)# If layer has been seen, ...iflayer_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 winiflayers[layer_coords['layer']][layer_coords['height']]==0:return1# ... else it's a move that leads to a losselse:losing_moves+=1# if the layer has not been seen, the move is stored in a variable which will be used laterelse:outer_moves+=[layer_coords]# if all moves lead to a loss, the current position leads to a lossiflosing_moves==len(moves):return0else:# 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.returnabs(1-is_winning_pos(outer_moves[0]['height']+1,outer_moves[0]['layer']+1,layers,n))defgen_results_by_pos(n):layers=[[0],[0,0]]forcinrange(3,n+1):layers+=[[]]forrinrange(1,c+1):layers[c-1]+=[is_winning_pos(r,c,layers,n)]returnlayersdefchessboardGame(x,y):n=15layers=gen_results_by_pos(n)layer_coords=get_layer_coords(x,y)result=layers[layer_coords['layer']][layer_coords['height']]return'First'ifresult==1else'Second'
A Chessboard Game
You are viewing a single comment's thread. Return to all 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.