Maxit Single-Player

Problem #118

Tags: games challenge

This task has a Challenge attached.
You may View Stats or read a Help on Challenges.

Click numbers inside rectangle to make a move

Once upon a time there was a computer game called Maxit. It was just beginning of the IBM-PC era, so the game is older than average user of CodeAbbey. Later ports included version called "Hot Numbers" with pictures by Penthouse (amiga version) - we'll not share the link here! :)

The gameplay (for two players) is simple:

In your free time you can try programming AI for this game - it is a good exercise since it is almost direct implementation of Minimax algorithm, allowing all of its features without additional complexity given by specific rules of chess, checkers etc.

Single-player modification

We'll use the following modifiation: there is only one player, and he performs "horizontal" and "vertical" moves in turns. On "horizontal" move he adds the taken value to his score while on "vertical" move he subtracts it.

The goal is to maximize score.

Try playing the small demo above to get the idea of the rules. You will see that different sequences of moves lead to different result, for example imagine the situation of half-empty board of size 3x3:

-3 :: +5
@@ :: ::
-2 :: -1

Here @@ marks the current position, :: represents empty squares and the next turn is "vertical".

Player can choose to take -2 or -3 - then remaining moves would be pre-determined. If he choses -2 he has the following chain of score change:

sub -2
add -1
sub +5
add -3
------
    -7

If instead he choses -3 then his fate is completely different:

sub -3
add +5
sub -1
add -2
------
    +7

If the field has one extra value -1, like this:

-3 :: +5
@@ :: -1
-2 :: -1

Then player can prefer to take it on the 3rd move to end the game before clearing the whole board with +9 score (because there would be no more values in the middle row and no move could be made).

Problem statement

You will be given large square field and your goal is to get maximum score of it following the rules described above. As an answer you'll need to return the sequence of moves. Each move should be represented by a single value - the index of the cell in the current row or current column, 0-based.

Input data will contain the size of the field in the first line.
Then the field itself will follow, rows are numbered from the top and columns from the left.
0 will mark the starting position of the "current" cell.
Answer should contain the sequence of moves.

Example:

input data:
4
 0 -3 +4 +3
-3 +4 -2 -1
+2 -1 -4 +3
-3 -1 -1 -2

answer:
2 2 0 1 1 0 3 3 2 1 3 2 1 3 0

This sequence of moves will lead to score of 19, though you can do better!

Challenge result is assessed by the following formula:

score = score_gained_by_user()
max = 51000
min = 46000
result = (score - min) / (max - min)
You need to login to get test data and submit solution.