Ley del cuadrado como grafo

Estaba en clase de ajedrez, de esas en las que te ponen un final “típico” y el profe suelta una frase como si fuese un hechizo: “ley del cuadrado”. Dibuja un cuadrado desde el peón, mira al rey, y en dos segundos ya está decidido si lo alcanza. Todo el mundo asiente… pero por dentro te queda la misma sensación que cuando alguien dice “confía”: funciona, sí, pero ¿por qué?

La ley del cuadrado se suele enseñar como un truco visual: dibujas un cuadrado desde el peón y, si el rey está dentro, lo alcanza antes de que corone. Funciona… pero parece magia.

Aquí la desmagificamos en modo “ciencia de sofá”: lo convertimos en un problema general de alcanzabilidad en un grafo con horizonte temporal, y lo reducimos a resolver desigualdades. Si te gustan los “por qué” más que los “mira qué regla”, este es tu post.

0 · La idea general (principios)

Para no perdernos, nos guiamos por tres principios muy simples:

Principio 1 (discreto): las piezas no se mueven en un plano continuo; saltan entre casillas. Eso sugiere trabajar con grafos (redes de estados).
Principio 2 (métrica inducida): la “distancia” relevante no es la de la regla sobre el papel, sino la que define el coste real de moverse: número de turnos.
Principio 3 (espacio-tiempo): el peón no es un objetivo fijo: es una trayectoria en el tiempo. Capturar significa interceptar esa trayectoria antes de un deadline (la coronación).

Con eso, el plan es: modelamos el rey como grafo → identificamos la métrica correcta → escribimos la captura como “existe t” → sustituimos coordenadas → nos quedan desigualdades.

1 · El tablero como grafo

Un grafo no es más que “lugares” y “caminos entre lugares”. Si prefieres analogías: como un mapa de metro (estaciones y conexiones) o como Google Maps (intersecciones y calles).

Aquí las “estaciones” son las casillas y las “vías” son los movimientos legales del rey. Esto no es una manía: en un grafo, la distancia natural es “mínimo número de aristas”, que es exactamente “mínimo número de turnos”.

Definimos primero el conjunto de casillas (vértices). El producto cartesiano {1..8}×{1..8} significa “todas las combinaciones de columna y fila”.

V=\{1,\dots,8\}\times\{1,\dots,8\}

Ahora las aristas del rey: E_K (K de King) es el conjunto de pares (u,v) tal que el rey puede ir de u a v en un movimiento.

E_K=\{(u,v)\in V\times V:\ v-u=(dx,dy),\ dx,dy\in\{-1,0,1\},\ (dx,dy)\neq(0,0)\}

Y el grafo completo del rey se escribe como un par: G_K = (V, E_K). Es decir: posiciones + transiciones.

\[ G_K=(V,E_K) \]

Grafo de movimientos del rey en el tablero: cada casilla conecta con sus adyacentes — El tablero como grafo: casillas = vértices, movimientos del rey = aristas. La distancia en el grafo coincide con “número de turnos”.

¿Qué significa dist_G(u,v)?

En un grafo, dist_G(u,v) es la distancia de grafo: el mínimo número de pasos para ir de u a v. En la analogía del metro: el mínimo número de paradas. En ajedrez: el mínimo número de turnos.

\operatorname{dist}_G(u,v):=\min\{t\in\mathbb{N}:\exists\ \text{camino }u=v_0\sim v_1\sim\cdots\sim v_t=v\}

Donde “~” solo significa “hay una arista entre esas dos casillas”.

¿Qué significa Reach(u,t)?

Reach(u,t) (de reachable) es el conjunto de casillas a las que puedes llegar desde u en t movimientos o menos. Piensa en ello como el “radio de acción” de un robot con batería limitada: con t unidades de energía, ¿qué zona cubre?

\operatorname{Reach}(u,t):=\{\,v\in V:\operatorname{dist}_G(u,v)\le t\,\}

Este objeto va a ser protagonista: si la trayectoria del peón “entra” en esta nube en algún momento, hay captura.

2 · Por qué no es euclídeo (y el cameo de √2)

Aquí viene la idea clave: la geometría del tablero en papel no es la geometría del rey.

En geometría euclídea (la de Pitágoras), moverte una casilla en horizontal mide 1, en vertical mide 1, y en diagonal mide √2 (hipotenusa de un triángulo 1–1–√2).

Pero el rey no paga √2 por la diagonal: la diagonal cuesta 1 turno, igual que mover en recta. Eso significa que la métrica efectiva no puede ser la euclídea (L2). Es una métrica inducida por el movimiento: lo que cuesta es el número de turnos.

La métrica correcta es L∞ (Chebyshev): el coste lo marca la coordenada “más retrasada”. Es una forma elegante de decir: si puedes corregir x e y a la vez (diagonal), entonces lo que te limita es la mayor de las dos correcciones.

