| Sudoku is a Japanese game which has become extremely popular recently.
In the game, we try to fill an N2 x N2
grid with integers from 1 to N2. The rules state that
each row and column must contain exactly one occurrence of each of the
N2 integers. Additionally, each of the
N2 aligned N x N subsquares must also contain
exactly one occurrence of each integer. The following is a valid
Sudoku grid with N = 3.
The game is to figure out how the whole grid is filled in, given the
numbers from just a few of the cells in the grid. Obviously, the more
information you have, the easier the problem becomes. In this
problem, you will start with an empty grid. You will then make a
sequence of queries, and the contents of the cell that you query will
be revealed to you. Eventually, you will have enough information that
you should be able to uniquely determine the values of all the cells.
You will be scored based on the number of queries that you make,
combined with the total amount of time from start to finish for a particular test case. Your score for a
particular test case will be proportional to
2-queries/(0.1+total execution time). Naturally, if your answer is incorrect for any reason, you will get a 0 for that test case. Additionally, if you repeat the same query more than once, you will get a 0.
Your total score will be proportional to the sum over i of SCOREi/OPTi, where OPTi is the highest score for a test case i, and SCOREi is your score for that case.
You will be allowed a total processing time
of 1 minute per test case over all queries, but only 5 seconds processing time
from one query to the next.
Your class should have a method initialize, which takes an
int, 3<=N<=8, corresponding to the size of the grid (3
above). The initialize method should return your first query as a
int[] with two elements: the row and column of your
query, respectively (1-based). The results of each query will be passed to a
method queryResults, which takes a int[] (the query you
submitted), and a int the result of the query. This
method should either returns the next query (as a int[]
with two elements), or else the solution to the puzzle, as a
int[] with N4 elements, in row major order.
Thus, the solution to the above puzzle would be:
{8,2,5,4,7,1,3,9,6,1,9,4,3,2,6,5,7,8,3,7,6,9,8,5,2,4,1,
5,1,9,7,4,3,8,6,2,6,3,2,5,9,8,4,1,7,4,8,7,6,1,2,9,3,5,
2,6,3,1,5,9,7,8,4,9,4,8,2,6,7,1,5,3,7,5,1,8,3,4,6,2,9}
|