Lighting up a grid

Lighting up a grid

This puzzle is about finding the optimal way to set a grid on fire. The question was posed by @algopuzzles on Twitter:

Spoiler alert: upper bound.
Spoiler alert: lower bound.

Followup comments:

  • It was conjectured that every solution "looks" like a permutation matrix. We do have examples to show that there are permutation-matrix-like configurations where the fire does not spread at all. Are there solutions that place light up more than one cell in a row or column?
  • Count the number of solutions. More generally, given a number between and , how many configurations with nodes lit up are such that they will eventually leave t nodes on fire?
  • Make a JavaScript-based web interactive that people can play with :)

super-embed:<div id="hyvor-talk-view"></div><script async defer type="text/javascript" src="//talk.hyvor.com/web-api/embed.js"></script>