Aplicació: Les n reines

Com aplicació de les tècniques de generació exhaustiva, aquesta lliçó mostra com resoldre el famós trencaclosques de les vuit reines.

El problema

Recordeu que al joc dels escacs les reines amenacen en horitzontal, vertical i diagonal:

Podeu col·locar vuit reines en un tauler d’escacs sense que cap reina amenaci cap altra?

Aquí en teniu una possible solució (i, en total, n’hi ha 92):

A continuació, anem a fer un programa per resoldre una versió generalitzada del trencaclosques: donat un valor n, volem escriure totes les maneres de col·locar n reines en un tauler d’n⨉n escacs. Per exemple, aquestes serien les dues úniques possibles col·locacions de 4 reines en un tauler 4⨉4:

· ♕ · · 
· · · ♕ 
♕ · · · 
· · ♕ · 

· · ♕ · 
♕ · · · 
· · · ♕ 
· ♕ · ·

Cal doncs posar n reines en un tauler n⨉n de forma que cap parell de reines es trobin:

Espai de cerca

Per fer el programa, realitzarem una cerca exhaustiva en l’espai de possibles configuracions. Cada configuració consisteix en la col·locació de reines en posicions del tauler.

Per a un tauler 8⨉8, aquest espai de cerca és enorme:

Però, descartant solucions on ja hi hagi amenaces, ho podem fer encara millor! Es tracta de fer que la cerca sigui exhaustiva, però sense perdre el temps en configuracions que no portin enlloc.

Representació

Una manera concisa de representar una solució és donar la columna de cada reina en cada fila. Per exemple, la solució

· · ♕ · · · · ·
· · · · · · ♕ · 
· · · ♕ · · · · 
· ♕ · · · · · ·
· · · · · · · ♕
· · · · ♕ · · · 
· · · · · · ♕ · 
♕ · · · · · · ·

es pot representar amb la llista [7, 3, 0, 2, 5, 1, 6, 4] (comencem a comptar des de zero).

Una solució parcial correspon a la col·locació d’un subconjunt de reines en les primeres columnes. Podem representar solucions parcial restringint els valors de la llista a unes quantes posicions inicials. Així, les primeres 5 posicions de la llista [7, 3, 0, 2, 1, 2, 3, 4] representen la solució parcial

· · ♕ · · · · ·
· · · · ♕ · · · 
· · · ♕ · · · · 
· ♕ · · · · · ·
· · · · · · · ·
· · · · · · · · 
· · · · · · · · 
♕ · · · · · · ·

i les darreres 3 posicions són irrellevants.

Representarem les solucions parcials amb el tipus SolParcial:

SolParcial: TypeAlias = list[int]

Les solucions parcials sense amenaces entre parells de reines s’anomenen solucions legals. Una solució és una solució parcial amb les n reines col·locades.

Algorisme

L’algorisme procedirà a buscar solucions parcials legals, tot intentant omplir el tauler progressivament, per files de dalt a baix. Per cada fila, es provarà de mirar si es pot col·locar legalment una reina a cadascuna de les seves n posicions (files), una rere l’altra. En cas afirmatiu, aquella reina es col·locarà en aquella columna i fila i es provarà d’estendre la solució parcial. Si en algun moment es troba una solució parcial amb totes les n reines col·locades, s’escriu la solució. Altrament, es tira enrere traient la darrera reina col·locada i provant una altra posició per a ella. Si no li queden més columnes, anirà enrere, fent el mateix per la fila anterior.

Comencem amb la funció principal cridant a la funció recursiva amb una solució parcial amb zero reines col·locades:

def genera_reines(n: int) -> None:
    """Escriu totes les maneres de col·locar n reines en un tauler n⨉n."""

    s: SolParcial = [-1 for _ in range(n)]  # els valors són irrellevants, la llargada no.
    genera_reines_rec(n, s, 0)

La funció recursiva rep el valor d’n i la solució parcial, que és una llista s d’n posicions on només les i primeres tenen un valor rellevant. El seu propòsit és escriure totes les solucions que estenen la solució parcial donada:

def genera_reines_rec(n: int, s: SolParcial, i: int) -> None:
    """
    Escriu totes les maneres de col·locar n reines en un tauler n⨉n
    de forma que les i primeres reines es col·loquen a les primeres i
    posicions de s. Aquestes primeres i posicions són una solució parcial legal.
    """

    if i == n:
        escriure_reines(s)
    else:
        for j in range(n):
            if legal(s, i, j):
                s[i] = j
                genera_reines_rec(n, s, i+1)

El seu funcionament és com segueix:

La funció legal comprova si es pot col·locar una reina a la fila i i a la columna j per a la solució parcial s fins a la posició i. La reina a la fila i i columna j amenaça a una reina a la fila k si comparteixen:

Aquesta és la implementació corresponent:

def legal(s: SolParcial, i: int, j: int) -> bool:
    """Indica si és legal col·locar una reina a la fila i i columna j per a a solució parcial s."""

    for k in range(i):
        if j == s[k] or j - i == s[k] - k or j + i == s[k] + k:
            return False
    return True

La funció escriure_reines és purament cosmètica:

def escriure_reines(s: SolParcial) -> None:
    """Escriu en format tauler la solució emmagatzemada en s."""

    for p in s:
        print('· ' * p, '♕ ', '· ' * (len(s) - p - 1), sep='')
    print()

Aquest és el programa complet:

from typing import TypeAlias
from yogi import read


SolParcial: TypeAlias = list[int]


def escriure_reines(s: SolParcial) -> None:
    """Escriu en format tauler la solució emmagatzemada en s."""

    for p in s:
        print('· ' * p, '♕ ', '· ' * (len(s) - p - 1), sep='')
    print()


def legal(s: SolParcial, i: int, j: int) -> bool:
    """Indica si és legal col·locar una reina a la fila i i columna j per a a solució parcial s."""

    for k in range(i):
        if j == s[k] or j - i == s[k] - k or j + i == s[k] + k:
            return False
    return True


def genera_reines_rec(n: int, s: SolParcial, i: int) -> None:
    """
    Escriu totes les maneres de col·locar n reines en un tauler n⨉n
    de forma que les i primeres reines es col·loquen a les primeres i
    posicions de s. Aquestes primeres i posicions són una solució parcial legal.
    """

    if i == n:
        escriure_reines(s)
    else:
        for j in range(n):
            if legal(s, i, j):
                s[i] = j
                genera_reines_rec(n, s, i+1)


def genera_reines(n: int) -> None:
    """Escriu totes les maneres de col·locar n reines en un tauler n⨉n."""

    s: SolParcial = [-1 for _ in range(n)]  # els valors són irrellevants, la llargada no.
    genera_reines_rec(n, s, 0)


if name == '__main__':
    genera_reines(read(int))

Exercicis

Ús de marcatges

🚧 Falta fer




Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2022

Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.