Bạn có chắc là đề đầy đủ không? Nếu tô màu đỏ ở một ô ở góc (trái cùng chẳng hạn), rồi tô vàng tất cả các ô còn lại, thì ta có $n = 2$. Vậy $n_{\min} \le 2$.
Mặt khác, nếu $n=1$ thì sẽ vô lý. Bằng phản chứng, ta lấy một cặp ô vuông khác màu và chung một cạnh, ta gọi hai ô là $T, P$ lần lượt cho trái, phải. Không mất tính tổng quát thì giả sử cặp này nằm ngang. Khi đó, ta sẽ có thêm 2 ô "láng giềng" nằm trên hoặc dưới của cặp này (luôn tồn tại vì độ dài bàn cờ $\ge 2$). Ô láng giềng bên trái sẽ cùng màu với $T$ và ô láng giềng bên phải sẽ cùng màu với $P$, do đó cạnh chung của hai ô láng giềng thỏa điều kiện cần tìm, nhưng ta đã giả sử từ đầu $n=1$, nên dẫn tới vô lý. Vậy $n_{\min} \ge 2$.
Kết luận: $n_{\min} = 2$.