Clase 48 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
N-Queens
El rompecabezas de n reinas es el problema de colocar n reinas en un tablero de ajedrez de n x n de manera que ninguna de ellas se ataque mutuamente. Dado un número entero n, devuelva todas las soluciones distintas del rompecabezas de n reinas. Puede devolver la respuesta en cualquier orden. Cada solución contiene una configuración del tablero distinta de la colocación de n reinas, donde "Q" y "." indican una reina y un espacio vacío, respectivamente.
Ejemplo 1:
Entrada: n = 4 Salida: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explicación: Existen dos soluciones distintas al rompecabezas de las 4 reinas como se muestra arriba
Solución
def solveNQueens(self, n: int) -> List[List[str]]: res = [] self.dfs([-1]*n, 0, [], res) return res def dfs(self, numeros, apuntador, construccionActual, res): if apuntador == len(numeros): res.append(construccionActual) return for i in range(len(numeros)): numeros[apuntador] = i if self.valid(numeros, apuntador): tmp = "."*len(numeros) self.dfs(numeros, apuntador+1, construccionActual+[tmp[:i]+"Q"+tmp[i+1:]], res) def valid(self, numeros, apuntador): for i in range(apuntador): if abs(numeros[i]-numeros[apuntador]) == apuntador - i or numeros[i] == numeros[apuntador]: return False return True
Carlos Hernandez
Diego Portillo
Mi solución:
def check_valid_board(board, queens, n): DIRECTIONS = [(1, 1), (1, -1), (-1, 1), (-1, -1)] for queen in queens: for direction in DIRECTIONS: i, j = queen offset_i, offset_j = direction while True: i += offset_i j += offset_j if i < 0 or i >= n or j < 0 or j >= n: break if board[i][j] == 'Q': return False return True def append_queen_to_board(i, combinations, taken_columns, queens, n, current_board): if len(queens) == n: splitted_board = current_board.split("|") if check_valid_board(splitted_board, queens, n): combinations.append(splitted_board) return current_board += '|' for index in range(n): if index not in taken_columns: current_combination = '.' * index + 'Q' + '.' * (n - index - 1) append_queen_to_board(i + 1, combinations, taken_columns + [index], queens + [(i + 1, index)], n, current_board + current_combination) def n_queens(n): combinations = [] taken_columns = [] queens = [] for i in range(n): current_board = '.' * i + 'Q' + '.' * (n - i - 1) append_queen_to_board(0, combinations, taken_columns + [i], queens + [(0, i)], n, current_board) return combinations
input_1 = 4 output_1 = [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] def position_queens(n, current_list, boards): if len(current_list) == n: base_string = "." * n board = [] for column_index in current_list: board.append(base_string[:column_index] + 'Q' + base_string[column_index+1:]) boards.append(board) return for index in range(n): row = len(current_list) column = index has_diagonal = False for prev_row, prev_column in enumerate(current_list): if abs(row - prev_row) == abs(column - prev_column): has_diagonal = True if column not in current_list and has_diagonal is False: current_list.append(column) position_queens(n, current_list, boards) current_list.remove(column) def n_queens(n): boards = [] position_queens(n,[],boards) return boards print(n_queens(input_1)) print(n_queens(input_1) == output_1)
