Need help with another student math challenge

I asked for help on one of my student's math challenges a few weeks ago, and you guys delivered. I'm a middle school gifted support teacher / hobbyist programmer, and we do some Scratch and basic Python in class.

This week's problem involves placing coins on a grid so the rows, columns, and diagonals each equal a given value. My student finished the problem using pencil/paper/logic, but we still want to solve it with a program.

Of course, we're not exactly sure how to approach it since though there are restrictions, there are also multiple options.

# Put the values of nickels (5), dimes (10), and quarters (25) on certain
# sqaures of this grid. Observe the following rules while doing so:
#
# Rule 1 - Only one coin per square
# Rule 2 - The rows must add up to equal the values on the right
# Rule 3 - The columns must add up to equal the values on the bottom
# Rule 4 - The diagonals must add up to equal the value at the corners
# Rule 5 - Put the value of each coin in the box
#
# Several coins have already been placed to help get you started.
# The box with a star is to remain blank.
# Hint: Not every square needs to have a coin. Some will remain blank.
#
#  40                55
#    +--+--+--+--+--+
#    |  |10|  |  |  | 40
#    +--+--+--+--+--+
#    |  |  |  |S |  | 15
#    +--+--+--+--+--+
#    |  |  |  |  |  | 85
#    +--+--+--+--+--+
#    |  |25|  |  |  | 65
#    +--+--+--+--+--+
#    |10| 5| 5|  |  | 40
#    +--+--+--+--+--+
#     60 65 40 45 35
#

View the game board here: https://drive.google.com/file/d/0B2mj8hA_IkqCV2xqcE9pTk5lLWc/view?usp=sharing

Online editor: https://repl.it/E1Oe/2

Thanks in advance!