Marko Rauhamaa <ma...@pacujo.net>: > I have optimized my solution slightly: > > 1. precalculated integer division operations (big savings) > > 2. interned integers (little savings) > > The example above now finishes in 41 minutes on my computer. (The C > version finishes in 13 seconds).
Any considered harmfull. Changing an "any" test to a loop shortens the solving time from 41 minutes to 14 minutes. Object creation overhead seems to be the killer. The program still has a prominent integer incrementation... ======================================================================== #!/usr/bin/env python3 import sys M = 3 N = M * M P = M * N Q = M * P buddies = [ [ buddy for buddy in range(Q) if buddy != slot and (buddy % N == slot % N or buddy // N == slot // N or buddy // P == slot // P and buddy % N // M == slot % N // M) ] for slot in range(Q) ] interned = { n : n for n in range(1, N + 1) } candidates = list(interned.values()) def main(): board = [] for n in sys.stdin.read().split(): try: board.append(int(n)) except ValueError: board.append(None) solve(board) def solve(board, slot=0): if slot == Q: report(board) elif board[slot] is None: for candidate in candidates: for buddy in buddies[slot]: if board[buddy] is candidate: break else: board[slot] = candidate solve(board, slot + 1) board[slot] = None else: solve(board, slot + 1) def report(board): print("\n".join( " ".join(str(board[row * N + col]) for col in range(N)) for row in range(N))) print() if __name__ == '__main__': main() ======================================================================== Marko -- https://mail.python.org/mailman/listinfo/python-list