Problem z zadaniem z Backtrackingu

0

Próbuje uporać się z tym problemem od paru godzin, mimo to po za kilkoma brutowymi rozwiązaniami, które i tak nie działały nic nie zrobiłem.. Może ktoś ma jakiś pomysł?

https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/kul/

0

No ale przecież w tym zadaniu jasno napisali że masz zrobić bruta "na pałe" bo plansza ma 8x8 a maksymalny poziom zagłębienia to 8. Więc testujesz wszystkie możliwe ruchy i wybierasz najlepszą sekwencje. Piszesz więc funkcje rekurencyjną:

def solve(board, moves=[], level=0):
    score = calculate_score(board)
    if score == 0:
        return moves
    elif level == 8:
        return None
    else:
        shortest_sequence = [None for i in range(17)]
        for possible_move in available_moves(board):
            new_board = make_move(board, possible_move)
            new_moves = solve(new_board, moves + possible_move, level + 1)
            if new_moves is not None and len(new_moves) < len(shortest_sequence):
                shortest_sequence = new_moves
        return shortest_sequence

Czyli:

  • Jeśli mamy już 0 kulek to zwracamy listę ruchów które nas do tego doprowadziły
  • Jeśli jesteśmy już po 8 ruchach i nadal nie mamy 0, to zwracamy None, bo ta ścieżka jest zła
  • Jeśli nie mamy jeszcze 0 ale mozemy wykonywać ruchy, to testujemy każdy możliwy ruch i sprawdzamy co dostaniemy jeśli go wykonamy. Jeśli dostaniemy jakąś listę ruchów (a nie None) to znaczy że dany ruch prowadzi do sytuacji gdzie dochodzimy do 0 kulek. Zapamiętujemy sobie najkrótszą taką sekwencje i zwracamy ją z funkcji.

Niemniej samo zadanie jest moim zdaniem dość głupie, bo algorytm rozwiązywania gry jest dość prosty, za to implementacja całej logiki do tego zadania jest mega żmudne tak na oko :)

0

Oo no tak, za bardzo sobie pokomplikowałem ten algorytm, teraz jest to dużo jaśniejsze, dzięki ;)

0

No tylko że to jest mimo wszystko dość skomplikowane ->

def print_board(board):
    print("\n".join([" ".join(line) for line in board]) + "\n")


def calculate_score(board):
    return sum([sum([1 for field in line if field != '.']) for line in board])


def available_moves(board):
    moves = []
    size = len(board)
    for i in range(size):
        for j in range(size - 1):
            moves.append(((i, j), (i, j + 1)))
            moves.append(((i, j + 1), (i, j)))
            moves.append(((j, i), (j + 1, i)))
            moves.append(((j + 1, i), (j, i)))
    return moves


def swap(board, possible_move):
    new_board = [[field for field in line] for line in board]
    source, target = possible_move
    tmp = board[target[0]][target[1]]
    new_board[target[0]][target[1]] = board[source[0]][source[1]]
    new_board[source[0]][source[1]] = tmp
    return new_board


def simplify_rows(board):
    to_remove = []
    for row in range(len(board)):
        identical = 1
        for col in range(len(board[0]) - 1):
            if board[row][col] != '.' and board[row][col] == board[row][col + 1]:
                identical += 1
            else:
                identical = 1
            if identical >= 3:
                to_remove.extend([(row, col - c + 1) for c in range(identical)])
    return set(to_remove)


def simplify_cols(board):
    to_remove = []
    for col in range(len(board)):
        identical = 1
        for row in range(len(board[0]) - 1):
            if board[row][col] != '.' and board[row][col] == board[row + 1][col]:
                identical += 1
            else:
                identical = 1
            if identical >= 3:
                to_remove.extend([(row - r + 1, col) for r in range(identical)])
    return set(to_remove)


def gravity_drop(board):
    size = len(board)
    for row in range(size):
        for col in range(size):
            if board[size - row - 1][col] == '.':
                for up_row in range(size - row - 1, -1, -1):
                    if board[up_row][col] != '.':
                        board[size - row - 1][col] = board[up_row][col]
                        board[up_row][col] = '.'
                        break
    return board


def simplify(board):
    to_remove = []
    to_remove.extend(simplify_rows(board))
    to_remove.extend(simplify_cols(board))
    for x, y in to_remove:
        board[x][y] = '.'
    if len(to_remove) > 0:
        board = gravity_drop(board)
        return simplify(board)
    return board


def make_move(board, possible_move):
    new_board = swap(board, possible_move)
    return simplify(new_board)


def to_text(moves):
    return "".join(["".join(map(str, list(source))) + "".join(map(str, list(target))) for (source, target) in moves])


def is_lexicographically_smaller(solution1, solution2):
    return to_text(solution1) < to_text(solution2)


def solve(board, moves=[], level=0):
    score = calculate_score(board)
    if score == 0:
        return moves
    elif level == 8:
        return None
    else:
        shortest_sequence = [None for i in range(999)]
        for possible_move in available_moves(board):
            new_board = make_move(board, possible_move)
            new_score = calculate_score(new_board)
            if new_score == score:
                continue
            new_moves = solve(new_board, moves + [possible_move], level + 1)
            if new_moves is not None:
                if len(new_moves) < len(shortest_sequence):
                    shortest_sequence = new_moves
                elif len(new_moves) == len(shortest_sequence) and is_lexicographically_smaller(new_moves, shortest_sequence):
                    shortest_sequence = new_moves
        if None not in shortest_sequence:
            return shortest_sequence
        else:
            return None


def main():
    data = """........
........
........
........
........
.01.....
.10.....
.01....."""
    board = [list(x) for x in data.split("\n")]
    print(solve(board))


main()

(numeruje wiersze i kolumny od 0, więc ten wynik (6, 1), (6, 2) to jest to co w przykładzie z zadania 7 2 7 3).

Ale tak jak pisalem wcześniej, sama funkcja rekurencyjna jest dość prosta w porównaniu z tym usuwaniem wierszy/kolumn i przesuwaniem kulek w dół na wolne miejsca... ;]

0

Dzięki za zaklepanie tego algorytmu, mój nie był jednak wolny od błędów bo funkcja usuwająca kulki za pomocą grawitacji nie działała tak jak powinna ;d

1 użytkowników online, w tym zalogowanych: 0, gości: 1