Problems solving Magic Domino (Blizzard)

I have been trying to solve this problem but I do not how to proceed.

I tried two different approaches:

First...

Store all possible combinations of rows that sum the magic number. Then solve the problem using backtrack: 'size' nested for loops and checking the constrains (sum(cols), sum(rows) and sum(diagonals)) each step. Of course with as much optimizations as I realized. With size of 6, the first set of combinations is 6000 long, and I got this number reduced to 1000 after third loop. (something like 6000 combs first loop, 4000 second, 6000 third, 1000 fourth, 6000 fifth, 500 sixth)

Second...

Store all domino pieces and again used backtracking to solve the problem. This case recursively adding a piece each step, checking conditions, if pass all conditions keep adding pieces, else try another piece until last piece (in this case go back and modify the previous piece).

==================

For size = 4 it is okey. It does not take long and solves everything. But with size = 6 it takes so many minutes.

Can anyone help me? I really want to solve this problem but I need a clue or something :/