Pulgas Saltarinas por backtracking !

pulgassaltarinas.py

#!/usr/bin/python3

import sys
from time import time
from math import sqrt
from random import uniform

UP = 0
RIGHT = 1
DOWN = 2
LEFT = 3

PRINT_PROBABILITY = 1

jumps_to = {
    UP: lambda pos, square_count: pos - int(sqrt(square_count)),
    RIGHT: lambda pos, square_count: pos + 1,
    DOWN: lambda pos, square_count: pos + int(sqrt(square_count)),
    LEFT: lambda pos, square_count: pos - 1
}

# (JUMP + 2) % 4 
collide_jump = {
    UP: DOWN,
    RIGHT: LEFT,
    LEFT: RIGHT,
    DOWN: UP
}

def flea_goes_out_of_board(board, pos, new_pos, jump_type):
    # UP
    if new_pos < 0:
        return True
    # DOWN
    if new_pos >= len(board):
        return True
    
    column = pos % int(sqrt(len(board)))
    new_column = new_pos % int(sqrt(len(board)))
        
    if column - new_column != 1 and jump_type == LEFT:
        return True
    
    if new_column - column != 1 and jump_type == RIGHT:
        return True
    
    return False

def flea_collides(board, pos, new_pos, jump_type):
    return board[new_pos] == collide_jump[jump_type]    

def flea_steals_square(board, pos, new_pos, jump_type):
    
    new_neighboors = [
        jumps_to[UP](new_pos, len(board)),
        jumps_to[RIGHT](new_pos, len(board)),
        jumps_to[DOWN](new_pos, len(board)),
        jumps_to[LEFT](new_pos, len(board))
    ]
    
    for neighboor in new_neighboors:
        if neighboor < 0 or neighboor >= len(board):
            continue
        
        where_did_jump = board[neighboor]
        if not where_did_jump:
            continue
        
        if jumps_to[where_did_jump](neighboor, len(board)) == new_pos:
            return True

    return False

def flea_can_jump(board, pos, jump_type):
    new_pos = jumps_to[jump_type](pos, len(board))
    return not (
        flea_goes_out_of_board(board, pos, new_pos, jump_type) or
        flea_collides(board, pos, new_pos, jump_type) or
        flea_steals_square(board, pos, new_pos, jump_type)
    )


def print_solution(board):
    rand = uniform(0, 1)
    if rand <= PRINT_PROBABILITY:
        print('Yay !', board)

def build_jump_path(board, pos):
    if pos >= len(board):
        print_solution(board)
        return 1
    
    jump_count = 0
    
    for JUMP in range(4):
        if flea_can_jump(board, pos, JUMP):
            board[pos] = JUMP
            jump_count += build_jump_path(board, pos + 1)
            board[pos] = None

    return jump_count
            
    
def main(board_size):
    before_exec_time = time()

    square_count = board_size * board_size
    board = [None] * square_count
    
    jump_count = build_jump_path(board, 0)
    print(jump_count)
    
    print('Execution Time: {:.6} seconds'.format(time() - before_exec_time))

if __name__ == '__main__':
    main(int(sys.argv[1]))