0
\$\begingroup\$

I'm trying to solve Pylons from the 2019's round 1A. The analysis suggests that a brute force approach should work. However, my Python 3 solution doesn't pass the 2nd test case. Can I make it faster without complicating the algorithm?

from itertools import product, repeat


def main():
    T = int(input())  # the number of test cases

    for case in range(1, T+1):
        R, C = map(int, input().split())  # the numbers of rows and columns

        stack = []

        for r, c in product(range(R), range(C)):
            grid = [[False]*C for _ in repeat(None, R)]
            grid[r][c] = True
            stack.append((((r, c),), grid))

        while stack:
            moves, grid = stack.pop()
            if len(moves) == R*C:
                print('Case #{}: POSSIBLE'.format(case))
                for r, c in moves:
                    print(r+1, c+1)
                break

            for r, c in product(range(R), range(C)):
                if (not grid[r][c] and r != moves[-1][0] and c != moves[-1][1]
                        and moves[-1][0] - moves[-1][1] != r - c
                        and moves[-1][0] + moves[-1][1] != r + c):
                    g = [r.copy() for r in grid]
                    g[r][c] = True
                    stack.append((moves+((r, c),), g))
        else:
            print('Case #{}: IMPOSSIBLE'.format(case))


main()
\$\endgroup\$
  • \$\begingroup\$ Can you share a link to the analysis you've mentioned? I have a strong doubts that the brute force may work. Meanwhile, the problem looks like a knight tour variation with an ability to make non-knight moves. Use Warnsdorff's rule, and break the dead ends with non-knight moves. \$\endgroup\$ – vnp Apr 13 at 18:36
  • \$\begingroup\$ Just follow the link and open the 'ANALYSIS' tab. \$\endgroup\$ – Eugene Yarmash Apr 13 at 19:18
  • \$\begingroup\$ There is nothing about the brute force there. The do however mention the knight tour (I honestly didn't read that tab when making the above comment). \$\endgroup\$ – vnp Apr 13 at 19:21
  • 1
    \$\begingroup\$ Can you add a title that explains what the task is? This way reviewers can get some context. \$\endgroup\$ – 422_unprocessable_entity Apr 13 at 21:56
  • \$\begingroup\$ @vnp: Did you read it to the end? :) This suggests that there are many possible solutions, and we might expect even more as the grid's dimensions get larger. {...} So, our intuition might suggest at this point that the best approach is some kind of brute force. \$\endgroup\$ – Eugene Yarmash Apr 14 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.