story - Lights in the Dungeon: Eighteen by Eleven

This is the fourth in a series Lights in the Dungeon puzzles.

_{previous (3rd) <--|--> next (5th)}

---

The five by five dungeon was only a little harder than the previous ones. You're feeling pretty good about it and you're even up for a little taunting. "Alright, Hooty, where the six by six?" you ask as you approach the cloaked figure waiting for you at the exit.

"Six by six?" asks the Lord, feigning ignorance. "I'm afraid I don't know what you talking about. You see, Fakky Jim and I have been working on your next challenge while you were busy rearranging tiles and walking through the dungeon, flipping lights like a good little monkey. Your next challenge is... a bit more grand. If you succeed, I promise to tell you the real reason I've brought you here."

Intrigued, you walk over to Fakky Jim and receive a scroll with the rules. You can tell they've been re-written from scratch as they were getting a bit illegible with all the strikethroughs and revisions from the previous puzzles.

1. You will enter a dungeon in which you must visit every room and turn off the light in the middle, an easy operation to perform.


2. As soon as you exit a room, every door to that room slams shut and locks. You can not re-enter that room through any means.


3. The map below shows the current design of the dungeon with each room bordered by red and labeled with a alphabetic character.


4. You may rearrange the rooms however you like before you enter but you cannot change the perimeter of the dungeon. In this case, that means you must maintain the exact stairstep shape that is eighteen rooms tall and somewhere between seven and eleven rooms wide.


5. You cannot rotate or flip rooms. You may only translate them.


6. The dungeon must have exactly one entrance and one exit.



7. There must be exactly one possible path through the dungeon. Obviously, any path is reversible if you simply enter from the other end but that does not count as a separate possible path.

Surprised, you look up at Fakky Jim and ask, "What happened to the collapsing floors?" The Grand Vizier just stares at you. You're not sure what you expected from a cat, magic though it may be. You turn to Lord Hooty and repeat the question.

"Ah," he starts, a sorrowful look upon his face, "we changed that after losing the cleaning crew. It was a tragedy, really. They were only doing their job. At least they were tasty so that's a silver lining."

---

How can you rearrange the dungeon rooms so that you can win the game?

_{There are probably multiple solutions. The first valid answer will be accepted.}

AAAAAAA
AABBBBB
CCCCCCC
DDDDDDEE
EFFFFFFF
FFFFFFFF
FFFFGGGGG
GHHHHMMMM
MMMMMMMMM
MMMMMMMMMM

MMMMMMMMMM
MMMMMMMMNN
NNNNNNNNNNN
NNNNNNNNNNN
NNNNNNNNNNN
OOOOOOOPPPP
PPPPPPPPPPP
PPPPPPPPPPP

---

For reference, here are the 16 possible rooms. (Note that this is all possible rooms. For this puzzle, you must use exactly the rooms shown in the map above.)

Answer

I started from the bottom-right corner and tried to get rid of all the Ms and Ns first, so I came up with:

Or as text:

ACPPPBC

PAGPPMM
PBHBOMM
PAGHHMMP
PPPPOMMP
FGGEDMMP
FGNOPMMFC
PPPFPMMMM
FHBEPMMMM
FADFCMMMMP
FBCFFMMMMP

AEFDFMMMMP
FNNNDMMMANC
ANNNCMMFNGM
FNNNOMFPFOM
ANNNNOFNDPM
FNNNNNNNNOD
ANNNNNNNNNN