Resolviendo un rompecabezas de búsqueda universitaria usando Python / Sudo Null IT News

En blanco y negro – uno de los acertijos interesantes del juego Búsqueda de rompecabezas Universidad de Melbourne 2010. En la trama del juego, persigues a un misterioso participante de un programa de televisión con la esperanza de revelar su identidad. Consigues entrar primero al estudio y luego a su camerino. Allí, entre su ropa, encuentras un trozo de papel. Uno de sus lados está ocupado por un mensaje, el otro por un rompecabezas y un conjunto de instrucciones para ello.

“Organiza cada uno de los cuadros a continuación en tiras de 1×1, 1×2 o 1×3 para que ninguna cuadrícula contenga tiras con el mismo patrón en blanco y negro, incluidas las rotaciones”.

El rompecabezas consta de 25 campos cuadrados dispuestos en 5 filas y 5 columnas. A su vez, cada campo se divide en 25 celdas mediante líneas horizontales y verticales. Las celdas tienen un fondo blanco o negro y cada una de ellas contiene una letra.

Primero, determinemos qué tiras podemos utilizar para solucionar este problema. Hay 6 tiras diferentes de 1×3 (WWW, WWB, WBW, WBB, BWB y BBB), 3 tiras diferentes de 1×2 (WW, WB y BB) y 2 tiras diferentes de 1×1 (W y B). En total, todas estas tiras contienen 26 celdas. Esto significa que para descomponer cada campo tendrás que utilizar todas las tiras de 1×3, todas las tiras de 1×2 y solo una de las tiras de 1×1. Dado que la ubicación de la tira de 1 celda se deriva de la ubicación de las 9 tiras restantes, se puede ignorar durante la descomposición. Por lo tanto, el problema se puede reformular de la siguiente manera: es necesario colocar en cada campo 6 tiras únicas de tamaño 1×3 y 3 tiras únicas de tamaño 1×2 para que los colores de las celdas del campo y los colores de las celdas de las rayas coincidir. Intentemos resolver este problema usando Python.

Representemos franjas usando una tupla de líneas en orden aleatorio, donde los caracteres de cada línea indicarán los colores de las celdas correspondientes de la franja ('w' o 'b').

# strips for the puzzle            
strips = ('ww','wb','bb','www','wwb','wbw','wbb','bwb','bbb')

Imaginemos cada campo como una tupla de cadenas, cada una de las cuales representará una fila del campo. En este caso, los símbolos de las filas representarán los colores de las celdas correspondientes.

# grids for the puzzle
grid01 = ('bwbww','bwbbb','wbwbw','bwwbw','bwwbb')
grid02 = ('bwbwb','bwbwb','wbwbw','wwbbb','wbbww')
grid03 = ('wwwbw','bbwww','bbbww','wwbbw','bbwbb')
grid04 = ('wwbbw','wbwbb','bwwwb','wwbbw','bbbwb')
grid05 = ('wwwwb','bbbbw','bbwbb','bwwbb','wwwwb')
grid06 = ('wbwwb','bwwbw','bbbbb','wwwbw','bwbww')
grid07 = ('wbwww','wwbbw','wbbbw','bbbbw','wbbww')
grid08 = ('wbbww','wwwbb','bwbww','bwbwb','bbwwb')
grid09 = ('bbbww','wwbww','wbbww','bwwwb','bbwbb')
grid10 = ('wwbbb','wbbbb','wbbwb','bwbww','bwwww')
grid11 = ('wwwww','bbbbb','wwbbw','wwbbb','bbbww')
grid12 = ('bbbbb','wwbwb','wwwwb','wwbwb','wwbwb')
grid13 = ('bwbwb','wwwbb','bwbwb','bwbbw','wwbwb')
grid14 = ('wbwwb','wbwbb','wwbbb','wwbbb','wwbbw')
grid15 = ('wwbbw','wwbww','bbbww','bbbww','bbwbw')
grid16 = ('wbwbw','wbwww','bbbbb','bwwww','bwbwb')
grid17 = ('wwwwb','wwwww','bbbbw','bbbwb','bwbbb')
grid18 = ('wbbww','bwwbb','bwwwb','bbbwb','wbwwb')
grid19 = ('bwwbw','wbwww','bwbwb','bwwbw','bbbbw')
grid20 = ('wbbwb','bbwbw','wwwwb','wbbbb','wwbwb')
grid21 = ('bbbwb','bbwbw','wbbww','bbwwb','wwbww')
grid22 = ('wwbbw','wbbbw','bwwwb','bwbbb','bwbww')
grid23 = ('wbwww','wwbwb','bbwww','wbwbb','bbbwb')
grid24 = ('bwwbb','wwwww','bwwww','bbbbb','wwbbb')
grid25 = ('wwwww','bbbww','bbbbw','bwbww','wwbbb')

