When Not to Simulate a Game (UVa 11553)

Grid

Some programming puzzles can be solved by simulating a game or process. For example:

UVa 978 is based on simulating a conflict between warring lemmings.
For UVa 732, you have to simulate something more abstract: a stack that pushes and pops characters.

UVa 11553 may seem like a classic simulation problem: a board game between two players. But it soon becomes clear that this problem can’t be solved by simulating the players’ moves.

The Problem

Two players, Alice and Bob, play a game on a $n \times n$ grid containing random integers. On each turn, Alice crosses out a row and Bob crosses out a column. The integer at the intersection of the row and column is added to a total score. The game ends when every row and every column have been crossed out. Alice’s goal is to maximize the total score. Bob’s goal is to minimize it. Given a particular game board, what is the best score Alice can achieve, assuming Alice and Bob both play perfectly.

Complete Search

This problem is in the Complete Search section of uHunt Chapter 3, so let’s see what it would take to search all possible move options for both players.

Alice gets the first move, and can choose any of $n$ rows. Bob can then respond by choosing any of $n$ columns. On the next turn, one row is crossed out, so Alice only has $n-1$ choices. Similarly, Bob must choose one of the $n-1$ remaining columns. The game proceeds until the last turn, when each player only has one choice. Therefore, the total number of possible games is $n \cdot n \cdot (n-1) \cdot (n-1) \cdot … \cdot 1 \cdot 1$, or ($n! \cdot n!$).

The problem statement tells us that $n$ can be up to 8, so to check all possibilities on the largest board, we would have to search $(8!)^2 = 40320^2 \approx 1.6 \times 10^9$ games. Calculating the total score for each game requires keeping track of the sum of $n$ integers, which you might do using another inner loop of size $n$, for a total of $(8!)^2 \cdot 8 \approx 1.3 \times 10^{10}$ operations to do the main simulation. Opinions vary about how many operations per second one should assume an online judge can carry out. But $10^{10}$ operations in one second (the time limit for this problem) is beyond even the most optimistic estimates.

A Greedy Solution?

Since we can’t simulate the whole game for the largest board, is there a greedy solution we can use to cut down on the number of turns that need to be searched? Greedy problems have their own section in uHunt Chapter 3, but let’s pretend we encountered this problem in the wild, and didn’t get that hint.

Since Alice is trying to maximize her score, and she gets to go first, maybe there’s an order she can pick rows so Bob is forced to get higher numbers than he wants on each turn.

Consider this $3 \times 3$ grid:

 1 -2 -3
-3  4 -5
-2  1  3

That -5 looks bad for Alice, so what if she starts the game by picking the first row? She might try that as a way of enticing Bob into greedily picking the third column and getting (for him) the best number on that row, -3. That takes the third column out of play, which means the -5 can never be picked, pushing the final score in Alice’s favor. The total game score might come out to $(-3) + (-3) + 1 = -5$.

But this sequence of moves violates the requirement for both players to play perfectly. There’s nothing preventing Bob from selecting other columns until Alice selects row 2 and he can get that nice -5. In fact, that would be a better strategy for him.

A Solution Without Simulation

Once you start thinking about how to come up with a greedy solution, you may discover the surprise fact about this problem: Alice’s moves are completely irrelevant. She has no influence over the final score, regardless of which rows she picks. Since Bob plays last on each turn, he gets to pick the optimal number in each row. The only restriction that applies to him is that he can’t pick two numbers in the same column.

So rather than a game between two players, we can reduce the problem to:

Given a grid of random integers, pick one number from each row such that the sum of your selected numbers is as small as possible, and no two of your numbers are from the same column.

Bob’s goal is to minimize the total score. If Bob has access to a computer, he can accomplish this as follows using the revised problem statement:

Consider all $n!$ permutations of number selections: one of the $n$ numbers from the first row, one of the $n-1$ remaining numbers in a different column from the second row, and so on.
Of those permutations, pick the one with the lowest sum, and remember the optimal column for each row.
When Alice selects a row, pick the optimal column for that row. The order in which Alice selects the rows does not affect the outcome, since Bob knows that Alice eventually has to pick every row.

Using this process, Bob can always get the lowest possible score given the constraints of the problem. And since there are $8! = 40320$ permutations at most, an online judge will execute this solution in well under one second, even using Java.

Pseudocode

Here’s how the solution works for each test case:

read the grid input
create an array of ints called colOrder, initialized
    to the starting order 0, 1, ..., n-1
for each permutation of colOrder
    for i from 0 to n-1
        retrieve the grid value at
            row i and the column number at
            position i in colOrder
        increment the total by that value
    if this total is smaller than any total found
        so far, update the minimum total
print the minimum total found

This solution is based on generating all permutations of the column numbers $0$ through $n-1$. Each of these permutations represents one of the $n!$ possible mapping of row numbers to column numbers. The one that produces the lowest sum is the one Bob should use. For this problem, we only need to save the total, not the permutation.

If you’re using C++, you can generate permutations using the next_permutation STL function. If you’re using a different language, take a look at Project Nayuki’s next lexicographical permutation algorithm.

Thinking Through This Problem

If you didn’t immediately notice the trick for this problem, try thinking through solutions in order of decreasing performance. The brute-force solution (trying all possibilities) will give you a basic idea of how the game works, but doesn’t provide much insight into what the problem is really asking. Thinking about the greedy approach should lead you to the realization that Bob has complete control of this game, and doesn’t have to make decisions based on Alice’s moves. From there, you can design a fast solution that only considers Bob’s moves.

(Image credit: Robson#)