Random coloring of a grid with no more than two straight nodes the same color, guaranteed to terminate

Question

Given a n×m grid graph, is there an algorithm that determines a random coloring of that graph (with k > 2 colors) such that—

• Up to two, but no more than two, adjacent nodes of the same color occur horizontally or vertically,
• the algorithm is guaranteed to terminate, and
• optionally, the algorithm chooses uniformly among all possible combinations?

Inspired by this question.

Answer 1

This seems very straightforward.

• Start with an uncolored grid graph.
• Visit all the nodes in the obvious order, left to right, top to bottom. At each visited node, choose any colour for it that does not complete a three-in-a-row triplets of the same colour.

It is always possible to choose a colour for each node, since there are at most two possible triplets that the currently visited node could complete (with the two nodes to its left or the two nodes above it - the other directions are not yet coloured) so at most two of the $k>2$ colours are disallowed.

This will not result in uniform choice amongst the available grids. The more adjacent pairs you create, the fewer choices you get to have when choosing colours for later nodes. So one choice of colour might lead to fewer possible completed grids than another choice. Ideally you'd want every node colour choice to be weighted by the number of possible completed grids that choice could lead to, but you can't really calculate that exactly. It might be possible to skew it a bit more towards uniform by estimating the number of grids available for each choice by taking into account any adjacent pairs you create. It is probably not worth it though since there are so many grids that any non-uniformity will go unnoticed in practice.