También reuniremos todos los campos en una tupla.

# given grids together as a tuple
grids = (grid01,grid02,grid03,grid04,grid05,
         grid06,grid07,grid08,grid09,grid10,
         grid11,grid12,grid13,grid14,grid15,
         grid16,grid17,grid18,grid19,grid20,
         grid21,grid22,grid23,grid24,grid25)

Para mayor claridad, convertiremos la solución de cada campo en un esquema simple que consta de barras verticales, guiones bajos y espacios. Además, durante la salida colocaremos varios diagramas en un nivel horizontal para que el resultado corresponda a la ubicación de los campos en la tarea. Proporcionemos un parámetro que indicará la cantidad de soluciones en un nivel durante la salida y lo estableceremos en cinco.

# number of outlines of placings in one row for the output
outlines_per_row = 5

El programa comenzará con la función solve_grids.

def solve_grids(grids, strips, outlines_per_row):
    """Function for solving grids for puzzle Black and White
       from MUMS Puzzle Hunt 2010 competition."""
    first_grid = grids(0)
    num_rows = len(first_grid)
    num_cols = len(first_grid(0))
    # sorting strips according to length in decreasing order
    # to make the problem easier
    strips = tuple(sorted(strips,key = len,reverse = True))
    outlines = ()
    for grid_values in grids:
        # represent the grid as a dictionary for search
        grid = {}
        for row in range(num_rows):
            for col in range(num_cols):
                grid((col,row)) = grid_values(row)(col)
        # try to find placing with depth-first search
        placing = depth_first_search(grid, num_cols, num_rows, strips,(), ())
        if placing:
            # form outline of a placing
            outline = get_placing_outline(placing, num_cols, num_rows)
            outlines += (outline,)
        else:
            return False
    # combine outlines
    output = get_output(outlines, outlines_per_row)
    return output

Sus datos de entrada son: una tupla de campos, una tupla de franjas y también un parámetro de salida. Para descomponer cada campo, el programa irá colocando rayas en él de acuerdo con su orden en la tupla; Por tanto, antes de iniciar la búsqueda, tiene sentido ordenar las tiras según su longitud en orden descendente. Como resultado, la búsqueda considerará menos opciones potenciales en el camino hacia una solución, lo que simplificará enormemente la tarea. Para la búsqueda será conveniente representar cada campo como un diccionario, en el que las claves serán tuplas de dos números que indican el número de columna y el número de fila de la celda, y los valores serán cadenas de un carácter que indican el color. de la celda dada ('w' o 'b'). Para cada campo de la tupla, la función genera dicha representación y luego ejecuta una búsqueda en profundidad con ella. La solución encontrada luego se convierte en un circuito que se agregará a la tupla general. Una vez completado este proceso, la función organiza los diagramas en niveles y devuelve el resultado.

Veamos ahora la función de búsqueda en profundidad.

