Как подойти к этому варианту игры NIM?

Question

Недавно я столкнулся с проблемой, которая дает вам матрицу 4*4, состоящую только из 0 и 1. В игру играют 2 игрока. В каждом ходу игрок может выбрать любую подматрицу, состоящую только из 1, и сделать ее равной 0. Игрок, который не может двигаться, проигрывает. Как применить в этом теорему Спрэга Гранди?

Пример - 0110 0000 0000 0001

Тогда игрок 1 выиграет (удалит одну "1" в первом ряду в первом ходу, во 2-м ходу игрок 2 возьмет один 1, и, таким образом, p1 займет финальный 1.

Answer 1

Вы не можете применить теорему Спраг-Гранди здесь. Теорема используется всякий раз, когда вы играете в несколько игр, например, когда вы играете в две игры на двух досках.

Вы можете просто решить, является ли доска выигрышной или проигрышной, если вы примените обычно рекурсивные определения: доска находится в выигрышном состоянии, если хотя бы один ход приводит к проигрышному состоянию. И доска находится в проигрышном состоянии, если ни одно движение не приводит к проигрышному состоянию.

def is_winning_state(board):
    for each rectangle rect of 1s on the board:
        if not is_winning_state(board - rect):
             return True
    return false

Вы также хотите применить динамическое программирование, иначе программа не будет завершена в разумные сроки.