I think it is a cool concept for a game. Maybe you could add a playback function that shows the change of the political climate and religion over time.  Another idea is to add an AI of some sorts. The AI would color squares according to traits or other factors that have a certain weight to them that influences the choice of the computer. For example the AI would have a preference for uncolored squares, but if it has the conqueror trait it would have a preference for colored tiles instead. Another example would be that the AI has lower preference for uncolored tiles behind/over rivers to from natural borders and stuff. These are just some ideas, I actually have no idea how hard it is to code. So whatever your choice will be I will be excited for your next addition to the game :D