def depth_first_search(grid, num_cols, num_rows, strips, occupied_cells, placing):
    """Function that perform depth-first search to place the strips on the grid."""
    if strips == ():
        # all strips are placed
        return placing
    # current strip of search
    current_strip = strips(0)
    # strips for further search
    next_strips = strips(1:)
    # position is used for search, representation is used for answer
    for (position,representation) in get_strip_positions(current_strip, num_cols, num_rows):
        position_is_possible = True
        # check that position is possible
        for cell in position:
            if position(cell) != grid(cell) or cell in occupied_cells:
                position_is_possible = False
                break
        if position_is_possible:
            next_occupied_cells = occupied_cells                        
            for cell in position:
                next_occupied_cells += (cell,)
            next_placing = placing + (representation,)
            final_placing = depth_first_search(grid, num_cols, num_rows, next_strips, next_occupied_cells, next_placing)
            if final_placing:
                return final_placing
    return False

Esta función primero verifica si la tupla de franjas está vacía. Si este es el caso, entonces ya se han colocado todas las rayas, y solo queda devolver el arreglo resultante. De lo contrario, la función intenta colocar la primera franja de la tupla en el campo y luego, si tiene éxito, pasa la tupla de las franjas restantes a la siguiente llamada. Las posibles posiciones de la tira se generan utilizando la función get_strip_positions. Esta función devuelve un generador que proporcionará posiciones según sea necesario; cada uno de ellos se representará de dos formas diferentes mediante una tupla de dos elementos. La primera representación se utiliza para buscar: es un diccionario, donde las claves son tuplas de dos números, que indican la ubicación de las celdas de la franja en el campo, y los valores son cadenas de un carácter, que indican los colores de la franja. celdas ('w' o 'b'). La segunda representación se utilizará para generar una respuesta al problema, ya que es más conveniente para la derivación posterior de la solución. Esta representación es una tupla de 3 elementos: el primer elemento denota la celda inferior izquierda de la tira en una posición determinada como una tupla de 2 números; el segundo elemento representa la orientación de la franja como una línea (“horizontal” o “vertical”); el tercer elemento indica la longitud de la tira como un número. La función utiliza la primera representación para comprobar que los colores de las celdas de la franja coincidan con los colores de las celdas del campo en una posición determinada, y también para asegurarse de que las celdas correspondientes del campo no estén ocupadas por otras franjas. Si la posición es posible, entonces la función completa la tupla de celdas ocupadas del campo, agrega una segunda representación de la franja a la solución y continúa la búsqueda con nuevos datos.

Veamos ahora la función get_strip_positions.

def get_strip_positions(strip, num_cols, num_rows):
    """Function that generate possible positions for the given strip
       according to the number of columns and rows in the grid."""
    strip_len = len(strip)
    # we should also consider reversed strip,
    # if it is different from the original one
    reversed_strip = strip(::-1)
    if strip == reversed_strip:
        patterns = (strip,)
    else:
        patterns = (strip, reversed_strip)
    # generate horizontal placings of the strip 
    for row in range(num_rows):
        for col in range(num_cols - strip_len + 1):
            for pattern in patterns:
                position = {}
                current_col = col
                for colour in pattern:
                    position((current_col, row)) = colour
                    current_col += 1
                yield (position, ((col,row),'horizontal',strip_len))
    # generate vertical placings of the strip 
    for col in range(num_cols):
        for row in range(num_rows - strip_len + 1):
            for pattern in patterns:
                position = {}
                current_row = row
                for colour in pattern:
                    position((col, current_row)) = colour
                    current_row += 1
                yield (position, ((col,row),'vertical',strip_len))

En primer lugar, “despliega” la tira 180 grados y comprueba si el resultado coincide con la versión original. Si este no es el caso, entonces se deben considerar más a fondo ambas opciones de ubicación. Primero, la función genera todas las posiciones horizontales posibles de la franja, considerando las líneas de campo por turno, luego las verticales, mirando por turno las columnas de campo.

Una vez que se encuentra una solución, la función solve_grids la pasa a la función get_placing_outline para generar el diseño de la tira para la salida.

