How can I optimize my brute-force solution to this problem?
Integer linear programming
Your problem can be formulated in the following way: we are given vectors $v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, where the board has $d$ cells, and the goal is, given a vector $c \in (\mathbb{Z}/N\mathbb{Z})^d$, find a function $f$ so that $\sum_i v_{i,f(j)}=c$.  This problem could then be solved by integer linear programming.  This is related to a $d$-dimensional subset-sum problem, so you might also be able to find other algorithms for multi-dimensional subset-sum and try them out as well.
How do we formulate it in that way?  If the grid has $d$ cells, we can think of a shape as a $d$-vector of 0's and 1's, with 1's in the cells covered by the shape.  Each shape can be placed in a number of different positions, yielding different vectors.  $v_{i,j}$ corresponds to the $j$th place where shape $i$ can be placed.  $c$ corresponds to the the numbers originally in the grid (well, the negation of those numbers, modulo $N$).  All arithmetic is done modulo $N$.
Slightly smarter brute force
Alternatively, here is a way to improve brute force a little bit, by trading memory for time.  Suppose you have $k$ shapes.  Start by enumerating all ways to place the first $k/2$ shapes onto an empty board of all zeros, and store all resulting positions in a hashtable or sorted list.  Then, enumerate all ways to place the last $k/2$ shapes onto the starting position, and look up each of the resulting positions in the hashtable or sorted list.  If you find any match, then that yields a solution.  This will let you push brute force a bit further -- potentially to about twice as many shapes -- if you have an unlimited amount of memory.  There are a lot of details involved in optimizing this to the max, but it's an idea you could consider if you brute force gets you close but falls a little bit short.  It is still an exponential-time algorithm so it will still hit a limit.