d_\infty\!\big((x,y),(x^\prime,y^\prime)\big):=\max\left(|x^\prime-x|,\ |y^\prime-y|\right)

Y ahora justificamos que d∞ coincide con la distancia de grafo del rey: una cota por debajo (no puedes corregir más de 1 por coordenada y turno) y una construcción por arriba (diagonales mientras se pueda, luego recta).

Lema 1 · Cota inferior

\begin{aligned} \text{En 1 paso:}\quad &|\Delta x|\le 1,\quad |\Delta y|\le 1\\ \text{En }t\text{ pasos:}\quad &|\Delta x|\le t,\quad |\Delta y|\le t\\ \Rightarrow\quad &t\ge \max\big(|\Delta x|,|\Delta y|\big)\\ \Rightarrow\quad &\operatorname{dist}_G(u,v)\ge d_\infty(u,v). \end{aligned}

Lema 2 · Cota superior

\begin{aligned} \text{Sea } m &:= \max\big(|\Delta x|,|\Delta y|\big).\\ \text{Construcción:}\quad &\text{(1) Reducir }\Delta x\text{ y }\Delta y\text{ simultáneamente (diagonales).}\\ &\text{(2) Corregir la coordenada restante (rectas).}\\ \Rightarrow\quad &\operatorname{dist}_G(u,v)\le m = d_\infty(u,v). \end{aligned}

Teorema 1 · Distancia del rey

\operatorname{dist}_G(u,v):=\min\{t\in\mathbb{N}:\exists\ \text{camino }u=v_0\sim v_1\sim\cdots\sim v_t=v\}

Traducción visual: lo alcanzable en t turnos bajo esta métrica es un cuadrado (L∞), no un círculo (L2). El “cuadrado” de la regla empieza a asomar.

Regla del cuadrado en un final rey contra peón — La “regla del cuadrado”: un test visual rápido de si el rey puede interceptar al peón antes de que corone.

Diagrama ASCII · Bola L∞ (cuadrado perfecto)

Aquí sí: una bola L∞ de radio 2 alrededor de la posición del rey es un bloque 5×5 centrado. Todo lo marcado con # está a ≤ 2 movimientos del rey.


B∞(K,2)  (cuadrado 5×5)

# # # # #
# # # # #
# # K # #
# # # # #
# # # # #

3 · El peón mete el tiempo en la ecuación

Hasta aquí el objetivo era fijo: “llegar a una casilla”. Pero el peón se mueve: es un objetivo móvil. En control/robótica esto es el típico problema de intercepción: persigues algo que avanza mientras tú te mueves.

Mini‑puente (cambio de problema): hasta ahora medíamos “cuántos turnos tarda el rey en llegar a una casilla fija”. Con el peón cambiamos de juego: el objetivo se mueve. Ya no basta con llegar a un sitio; hay que llegar cuando el peón esté allí. Eso es un problema de intercepción (persecución con reloj).

Usamos el modelo limpio detrás de la regla clásica: el peón avanza 1 por turno hacia la coronación, y no hay bloqueos. Definimos su trayectoria y el horizonte temporal.

Piensa en p_t como una función del tiempo: si le das un turno t, te devuelve la casilla del peón en ese turno. En el modelo “limpio” detrás de la regla clásica, el peón avanza recto una fila por turno (sin bloqueos, sin capturas diagonales), así que su x permanece constante y solo cambia y.

\begin{aligned} \mathbf{p}_0 &= (x_p,\ y_p),\\ \mathbf{p}_t &= (x_p,\ y_p+t),\\ n &:= 8-y_p,\qquad t\in\{0,\dots,n\}. \end{aligned}

n es el deadline: los turnos que quedan antes de que el peón llegue a y=8.

Dicho en lenguaje llano: si el peón está en la fila y_p, le faltan 8 − y_p avances para llegar a la octava y coronar, así que el problema solo “existe” durante esos n turnos. Después, el objetivo deja de ser el peón tal como lo hemos modelado.

4 · Intercepción = “existe t”

Esta frase es el puente entre el “truco visual” y la matemática: capturar significa que existe un instante t (antes del deadline) en el que el rey puede estar en la misma casilla que el peón.

\exists\, t\le n:\ \operatorname{dist}_G(\mathbf{k}_0,\mathbf{p}_t)\le t

Lectura en castellano de la fórmula: existe algún turno t (antes de que el peón corone) tal que el rey puede estar en la misma casilla que el peón en ese turno.

Ojo con el ≤ t: no significa “llegar exactamente en t”, sino “llegar como muy tarde en t”. Si el rey llega antes, puede esperar (quedarse en la misma casilla) hasta que el peón pase por allí. Por eso usamos ≤ y no =.