def get_placing_outline(placing, num_cols, num_rows):
    """Function that creates outline of the placing for output
       that consists of bars, underscores and spaces."""
    cells_without_left_border = ()
    cells_without_lower_border = ()
    for strip in placing:
        first_cell = strip(0)
        col,row = first_cell(0),first_cell(1)
        orientation = strip(1)
        strip_len = strip(2)
        if orientation == 'horizontal':
            for strip_index in range(1, strip_len):
                cells_without_left_border += ((col + strip_index, row),)
        elif orientation == 'vertical':
            for strip_index in range(1, strip_len):
                cells_without_lower_border += ((col, row + strip_index),)
    outline = ()
    # decremental loop for rows with one additional row for the upper border of the grid
    for row in range(num_rows,-1,-1):
        level=""
        # loop for cols with one additional col for the right border of the grid
        for col in range(num_cols+1):
            cell = (col,row)
            if row < num_rows and (col == 0 or col == num_cols or not cell in cells_without_left_border):
                level += '|'
            else:
                level += ' '
            if col < num_cols:
                if row == 0 or row == num_rows or not cell in cells_without_lower_border:
                    level += '_'
                else:
                    level += ' '
        outline.append(level)
    return outline

Primero, esta función extrae de la solución todas las celdas del campo cuyo lado izquierdo no es el límite de ninguna franja, y todas las celdas del campo cuyo lado inferior no es el límite de ninguna franja. Luego, la función utiliza barras horizontales, guiones bajos y espacios para crear un diagrama de solución como una lista de cadenas, cada una de las cuales representa un nivel del diagrama. Debe considerar una fila adicional para mostrar el borde superior del campo y una columna adicional para mostrar el borde derecho del campo.

El esquema de cada solución se agrega a una tupla común, que luego se pasa a la función get_output, que genera el resultado final.

def get_output(outlines, outlines_per_row):
    """Function that combines outlines to create output
       with outlines_per_row outlines in one row."""
    outlines_len = len(outlines)
    output=""
    # determine starting index for every row
    for first_index in range(0, outlines_len, outlines_per_row):
        last_index = min(first_index + outlines_per_row, outlines_len)
        # add first outline to the row
        one_row = outlines(first_index)
        # add other outlines to the row
        for current_outline in outlines(first_index+1:last_index):
            level_index = 0
            for level in current_outline:
                one_row(level_index) += ' ' + level
                level_index += 1
        for level in one_row:
            output += level + '\n'
    return output

Esta función combina los mapas de decisión para cada nivel de salida horizontal en una lista. Inicialmente, cada nivel de salida es simplemente el primer circuito de ese nivel. Los circuitos posteriores se agregan a la lista nivel por nivel, seguidos de un espacio. Una vez que se genera el nivel de salida, se convierte en una cadena con nuevas líneas agregadas.

Ahora solo queda agregar comandos al programa para descomponer los campos indicados en la tarea y mostrar esquemas para su solución.

if __name__ == '__main__':
    # solve the given grids for the puzzle
    answer = solve_grids(grids, strips, outlines_per_row)
    print(answer)

El resultado del programa se puede ver a continuación.

 _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _ 
| | | |_ _| | |_ _|_ _| | |_ _ _| | |_ _ _| | | |_ _ _|_ _|
| | | | | | | | |_ _ _| |_|_ _ _| | |_ _ _|_| | | |_ _ _|_|
|_|_|_| |_| |_| | | | | |_ _ _|_|_| |_|_ _ _|_| | | | | | |
|_ _ _|_| | |_|_|_| | | |_ _|_ _ _| |_ _ _|_ _| |_|_| | | |
|_|_ _ _|_| |_ _ _|_|_| |_ _|_ _ _| |_ _|_ _ _| |_ _|_|_|_|
 _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _ 
