NES Programming

How would you program a complex game, like RTS or Roguelike, in the context of NES constraints?

I think the first console roguelikes were on SNES (the early Mystery Dungeon/Shiren games), and when it comes to indie stuff the 'worst' hardware I could think of is GBA (POWDER). NES is definitely weaker than SNES and GBA, as well as mainframes and minicomputers on which early roguelikes were played, but I do think it is doable. the aforementioned SNES and GBA roguelikes have solved the interface problem (as traditionally, those kinds of games required a full keyboard) but I think the biggest issue you'll face will be getting a decent RNG to run on an 8-bit processor without taking a lot of time. maybe look up Atari and C64 maze generators?