Is it possible to paint the cells of a rectangular grid with $𝐾$ different colours such that:

  1. No two adjacent (horizontally or vertically) cells have the same colour, and
  2. Every combination of two colours appears exactly once in some two adjacent (horizontally or vertically) cells, and
  3. The sides of the rectangle are greater than 1.

I've asked this question on Puzzling StackExchange and there a solution was found for 17 colours on a 7x11 grid. Now I am wondering are there any other solutions for other values of $K$?

  • $\begingroup$ Why do you need 3rd condition? This isn't geometric problem. $\endgroup$
    – nonuser
    Jul 24, 2020 at 6:47
  • $\begingroup$ The third condition ensures that you remove trivial solutions where it is a single row of cells. Those solutions are easy to find and I am not interested in them. $\endgroup$ Jul 24, 2020 at 6:54
  • $\begingroup$ This makes me think of rook polynomials $r(n,k)$. A rook polynomial counts the number of ways to place $k$ non-attacking rooks on an $n\times n$ board. Perhaps there is an analogous "king" polynomial for rectangular boards. By that I mean a polynomial which counts the number of non-attacking king configurations on an $n\times m$ board. I think such configurations would be in bijection with your $2$-colored grids. I also think that condition $(2)$ wouldn't be to hard to encode in the polynomials... $\endgroup$
    – Condo
    Jul 24, 2020 at 16:15


You must log in to answer this question.

Browse other questions tagged .