Programming Assignment 4: Alien Chess
CECS 328
1 Deadline
Friday, November 19th
2 Alien Chess
On the planet Xeebo, chess is played with only one type of board piece. On a m
by n board (where 4 ≤ m ≤ 7 and n is large), one of the players first assigns a
positive integer value to each square of the board. The other player then places
pieces on the board so as to maximize the sum of the scores on the squares that
it has chosen subject to one restriction: No piece can be placed on a square that
is immediately vertical or horizontal to another piece. (Think of the pieces as
one-square, non-attacking rooks.)
You are playing this game with a Xeebo and your goal is to write a program
that can optimally determine the best place to put your pieces. You will return
a list of the positions that you choose. (Board positions are (row, column) and
start counting from 0. Repeated positions will be counted incorrect.)
HINT: With the rows that small, it might be worth it to precompute, given a
particular type of column placement in column i, all of the possible next column
types that could be in column i + 1.
3 Your code
The Java header for your function in StudentSolver.java should be:
public static ArrayList<Pair<Integer,Integer>> solve(int[][] board)
The Python header for your function in studentsolver.py should be:
def solve(board)
The C++ header for your function in StudentSolver.h should be:
static std::vector<std::pair<int, int>> solve(int** board, int m, int
n);
1
4 Example
Consider the following 4 × 6 board:
[[35, 90, 54, 62, 62, 69], [89, 17, 59, 13, 76, 24], [73, 1, 57, 11, 60, 34], [52, 94, 21, 67, 9, 77]]
The optimal solution would be
[(0, 5),(3, 5),(1, 4),(0, 3),(3, 3),(1, 2),(0, 1),(3, 1),(1, 0)]
for a total of 69 + 77 + 76 + 62 + 67 + 59 + 90 + 94 + 89 = 683.
2
