i183.nim

const
    N = 5


type
    direction = enum
        North, East, South, West

    board_data = array[N * N, int]
    tile_data = array[N * N, array[direction, char]]


proc read_data(): tile_data =
    var 
        f = open("input.txt")
        x: string

    for i in 0 .. <(N * N):
        x = f.readLine
        var tile: array[direction, char]
        for j in items(direction):
            tile[j] = x[ord(j)]
        result[i] = tile
    f.close


var
    board, rotate_info: board_data
    is_busy: array[N * N, bool]
    tile_info = read_data()


proc validity(pos, tile: int): bool {.inline.} =
    var x, y: bool = true
    if pos >= N:
        x = abs(ord(tile_info[tile][North]) - ord(tile_info[board[pos - N]][South])) == 32

    if pos mod N != 0:
        y = abs(ord(tile_info[tile][West]) - ord(tile_info[board[pos - 1]][East])) == 32

    result = x and y


proc rotate(piece: var array[direction, char]) =
    var temp1: char = piece[North]
    var temp2: char
    piece[North] = piece[West]
    for i in East .. West:
        temp2 = piece[i]
        piece[i] = temp1
        temp1 = temp2


proc search(pos: int): bool =
    if pos == N * N: return true
    for i in 0 .. <(N * N):
        if is_busy[i]: 
            continue
        for j in 0 .. <4:
            if validity(pos, i):
                board[pos] = i
                is_busy[i] = true
                rotate_info[i] = j
                if search(pos+1):
                    return true
                is_busy[i] = false
            rotate(tile_info[i])
    return false


if search(0):
    var output = ""
    for i in board:
        output.add($chr(65+i) & $(rotate_info[i]) & " ")
    echo output
else:
    echo "No solution"

input.txt

cKCk
yYcc
YcCK
kKCM
CMKc
cKYC
kYcm
KYyY
Mccm
yKcm
mykK
MMCm
ckYC
ycmm
MmKM
kymc
KMMK
KcyM
kYck
YCKM
myYm
kYyY
CMKM
yYCM
YKyk

output

$ nimrod c -d:release i183.nim

$ time i183.exe
A0 M2 B1 U1 I3 J2 L2 X0 V1 Q3 T0 G1 R3 H2 Y1 D0 P3 O3 S0 K2 C3 E0 N1 F1 W3

real    0m2.418s
user    0m0.000s
sys     0m0.047s