Puzzle Solution

solve_puzzle.py

def direction_to_increment(direction):
    """Map a direction to x and y increments."""
    mapping = {
        "N": (0, 1),
        "NE": (1, 1),
        "E": (1, 0),
        "SE": (1, -1),
        "S": (0, -1),
        "SW": (-1, -1),
        "W": (-1, 0),
        "NW": (-1, 1)
    }
    return mapping[direction]

def invert_direction(direction):
    """Invert a direction to move backward."""
    inverse_mapping = {
        "N": "S",
        "NE": "SW",
        "E": "W",
        "SE": "NW",
        "S": "N",
        "SW": "NE",
        "W": "E",
        "NW": "SE"
    }
    return inverse_mapping[direction]

def is_valid_position(x, y, n, m):
    """Check if a position is within the bounds of the board."""
    return 0 <= x < n and 0 <= y < m

def validate_path(board, start, end):
    """
    Validate if the path from the starting position to the end position is valid.

    Args:
        board: The n x m matrix containing direction sets.
        start: Tuple (x, y) for the current position.
        end: Tuple (x, y) for the target position.

    Returns:
        True if the path is valid, False otherwise.
    """
    rows = len(board)
    cols = len(board[0])  if rows > 0 else 0

    end_x, end_y = end
    if not is_valid_position(end_x, end_y, rows, cols):
        return False

    directions = board[end_x][end_y]
    reversed_directions = directions[::-1]  # Reverse the order of the steps

    current_x, current_y = end_x, end_y

    for direction in reversed_directions:
        inverted_direction = invert_direction(direction)
        dx, dy = direction_to_increment(inverted_direction)
        current_x += dx
        current_y += dy

        if not is_valid_position(current_x, current_y, rows, cols):
            return False

    return (current_x, current_y) == start

def find_possible_ends(board, start):
    """
    Find all possible end positions given a starting position.

    Args:
        board: The n x m matrix containing direction sets.
        start: Tuple (x, y) for the current position.

    Returns:
        List of tuples representing possible end positions.
    """
    rows = len(board)
    cols = len(board[0])  if rows > 0 else 0

    start_x, start_y = start
    if not is_valid_position(start_x, start_y, rows, cols):
        return []

    possible_ends = []

    for end_x in range(rows):
        for end_y in range(cols):
            directions = board[end_x][end_y]
            reversed_directions = directions[::-1]  # Reverse the order of the steps

            current_x, current_y = end_x, end_y

            valid_path = True
            for direction in reversed_directions:
                if direction is None:
                    valid_path = False
                    break

                inverted_direction = invert_direction(direction)
                dx, dy = direction_to_increment(inverted_direction)
                current_x += dx
                current_y += dy

                if not is_valid_position(current_x, current_y, rows, cols):
                    valid_path = False
                    break

            if valid_path and (current_x, current_y) == start:
                possible_ends.append((end_x, end_y))

    return possible_ends

def convert_to_decoder_indices(possible_ends, board, decoder):
    """
    Convert possible end positions to decoder indices using the board and decoder matrix.

    Args:
        possible_ends: List of possible end positions.
        board: The n x m matrix containing direction sets.
        decoder: The decoder matrix mapping directions to indices.

    Returns:
        List of tuples containing end positions and corresponding decoder indices.
    """
    results = []

    for end_x, end_y in possible_ends:
        directions = board[end_x][end_y]  # Use board value for the directions

        decoder_indices = []
        reversed_decoder = decoder[::-1]
        reversed_direction = directions[::-1]
        for idx, direction in enumerate(reversed_direction):
            row = reversed_decoder[idx]
            if direction in row:
                decoder_indices.append((directions[idx], row.index(direction)))

        if decoder_indices:
            results.append(((end_x, end_y), decoder_indices))

    return results

def find_next_possible_ends(board, decoder, start, end):
    start_position = start
    possible_ends = find_possible_ends(board, start_position)
    results = convert_to_decoder_indices(possible_ends, board, decoder)
    for end_position, indices in results:
        print(f"Start: {start} Possible end: {end_position}, Decoder indices: {indices}")

    if end is not None:
        if end not in possible_ends:
            print(f"{end} is NOT possible from {start}")
    return possible_ends

def check_movements(movements, board, decoder):
    print(f"Board Size: {len(board)} x {len(board[0])}")

    for i, (start, end) in enumerate(movements):
        valid = validate_path(board, start, end)
        print(f"Movement {i + 1}: {start} to {end} is {'valid' if valid else 'invalid'}.")
    for i, (start, end) in enumerate(movements):
        find_next_possible_ends(board, decoder, start, end)

def encode_board(board):
    return [list(row[::-1]) for row in zip(*board)]

# Define the board and decoder matrix
decoder = [
    ["N", "S", "E", "W", "SE", "NW", "NE", "SW", "N"],
    ["E", "W", "SE", "NW", "NE", "SW", "N", "S", "E"],
    ["SE", "NW", "NE", "SW", "N", "S", "E", "W", "SE"]
]

def test():
    """
    Test the solution with a sample board and movements.
    """
    test_board = [
        [['N', 'SW', 'N'], ['N', 'N', 'E'], ['N', 'N', 'E']],
        [['SW', 'N', 'W'], ['N', 'E', 'S'], ['S', 'S', 'N']],
        [[None, None, None], ['N', 'W', 'S'], ['S', 'S', 'E']]
    ]

    encoded_board = encode_board(test_board)

    # Test movements: (x, y)
    test_movements = [
        ((0, 0), (1, 2)),
        ((1, 2), (2, 0)),
        ((2, 0), (1, 0)),
        ((1, 0), (2, 2)),
        ((2, 2), (2, 1)),
        ((2, 1), (0, 1)),
        ((0, 1), (1, 1)),
        ((1, 1), (0, 2))
    ]
    check_movements(test_movements, encoded_board, decoder)

def main():
    """
    Main function to test the solution with a sample board and movements.
    """
    game_board = [
        [["N","N","N"],["NW","SE","NW"],["SE","NE","NW"],["N","W","S"],["NW","W","NE"],["S","NE","NE"]],
        [["NE","NW","S"],["NW","SE","N"],["S","NE","SE"],["E","E","E"],["NE","E","NW"],["E","SE","E"]],
        [["N","SW","NW"],["W","W","NW"],["W","W","NW"],["SE","W","SW"],["NE","NW","N"],["S","W","SE"]],
        [["SW","N","SW"],["SW","SW","W"],["W","W","S"],["S","SE","SE"],["W","SE","E"],["S","W","SE"]]
    ]
    # (x, y)
    game_movements = [
        ((4,1),(2,0)),
        ((2,0),(0,1)),
        ((0,1),(0,2)),
        ((0,2),(3,2)),
        ((3,2),(5,3)),
        ((5,3),(5,1)),
        ((5,1),(4,3)),
        ((4,3),(3,1)),
        ((3,1),(4,0)),
    ]

    encoded_game_board = encode_board(game_board)
    check_movements(game_movements, encoded_game_board, decoder)
    print("== Next moves ==")
    next_end = game_movements[-1][1]
    while next_end:
        next_ends = find_next_possible_ends(encoded_game_board, decoder, next_end, None)
        if len(next_ends) == 0:
            break
        next_end = next_ends[0]

if __name__ == "__main__":
    main()