import numpy as np import copy import sys from itertools import permutations import os from collections import deque import time import heapq class Island: def __init__(self, row, col, is_island, value, bridges): self.row = row self.col = col self.is_island = is_island self.value = value self.bridges = bridges def __lt__(self, other): return self.value > other.value def find_solution(board, viable_moves): moves = [] bad_moves = [] board_states = [] for perm in permutations(viable_moves): board_copy = copy.deepcopy(board) move_queue = deque(perm) for move in move_queue: island1, island2 = move valid = perform_move(board_copy, island1.row, island1.col, island2.row, island2.col) if valid: moves.append([island1.row, island1.col, island2.row, island2.col]) else: bad_moves.append((island1, island2)) if is_winner(board_copy): return moves if bad_moves: for island1, island2 in bad_moves: valid = perform_move(board_copy, island1.row, island1.col, island2.row, island2.col) if valid: moves.append([island1.row, island1.col, island2.row, island2.col]) if is_winner(board_copy): return moves else: print_board(board_copy) board_states.append(board_copy) moves.clear() sys.exit(0) return None def is_winner(board): rows, cols = board.shape islands = [board[i, j] for i in range(rows) for j in range(cols) if board[i, j].is_island] return all(isl.bridges == isl.value for isl in islands) def create_board(file_path): # Read puzzle file: blank spots as '.', islands as digits or 'a'/'b'/'c' for 10/11/12 with open(file_path, 'r') as f: n, m = map(int, f.readline().split(',')) temp = [] mapping = {'a': 10, 'b': 11, 'c': 12} for i in range(n): line = f.readline().strip() chars = list(line) row = [] for j, ch in enumerate(chars): if ch == '.': row.append(Island(i, j, False, '.', 0)) else: if ch.isdigit(): val = int(ch) elif ch in mapping: val = mapping[ch] else: raise ValueError(f"Invalid character in board: {ch}") row.append(Island(i, j, True, val, 0)) temp.append(row) # Expand grid for bridge placement expanded = [] for i in range(n): expanded.append(temp[i]) for j in range(m): if i < n - 1 and temp[i][j].is_island and temp[i+1][j].is_island: gap_row = [Island(i, j, False, '.', 0) for _ in range(len(temp[0]))] expanded.append(gap_row) break for i in range(len(expanded)): for j in range(len(expanded[i])): if j < len(expanded[i]) - 1 and expanded[i][j].is_island and expanded[i][j+1].is_island: for k in range(len(expanded)): expanded[k].insert(j+1, Island(i, j, False, '.', 0)) break board = np.array(expanded) update_positions(board) return board def connect_islands(board, island1, island2, is_human=False): # Prevent exceeding allowed bridges for isl in (island1, island2): if isl.bridges == isl.value: if is_human: print("Maximum number of bridges reached") return # Horizontal if island1.row == island2.row: row = island1.row step = 1 if island1.col < island2.col else -1 start = island1.col + step end = island2.col if board[row, start].bridges == 2: if is_human: print("Already two bridges") return for c in range(start, end, step): if board[row, c].bridges % 2 == 0: board[row, c].bridges = 1 board[row, c].value = '-' else: board[row, c].bridges = 2 board[row, c].value = '=' # Vertical if island1.col == island2.col: col = island1.col step = 1 if island1.row < island2.row else -1 start = island1.row + step end = island2.row if board[start, col].bridges == 2: if is_human: print("Already two bridges") return for r in range(start, end, step): if board[r, col].bridges % 2 == 0: board[r, col].bridges = 1 board[r, col].value = '|' else: board[r, col].bridges = 2 board[r, col].value = '║' island1.bridges += 1 island2.bridges += 1 def check_islands(board, island1, island2, is_human=False): # Ensure no other island between two if island1.row == island2.row: step = 1 if island1.col < island2.col else -1 for c in range(island1.col + step, island2.col, step): if board[island1.row, c].is_island: if is_human: print("Island in the way") return False return True if island1.col == island2.col: step = 1 if island1.row < island2.row else -1 for r in range(island1.row + step, island2.row, step): if board[r, island1.col].is_island: if is_human: print("Island in the way") return False return True if is_human: print("Cannot connect these islands") return False def update_positions(board): rows, cols = board.shape for i in range(rows): for j in range(cols): board[i, j].row = i board[i, j].col = j def validate_row(board, island1, island2, bridges): step = 1 if island1.col < island2.col else -1 symbol = '-' if bridges == 1 else '.' for c in range(island1.col + step, island2.col, step): if board[island1.row, c].value != symbol: return False return True def validate_col(board, island1, island2, bridges): step = 1 if island1.row < island2.row else -1 symbol = '|' if bridges == 1 else '.' for r in range(island1.row + step, island2.row, step): if board[r, island1.col].value != symbol: return False return True def perform_move(board, row1, col1, row2, col2): valid = False cell1 = board[row1, col1] cell2 = board[row2, col2] if cell1.is_island and cell2.is_island: if check_islands(board, cell1, cell2): # Next cell determines existing bridges if cell1.row == cell2.row: next_cell = board[cell1.row, cell1.col + (1 if cell1.col < cell2.col else -1)] valid = validate_row(board, cell1, cell2, next_cell.bridges) else: next_cell = board[cell1.row + (1 if cell1.row < cell2.row else -1), cell1.col] valid = validate_col(board, cell1, cell2, next_cell.bridges) if valid: connect_islands(board, cell1, cell2) return valid def print_board(board): os.system('clear') rows, cols = board.shape for i in range(rows): for j in range(cols): print(f" {board[i, j].value} ", end="") print() time.sleep(1) def move(board, row1, col1, row2, col2, is_human=False): if board[row1, col1].is_island and board[row2, col2].is_island: if check_islands(board, board[row1, col1], board[row2, col2], is_human): if perform_move(board, row1, col1, row2, col2): connect_islands(board, board[row1, col1], board[row2, col2], is_human) else: print("No island at given coordinates") def automatic(board): possible_moves = [] rows, cols = board.shape for i in range(rows): for j in range(cols): if board[i, j].is_island: # horizontal neighbors line = board[i, :] left, right = line[:j], line[j:] for k in range(len(left)-1, -1, -1): if left[k].is_island: possible_moves.append((board[i, j], left[k])) break for neighbor in right: if neighbor.is_island and neighbor.col != j: possible_moves.append((board[i, j], neighbor)) break # vertical neighbors col_line = board[:, j] up, down = col_line[:i], col_line[i:] for k in range(len(up)-1, -1, -1): if up[k].is_island: possible_moves.append((board[i, j], up[k])) break for neighbor in down: if neighbor.is_island and neighbor.row != i: possible_moves.append((board[i, j], neighbor)) break return find_solution(copy.deepcopy(board), possible_moves) if __name__ == "__main__": board = create_board("islands.in") print_board(board) rows, cols = board.shape is_human = False print("Automatic (1)") print("Human (2)") while True: choice = input("How run? (1=auto, 2=human): ").strip() if choice == "1": break elif choice == "2": is_human = True break while True: try: if is_human: print_board(board) coords = list(map(int, input("Enter coords row1,col1,row2,col2: ").split(','))) if len(coords) != 4: raise ValueError("Enter 4 comma-separated numbers") if any(c < 0 or c >= rows for c in (coords[0], coords[2])) or any(c < 0 or c >= cols for c in (coords[1], coords[3])): raise ValueError("Invalid coordinates") move(board, *coords, True) else: solution = automatic(board) if solution is not None: for step in solution: print_board(board) move(board, step[0], step[1], step[2], step[3]) else: print("No solution") except ValueError as e: print(e) if is_winner(board): print_board(board) print("You win!") break