Solve the nrich factor lines puzzle - http://nrich.maths.org/1138

factorlines.py

from itertools import product

# the size of the grid
columns = 5
rows = 5

# the cards we're given
cards = [1,2,3,21]

def valid_placement(card,place):
	# card can be put in place if place is a factor or a multiple of card
	return card%place==0 or place%card==0

# for each card, work out which cells it can be placed on
valids = [[place for place in range(1,columns*rows+1) if valid_placement(card,place)] for card in cards]

# does a given arrangement of cards (list giving places to put each card) form a line?
def valid_arrangement(arrangement):
	# if two cards have been put in the same place, this is not valid
	if len(set(arrangement))!=len(arrangement):
		return False

	#from now on, it doesn't matter which cards go where - only that the pattern forms a line

	# sort the places by number, so the smallest one will be the first in the list and the biggest one will be the last
	arrangement = sorted(arrangement)

	def grid_coords(place):
		place -= 1
		x = place % columns
		y = (place-x)//columns
		return (x,y)

	# work out the grid coordinates of each card
	coords = [grid_coords(place) for place in arrangement]

	# coords of the first card
	first_x, first_y = coords[0]
	# coords of the last card
	last_x, last_y = coords[-1]

	# if the cards are in a vertical line, then they'll all have the same x-coord
	if len(set(x[0] for x in coords))==1:
		#the cards form a continuous line if the difference in y-coords between the first and last card is one less than the number of cards
		return (last_y-first_y)==len(cards)-1
	# if the cards are in a horizontal line, then they'll all have the same y-coord
	elif len(set(x[1] for x in coords))==1:
		#the cards form a continuous line if the difference in x-coords between the first and last card is one less than the number of cards
		return (last_x-first_x)==len(cards)-1
	# if the sum of the x- and y-coords for each card is the same, then they all lie on the same upwards diagonal
	elif len(set(x[0]+x[1] for x in coords))==1:	## all on same up-diagonal
		# the difference between the x- and y-coords increases by two each step down and left, so the difference between the last and first cards' differences is 2*(number of cards - 1) when the arrangement forms a continuous line
		return ( (last_y-last_x)-(first_y-first_x) ) == 2*(len(cards)-1)
	# if the difference between the x- and y-coords for each card is the same, then they all lie on the same downwards diagonal
	elif len(set(x[0]-x[1] for x in coords))==1:
		# the sum of the x- and y-coords increases by two each step down and right, so the difference between the last and first cards' sums is 2*(number of cards - 1) when the arrangement forms a continuous line
		return ( (last_y+last_x)-(first_y+first_x) ) == 2*(len(cards)-1)
	else:
		return False

# for each possible choice of places for the four cards, work out which ones form a continuous line
arrangements = [arrangement for arrangement in product(*valids) if valid_arrangement(arrangement)]

# show the arrangements
def show_arrangement(arrangement):
	s = ''
	arrangement = list(arrangement)
	for y in range(0,rows):
		for x in range(0,columns):
			number = y*columns+x+1
			try:
				card = arrangement.index(number)
				s+=str(cards[card]).rjust(2)
			except ValueError:
				s+='--'
			if x<columns-1:
				s+=' '
		s+='\n'
	return s
for arrangement in arrangements:
	print(show_arrangement(arrangement))

# show how many arrangements there are
print("There are %i lines" % len(arrangements))