PROBLEMA DE LAS 8 REINAS (AJEDREZ)

Dando color a los gráficos de la reina

El n×n reina gráfico tiene los cuadrados de n×n tablero de ajedrez de sus vértices y dos vértices son adyacentes si y sólo si, las reinas puestos en las dos plazas se atacan mutuamente.

La prueba es sencilla: Cuando el tablero de ajedrez es considerado como el cuadrado cartesiano de {0,1,...,n-1} , color de vértice (i,j) por el (j-2i) mod n . Esta construcción se ilustra a continuación el n=5 y n=7 . 

0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1

0 1 2 3 4 5 6 5 6 0 1 2 3 4 3 4 5 6 0 1 2 1 2 3 4 5 6 0 6 0 1 2 3 4 5 4 5 6 0 1 2 3 2 3 4 5 6 0 1

Verificar que (siempre que n mod 6 es 1 o 5 ) que no hay dos vértices del mismo color son adyacentes es un ejercicio de rutina, pero aquí están los detalles de todos modos.

Considere la posibilidad de vértices (i,j) y (x,y) del mismo color. Por definición,

(*) 2(xi) es congruente con (yj) mod n .

Si los dos vértices están en la misma fila (x=i) , entonces (*) implica y=j . Si los dos vértices están en la misma columna (y=j) , entonces (*) implica x=i desde n es impar. Si los dos vértices están en la misma diagonal, entonces xi=yj o xi=jy , en el primer caso, (*) implica (x,y)=(i,j) , en este último caso, (*) implica (x,y)=(i,j) desde el 3 no divide n .

El mismo argumento (con el "xi=yj o xi=jy" reemplazado por xi es congruente con yj mod n o xi es congruente con jy mod n), muestra que el color funciona incluso a las reinas mas poderosas, que se mueven en diagonal envolviendo el contorno del tablero de ajedrez.