|_ _ _|_ _| | | |_ _ _| | | |_ _ _| | | |_ _ _| | |_ _ _| |
|_ _ _| | | | |_| |_ _| | |_|_ _ _| |_| |_ _ _| | |_ _ _|_|
| |_ _| | | |_| | | | | |_|_ _ _|_| | |_|_ _| | |_|_|_ _ _|
| | |_|_|_| | | |_| | | |_ _ _|_ _| |_|_ _ _| | |_ _|_ _ _|
|_|_|_ _ _| |_|_|_|_|_| |_ _ _|_ _| |_ _ _|_|_| |_ _ _|_ _|
 _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _ 
|_ _ _|_ _| | |_|_ _ _| |_ _ _|_ _| |_ _ _| | | | |_ _ _|_|
|_ _ _|_| | | |_ _ _| | | | |_ _ _| | | | | | | | | |_ _ _|
| |_ _ _| | |_| | | | | |_|_|_| | | | |_|_|_|_| |_|_|_ _| |
| | |_ _|_| | | | |_|_| |_ _ _| | | |_|_ _ _|_| | |_ _ _| |
|_|_|_ _ _| |_|_|_|_ _| |_ _ _|_|_| |_ _ _|_ _| |_|_ _ _|_|
 _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _ 
| |_ _ _| | |_ _ _|_| | |_ _ _|_ _| |_ _ _| | | |_ _|_ _ _|
|_| |_ _|_| |_ _ _| | | | |_|_ _ _| | | |_|_|_| | |_ _ _| |
| | |_ _ _| | |_ _| |_| | |_ _ _| | | | |_ _ _| | |_ _ _|_|
| |_|_ _ _| | |_ _|_| | |_|_ _ _|_| |_|_|_ _ _| |_|_|_ _ _|
|_|_ _ _|_| |_|_ _ _|_| |_ _ _|_ _| |_ _|_ _ _| |_ _ _|_ _|
 _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _   _ _ _ _ _ 
|_ _ _| | | | | |_| | | |_ _ _| | | | | |_ _ _| |_|_ _ _| |
|_ _| | |_| | | | | | | |_| | | | | |_| |_ _| | |_ _ _| | |
| | | |_| | |_|_| |_|_| | |_|_|_|_| | |_|_ _| | |_ _ _| |_|
| | |_|_|_| |_ _|_| | | | | |_ _ _| | |_ _ _|_| | |_ _|_| |
|_|_|_ _ _| |_ _ _|_|_| |_|_|_ _ _| |_|_|_ _ _| |_|_ _ _|_|

Los esquemas de solución resultantes ahora deben superponerse a las imágenes originales.

Se debe prestar atención a las franjas de una celda para cada solución. Las letras de estas celdas, en conjunto, suman el mensaje: “UNA CUADRÍCULA MÁS. USAR TIRAS NEGRAS” (OTRO CAMPO. USAR TIRAS NEGRAS). En este caso, cada franja de 1 celda ocupa una posición única. Así, a partir de estas celdas podrás crear otro campo de 5×5 sin espacios ni superposiciones.

Creemos una representación de este campo.

# final grid for the puzzle
final_grid = ('bwwww','bbwbb','bbbww','wbwbb','wwbbw')

Agreguemos comandos al programa para descomponerlo y generar un diagrama de solución.

if __name__ == '__main__':
    # solve the final grid for the puzzle
    answer = solve_grids((final_grid,), strips, outlines_per_row)
    print(answer)

El resultado de su ejecución se puede ver a continuación.

 _ _ _ _ _ 
|_ _|_ _ _|
|_ _ _|_ _|
| |_|_ _ _|
| |_ _ _| |
|_|_ _ _|_|

A continuación, superpongamos el diagrama a la imagen original (el borde izquierdo de la celda con la letra T es incorrecto, las letras B y L deben intercambiarse).

Según la sugerencia, debes prestar atención a las rayas que consisten únicamente en celdas negras. Las letras dentro de estas franjas forman la palabra DOMINO. Es respuesta en asignación.