UVa 167

From Algorithmist
Jump to navigation Jump to search

167 - The Sultan's Successors[edit]

Summary[edit]

Determine what solution of the 8-queens problem produces the highest number on the given board.

Methods[edit]

There are two main methods of solving that problem:

  • 1) The former is to use backtracking where you compute each possible solution recursively and output the highest sum.
  • 2) Use the knowledge that people have already computed the possible combinations of valid chessboard locations, hardcode them into the program and see which of them produces the highest sum.

The second method is essentially a shortcut through the first method.

Tip: On a board just like in the sample input except where the location 1,7 is 49 and not 48, all combinations of valid 8-queens locations will produce the sum of 260. This can be used to see if there have been typos or they've been miscalculated.

Optimizations[edit]

Considering the two methods, there are a few possible optimizations:

  • 1)
    • Only try to place the queens at valid locations. If no valid location is available, backtrack.
    • Start at the first row or column, then the second one and so forth. Do it systematically.
    • When trying each location, try to see immediately if the location is valid by seeing if the location is already threatened by a queen which has already been placed.
    • Between cases, remember which locations are valid so you don't have to find the locations repeatedly.
  • 2)
    • Optimizations are based on execution of calculating the sums of already known locations and other minimal factors.

Gotchas[edit]

  • The output must be in 5-character fields followed by a newline after each sum.
  • The Online Judge expects the last sum to be followed by a newline.

Input[edit]

  • Note that the integer value in the first column in the 7th row of the chessboard is a repeat from the last column in row 6.
  • It starts with an integer K which consists of the number of cases, which are no more than 20.
  • It follows with a K number of 8x8 boards where each row is followed by a newline.
  • There are no empty lines between the boards.
1
 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Output[edit]

  260

Solution[edit]