Y aquí usamos el Teorema 1: reemplazamos la distancia de grafo por L∞. Esto es justo lo que queríamos: transformar el problema en desigualdades explícitas.

Importante: aquí no estamos “aproximando” nada. En el punto 2 demostramos que para el rey dist_G(u,v) = d∞(u,v). Así que sustituir dist_G por d∞ es usar una identidad, no cambiar el problema.

(\text{Teorema }1)\ \Longleftrightarrow\ \exists\, t\le n:\ d_\infty(\mathbf{k}_0,\mathbf{p}_t)\le t

Analogía: cono de luz relativista discreto

Diagrama de cono de luz en espacio-tiempo de Minkowski — Cono causal (Minkowski): región alcanzable bajo un límite de propagación. El paralelo discreto del rey es la expansión de `Reach(k₀,t)` con el tiempo.

Si te gusta la física, aquí hay una imagen mental potente:

En relatividad, desde un evento (t=0) hay un cono de luz: el conjunto de puntos del espacio-tiempo que puedes alcanzar sin superar la velocidad de la luz.

Aquí pasa algo parecido, pero discreto: el “límite de velocidad” del rey es 1 casilla por turno (y puede hacerlo en diagonal). Desde la posición inicial k₀, el conjunto Reach(k₀,t) es su “frente causal” a tiempo t.

Si apilas las regiones alcanzables para t=0,1,2,3,... obtienes un cono causal discreto. Y el peón traza una línea (su worldline). Capturar = intersección entre worldline y cono.


Esquema (capas de alcanzabilidad):

t=0:            K
t=1:          ( 3×3 )
t=2:        ( 5×5 )
t=3:      ( 7×7 )
...

(worldline del peón = una columna que sube)
(intersección = captura)

Ejemplo concreto: cono de luz (Minkowski) y su paralelo “rey en el tablero”

Vamos a poner números para que la analogía deje de ser poesía y se vuelva mecánica. En un diagrama de Minkowski 1+1 (un eje de tiempo y uno de espacio), si tomas unidades con c = 1 (la luz recorre 1 unidad de espacio por 1 unidad de tiempo), entonces:

Un destello de luz emitido en el evento E₀ = (t=0, x=0) solo puede llegar a eventos (t, x) que cumplan |x| ≤ t.
Las fronteras del cono (la propia luz) son las rectas x = +t y x = −t.

Por ejemplo, el evento (t=3, x=2) está dentro del cono porque |2| ≤ 3. En cambio, (t=3, x=5) está fuera: requeriría una señal más rápida que la luz.


Cono de luz (1+1, c=1)

t
^
|        /
|       /   frontera: x = +t
|      /
|     •  (t=3,x=2)  dentro
|    /
|   /
|  /
| / 
|/______________> x
 \ 
  \   frontera: x = -t
   \
    • (t=3,x=5)  fuera (no permitido)

Ahora el paralelo discreto del rey es casi el mismo “tipo” de restricción, solo que con otra métrica: en cada turno, el rey puede cambiar x y y a lo sumo en 1 (incluida diagonal). Eso hace que el conjunto permitido tras t turnos sea:

\begin{aligned} \text{Desde }\mathbf{k}_0=(x_0,y_0)\text{, en }t\text{ turnos:}\quad &|x-x_0|\le t,\qquad |y-y_0|\le t\\ \Longleftrightarrow\quad &\max\big(|x-x_0|,\ |y-y_0|\big)\le t \qquad (\text{métrica }L_\infty). \end{aligned}

Visualmente: en Minkowski (con c=1) la sección a tiempo fijo es un intervalo (un “diamante” en 1+1); en el rey (con L∞) la sección a tiempo fijo es un cuadrado en el tablero. En ambos casos, la idea común es: hay un límite de propagación y la “captura” es una intersección entre una trayectoria (worldline) y una región alcanzable.

5 · De geometría a desigualdades

Ahora hacemos lo típico en ciencia aplicada: elegimos variables que capturen “lo que importa” y lo pasamos a álgebra. Aquí importan dos separaciones iniciales: horizontal y vertical.

Por eso aparecen valores absolutos: la dirección (izquierda/derecha, arriba/abajo) no importa; importa la magnitud.

\begin{aligned} \mathbf{k}_0 &= (x_k,\ y_k),\\ \mathbf{p}_0 &= (x_p,\ y_p),\\ a &:= |x_p-x_k|,\\ b &:= |y_p-y_k|. \end{aligned}

Los valores absolutos aparecen porque la desigualdad no necesita saber si el peón está “a la izquierda” o “a la derecha” del rey: solo importa cuántas columnas y filas los separan (magnitud, no dirección).

Sustituimos la trayectoria del peón p_t dentro de la métrica d∞. No hay truco: es una sustitución directa.

