Here is the solved killer sudoku:
The key is: 1-K, 2-F, 3-G, 4-E, 5-A, 6-R, 7-I, 8-H
The solution path can be seen below.
The puzzle in the background is a
sokoban, as indicated by the hirigana in the steps: そ, こ, ば, and ん represent the syllables so, ko, ba, and n, respectively. It has a relatively simple solution path:
The numbers traced along the solution path are 8-5-3-4-6-2-7-1-7-6, or HAGERFIKIR, which happens to be the name of a theater.
This means that Gladys must have started out her journey in
Addis Ababa, Ethiopia, or more specifically, the Hager Fikir Theatre!
Full solution path for the sudoku (disclaimer - this is a slightly more logical version of my actual path when solving for the first time so as to make myself look a bit less like an idiot):
First, there are two letters which are each used in three cages within the same box: H and I. These must be 7 and 8 in some order, since only 7 and 8 have three different sums with distinct digits (within the scope of this puzzle, of course). Furthermore, if H was 7, the digits outside of the H cages would have to be 7 and 8, meaning A would also have to be at least 8, a contradiction. Therefore H is 8 and I is 7. We can quickly fill in R as 6 as well due to the cage of size 3:
Let's continue looking at the box with the 3 8-cages. We know that these cages must include 1-7, 2-6, and 3-5, in some order, meaning 4 and 8 must be outside of those three cages. However, one of these is also in a cage, and it obviously can't be 8 or else it wouldn't add up to A. Thus, that number must be 4, and with 6 and up already off the table, A must be 5, K must be 1, and we can use the A in the bottom left to complete a cage:
The top cell of the 3-cell 6-cage must be a 1, due to the 1 in the lower box. That (and the 1-4 cage below it) means that the 5-cage in the upper right box must be a 2-3, in some order, and the 6-cage directly above it must be a 1 and a 5. We can now place the 5 and 6 in the top-left box, and the 8 in the top-right box due to normal sudoku rules:
With a 1 and a 5 already in the column, the rightmost 7-cage in the bottom-left box must be a 3-4, leaving the other as a 1-6. The 6-cage immediately above that one must be a 2-4 (which is resolvable). Now, the minimum sum for the E-cage is 4, which is also our highest remaining unassigned value, so that cage must be a 1-3. With so many possibilities stacked in columns, we can now fill in the top-left box:
With six of the eight letter-digit pairs found, that leaves F and G to be 2 and 3 in some order. There's already a 2 in the seventh row, so F must be 2 and G must be 3. Also, the only possible remaining combination for the 8-cage in between them is 1 and 7. This places the 4 and the 7 in the top-right box, and with the five in the bottom row, we can now complete that column and disambiguate several cages:
Using regular old sudoku rules, we can find the 6 in r4c4 and the 1 and then the 5 in the bottom-right box, as well as the 7 in between them because of killer sudoku. That 5 is particularly helpful, as with a 1 already in that column, the cage directly above it must be a 2-6, leaving a 3-5 in the rest of that box, both of which we can immediately disambiguate. We can also fill in the 7-8 pair in the bottom-left box, the 1-3 pair in the leftmost row, the 2-3 pair in the top-right box, and the 1-7 pair in the fifth column:
From here, you could figure out that the only remaining cage must be a 3-4 and use the 3 in the third column to disambiguate it, but you don't technically need to - the rest of the puzzle can be solved using nothing but columns, rows, and boxes:
