Puzzle Me This

Description
First they took our jerbs, now they're taking our puzzles! (with your help)

Today we're gonna find a way to solve jigsaw puzzles using computers

Input Description
As I am no designer the input will be purely numerical, feel free to make some visual version of the jigsaw puzzles :)

You will first be given the dimension as X, Y

Afterwards you will be given list of puzzle pieces and what type their 4 sides connect to (given as up, right, down, left)

Their side-connection is given as a number, They connect with their negated number

this means that a 1 and -1 connects, 2 and -2 connects etc.

0 means that it doesnt connect with anything.

Assume pieces are rotated in the correct direction.

fx:

2, 2
0: 0,1,2,0
1: 0,0,2,-1
2: -2,0,0,2
3: -2,-2,0,0
Output Description
Output is a 2D picture/matrix of the pieces in their correct position

for the example this would be

0 1
3 2
Challenge Input
Challenges are generated, so there is a slight chance of multiple solutions :P

5 by 5
https://pastebin.com/raw/rgrAdmnd

10 by 10
https://pastebin.com/raw/DRik2yrA

100 by 100
https://pastebin.com/raw/J8U6GxhL

Bonus
The pieces are randomly rotated and might need to be rotated to fit.

The example:

0: 0,1,2,0
1: 0,0,2,-1
2: -2,0,0,2
3: -2,-2,0,0
Could look like:

0: 0,1,2,0
1: 0,2,-1,0
2: 2,-2,0,0
3: -2,-2,0,0


Solution
in C

#include <stdio.h>

#define U 0
#define R 1
#define D 2
#define L 3

static int
solve(int parts[][4], int w, int h, int n, int *solution)
{
    if (n == w * h)
        return 1;

    int x = n % w;
    int y = n / w;
    for (int i = n; i < w * h; i++) {
        int p = solution[i];
        int valid = 1;

        /* Check left */
        if (x == 0) {
            if (parts[p][L] != 0)
                valid = 0;
        } else {
            int left = solution[n - 1];
            if (!parts[p][L] || parts[p][L] != -parts[left][R])
                valid = 0;
        }

        /* Check right */
        if (y == 0) {
            if (parts[p][U] != 0)
                valid = 0;
        } else {
            int up = solution[(y - 1) * w + x];
            if (!parts[p][U] || parts[p][U] != -parts[up][D])
                valid = 0;
        }

        if (valid) {
            int save = solution[n];
            solution[n] = p;
            solution[i] = save;
            if (solve(parts, w, h, n + 1, solution))
                return 1;
            solution[n] = save;
            solution[i] = p;
        }
    }

    return 0;
}

int
main(void)
{
    /* Parse input */
    int w, h;
    int parts[256][4];
    scanf("%d, %d", &w, &h);
    for (int i = 0; i < w * h; i++) {
        int n, p[4];
        scanf("%d: %d,%d,%d,%d", &n, p, p + 1, p + 2, p + 3);
        parts[n][0] = p[0];
        parts[n][1] = p[1];
        parts[n][2] = p[2];
        parts[n][3] = p[3];
    }

    /* Initialize solution array */
    int solution[sizeof(parts) / sizeof(*parts)];
    for (int i = 0; i < w * h; i++)
        solution[i] = i;

    /* Run solver and print the first solution (if any) */
    if (solve(parts, w, h, 0, solution))
        for (int y = 0; y < h; y++)
            for (int x = 0; x < w; x++)
                printf("% 3d%s", solution[y * w + x], "\n" + (x < w - 1));
}