\begin{aligned} \mathbf{p}_t &= (x_p,\ y_p+t),\\ d_\infty(\mathbf{k}_0,\mathbf{p}_t) &= \max\big(a,\ |(y_p+t)-y_k|\big). \end{aligned}

Aquí se ve la mecánica del “objetivo móvil”: la separación horizontal a es fija (el peón no cambia de columna en este modelo), mientras que la separación vertical depende de t porque el peón sube una fila por turno. La métrica L∞ toma la peor de las dos: en cada turno, lo que te limita es la coordenada en la que vas más “atrasado”.

Y ya podemos escribir la condición de captura como una desigualdad explícita (nuestro objetivo desde el principio):

\max\big(a,\ |(y_p+t)-y_k|\big)\le t

Cómo leerla: en el turno t, el rey dispone de t movimientos; por tanto, puede corregir como máximo t columnas y t filas. La condición dice: “en ese turno, tanto la separación horizontal como la vertical (la peor de ambas) caben dentro del presupuesto t”. Si eso ocurre para algún t ≤ n, hay intercepción.

Este es el momento “ajá”: la ley del cuadrado no es un dibujo, es una condición de existencia de soluciones para una desigualdad.

6 · Ley del cuadrado (condición inicial)

La regla clásica dice: “si el rey está dentro del cuadrado, atrapa”. En este lenguaje significa: “si la distancia L∞ inicial del rey al peón es ≤ n”.

(\text{Teorema }1)\ \Longleftrightarrow\ \exists\, t\le n:\ d_\infty(\mathbf{k}_0,\mathbf{p}_t)\le t

Lo genial: el problema era espacio-tiempo (objetivo móvil), pero la respuesta queda como una condición inicial. Por eso es una regla mental tan rápida.

Demostración (esqueleto)

No exprimimos cada detalle fino de ajedrez (turno exacto, doble paso, etc.). Pero sí dejamos claro “de dónde sale”: (⇒) usa intercepción + desigualdad triangular; (⇐) usa alcanzabilidad + sincronización de un camino.

\begin{aligned} (\Rightarrow)\ &\exists\, t\le n:\ d_\infty(\mathbf{k}_0,\mathbf{p}_t)\le t.\\ &\mathbf{p}_t=(x_p,\ y_p+t),\quad d_\infty=\max(|\Delta x|,|\Delta y|).\\ &\Rightarrow\ |x_p-x_k|\le t,\qquad |(y_p+t)-y_k|\le t.\\ &\Rightarrow\ y_k\ge (y_p+t)-t = y_p.\\ &\Rightarrow\ |y_p-y_k|=y_k-y_p\le 8-y_p=n,\\ &\hspace{31pt}|x_p-x_k|\le t\le n.\\ &\Rightarrow\ d_\infty(\mathbf{k}_0,\mathbf{p}_0)=\max(|x_p-x_k|,|y_p-y_k|)\le n. \end{aligned}

\begin{aligned} (\Leftarrow)\ &d_\infty(\mathbf{k}_0,\mathbf{p}_0)\le n,\quad n=8-y_p.\\ &\operatorname{Reach}(\mathbf{k}_0,t)=\{v:\ d_\infty(\mathbf{k}_0,v)\le t\}\ \text{crece con }t.\\ &\text{Captura}\ \Longleftrightarrow\ \exists\, t\le n:\ d_\infty(\mathbf{k}_0,\mathbf{p}_t)\le t.\\ &\text{Con }a:=|x_p-x_k|\ \text{constante y } |y_p-y_k|\le n,\\ &\text{existe }t\le n\ \text{tal que }\max\big(a,\ |(y_p+t)-y_k|\big)\le t. \end{aligned}

7 · Por qué se dibuja un “cuadrado”

El cuadrado aparece porque la bola de radio n en L∞ es un cuadrado alineado con los ejes: “estar a distancia ≤ n” equivale a “ambas coordenadas están dentro de un margen n”.

B_\infty(\mathbf{p}_0,n)=\{(x,y): |x-x_p|\le n,\ |y-y_p|\le n\}

Eso es exactamente lo que la ley del cuadrado te pide dibujar sin decir “métrica” ni “grafo”: un bounding box de alcance en el espacio que realmente usa el rey.

Resumen de sofá: el rey vive en un “espacio” no euclídeo porque la diagonal no cuesta √2, cuesta 1 turno. Ese coste induce L∞, L∞ genera cuadrados, y perseguir un peón se convierte en un “existe t” que termina siendo una desigualdad inicial simple.

Y si te quedas con una imagen: el rey genera un “cono causal” discreto; el peón traza su worldline; la captura es su intersección. El cuadrado es solo la sección transversal de ese cono.

← ALL INSIGHTS HOME →