## Psycho Killer

Source

I got this problem from Rustan Leino, who got it from Carroll Morgan.

I solved it and wrote up my solution.

Problem

A building has 16 rooms, arranged in a 4x4 grid. There's a door between every pair of adjacent rooms ("adjacent" meaning north, south, west, and east, but no diagonals). Only the room in the northeast corner has a door that leads out of the building.

In the initial configuration, there's one person in each room. The person in the southwest corner is a psycho killer, and the rest cannot move because they're chained to the floor. The psycho killer has the following traits: If they enter a room where there's another person, they immediately kill that other person. But, they also can't stand the sight of blood, so they won't enter any room where there's a dead person.

As it happened, from that initial configuration, the psycho killer managed to get out of the building after killing all the other 15 people. What path could they have taken?

Solution