## 1. Abridged Problem Statement

A square chessboard of size `N × N` (`1 ≤ N ≤ 5`) was broken into connected pieces. The pieces are shown scattered on a `20 × 20` table. Each piece is marked by a distinct uppercase Latin letter, and empty table cells are `.`.

Pieces may be rotated by `0°`, `90°`, `180°`, or `270°`, but not reflected. Using every given piece exactly once, reconstruct any valid `N × N` square and output it as `N` lines of letters.

It is guaranteed that at least one reconstruction exists.

---

## 2. Detailed Editorial

### Key observations

- The target board has at most `5 × 5 = 25` cells.
- Each input piece is represented by all cells with the same letter.
- A piece can be rotated, but not mirrored.
- We need an exact tiling of an `N × N` board using all pieces exactly once.

This is naturally solved by backtracking.

---

### Representing a piece

For every letter, collect all its occupied cells from the `20 × 20` input.

For example, a piece might have absolute coordinates:

```text
(13, 12), (14, 11), (14, 12), (14, 13), (15, 12)
```

We normalize a piece by shifting it so that its minimum row and minimum column become zero.

So the above becomes:

```text
(0, 1), (1, 0), (1, 1), (1, 2), (2, 1)
```

Then we sort the cells lexicographically. This gives a canonical representation of that shape in that orientation.

---

### Generating rotations

A `90°` rotation can be represented as:

```text
(r, c) -> (c, -r)
```

After rotating, normalize again.

For each piece, generate up to four rotations:

```text
0°, 90°, 180°, 270°
```

Some pieces are symmetric, so duplicate rotations are removed.

---

### Grouping identical pieces

If two pieces have the same shape up to rotation, they are interchangeable.

For example, if pieces `A`, `B`, and `C` are all single cells, treating them separately would cause unnecessary permutations. Instead, group them together.

For every piece:

1. Generate all unique rotations.
2. Pick the lexicographically smallest rotation as its canonical key.
3. Store pieces with the same key in one group.

Each group contains:

- the list of possible orientations,
- the list of letters still unused from that shape group.

This drastically reduces backtracking.

---

### Backtracking strategy

Maintain an `N × N` result board initialized with dots.

At every recursive step:

1. Find the first empty cell in row-major order.
2. Try to place each remaining piece group there.
3. For each possible orientation of that group:
   - align the orientation’s first cell with the target empty cell,
   - check whether all cells are inside the board and currently empty,
   - place the piece,
   - recurse,
   - undo if recursion fails.

Why can we align the piece’s first cell to the first empty board cell?

Because the chosen board cell is the first empty cell in row-major order. Any valid new piece placement cannot occupy an earlier board cell, because all earlier cells are already filled. Therefore, the lexicographically first cell of the placed piece must land exactly on the chosen empty cell.

This avoids trying all possible translations.

---

### Correctness proof

#### Lemma 1

The generated orientation list of a piece contains exactly all distinct rotations allowed by the statement.

**Proof.**

The algorithm applies the rotation transformation four times, corresponding to rotations by `0°`, `90°`, `180°`, and `270°`. After each rotation, the shape is normalized. Duplicate rotations caused by symmetry are removed. Therefore, all and only valid distinct rotations are generated. ∎

#### Lemma 2

Grouping identical pieces does not remove any valid solution.

**Proof.**

Pieces in the same group have the same shape up to rotation. Therefore, any placement possible for one piece in the group is also possible for any other piece in that group. Since the output only needs each letter to occupy a shape matching its original piece, swapping identical-shape letters preserves validity. ∎

#### Lemma 3

When filling the first empty cell, it is sufficient to align it with the first cell of a candidate orientation.

**Proof.**

Let `(r, c)` be the first empty cell in row-major order. All cells before `(r, c)` are already occupied.

Suppose a valid next placement covers `(r, c)`. If the lexicographically first cell of that placed piece were before `(r, c)`, then that cell would already be occupied, causing overlap. Hence the first cell of the placed piece must be exactly `(r, c)`. ∎

#### Lemma 4

The backtracking search considers every valid tiling.

**Proof.**

Consider any valid final tiling extending the current partial board. By Lemma 3, the piece covering the first empty cell must be placed with its first orientation cell aligned to that empty cell. The algorithm tries every remaining shape group and every orientation, so it will try that placement. Repeating this argument recursively shows that the whole tiling is considered. ∎

#### Lemma 5

Every board printed by the algorithm is valid.

**Proof.**

The algorithm only places pieces inside the board, only on empty cells, and removes exactly one available letter from the corresponding shape group. The recursion stops only when no empty cells remain. Since the total area of all pieces equals `N²`, every piece has been used exactly once, and the board is fully tiled. ∎

#### Theorem

The algorithm outputs a valid reconstruction of the broken chessboard.

**Proof.**

By Lemma 4, since a solution is guaranteed to exist, the backtracking will find one. By Lemma 5, the printed reconstruction is valid. ∎

---

### Complexity

The board has at most `25` cells, so the recursion depth is at most the number of pieces, also at most `25`.

In the worst theoretical case, backtracking can be exponential. However:

- `N ≤ 5`,
- rotations are at most four per piece,
- identical pieces are grouped,
- choosing the first empty cell greatly reduces placement possibilities.

So the solution is easily fast enough for the given constraints.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<string> grid;

void read() {
    cin >> n;
    grid.assign(20, "");
    cin >> grid;
}

void solve() {
    // We need to tile the N x N square (N <= 5) with the given pieces, where
    // each piece may be used in any of its 4 rotations. This is exact-cover
    // backtracking: always look at the first empty cell in row-major order, and
    // try to cover it with some still-unused piece in some orientation. Because
    // that cell is the row-major minimum among all empty cells, the piece's own
    // row-major minimum cell must land exactly on it, so each (piece,
    // orientation) gives a single placement to test, which keeps recursion
    // shallow and branchless per cell.
    //
    // The key pruning is collapsing isomorphic pieces. For every piece we
    // generate the (de-duplicated) set of its rotation shapes and take the
    // smallest of them as a canonical key. Pieces sharing a key are
    // interchangeable, so we store them as one group holding the shared list of
    // orientations plus a stack of the actual letters still available. The
    // branching factor at each step is then "number of distinct shapes still
    // present" times "orientations", not "number of pieces" - e.g. 25 unit
    // squares become a single group instead of a 25! explosion.
    //
    // Pieces are represented as sorted vectors of relative (row, col) cells,
    // normalized so the minimum row and column are zero; orient[0] is then the
    // anchor cell we align onto the target empty cell.
    //
    // For a loose complexity bound, let the distinct shapes have multiplicities
    // m_1..m_S and orientation counts o_i <= 4, with sum(m_i) = K pieces and
    // sum(m_i * size_i) = N^2 <= 25. A root-to-leaf path is a sequence of
    // (shape, orientation) placements, so the number of leaves is at most
    // K! / (m_1! * ... * m_S!) * product(o_i ^ m_i): the multinomial counts the
    // orderings of non-isomorphic pieces (identical pieces collapse, which is
    // why 25 unit squares stay linear instead of 25!), and the product counts
    // the orientation freedom. This is maximized when all shapes are distinct,
    // giving at most K! * 4^K; feasibility caps K at 8 for N = 5 (the smallest
    // eight distinct one-sided polyominoes already sum to 25 cells), so the
    // worst case is about 8! * 4^8 ~ 2.6e9. That is a wild over-count because
    // it ignores geometry: the first empty cell that no remaining piece can
    // cover prunes an entire subtree, so the real search is microscopic in
    // practice.

    map<char, vector<pair<int, int>>> piece_cells;
    for(int i = 0; i < 20; i++) {
        for(int j = 0; j < 20; j++) {
            if(grid[i][j] != '.') {
                piece_cells[grid[i][j]].push_back({i, j});
            }
        }
    }

    auto normalize = [](vector<pair<int, int>> cells) {
        int mr = INT_MAX, mc = INT_MAX;
        for(auto& [r, c]: cells) {
            mr = min(mr, r);
            mc = min(mc, c);
        }
        for(auto& [r, c]: cells) {
            r -= mr;
            c -= mc;
        }
        sort(cells.begin(), cells.end());
        return cells;
    };

    auto rotate = [&](const vector<pair<int, int>>& cells) {
        vector<pair<int, int>> rotated;
        for(auto& [r, c]: cells) {
            rotated.push_back({c, -r});
        }
        return normalize(rotated);
    };

    auto orientations = [&](vector<pair<int, int>> base) {
        base = normalize(base);
        vector<vector<pair<int, int>>> orients;
        for(int k = 0; k < 4; k++) {
            if(find(orients.begin(), orients.end(), base) == orients.end()) {
                orients.push_back(base);
            }
            base = rotate(base);
        }
        return orients;
    };

    struct group_t {
        vector<vector<pair<int, int>>> orients;
        vector<char> letters;
    };

    map<vector<pair<int, int>>, group_t> grouped;
    for(auto& [letter, cells]: piece_cells) {
        auto orients = orientations(cells);
        auto key = *min_element(orients.begin(), orients.end());
        auto& g = grouped[key];
        if(g.orients.empty()) {
            g.orients = orients;
        }
        g.letters.push_back(letter);
    }

    vector<group_t> groups;
    for(auto& [key, g]: grouped) {
        groups.push_back(g);
    }

    vector<string> res(n, string(n, '.'));

    function<bool()> backtrack = [&]() -> bool {
        int tr = -1, tc = -1;
        for(int i = 0; i < n && tr < 0; i++) {
            for(int j = 0; j < n; j++) {
                if(res[i][j] == '.') {
                    tr = i;
                    tc = j;
                    break;
                }
            }
        }

        if(tr < 0) {
            return true;
        }

        for(auto& g: groups) {
            if(g.letters.empty()) {
                continue;
            }

            for(auto& orient: g.orients) {
                int ar = orient[0].first, ac = orient[0].second;
                bool ok = true;
                for(auto& [r, c]: orient) {
                    int nr = tr + r - ar, nc = tc + c - ac;
                    if(nr < 0 || nr >= n || nc < 0 || nc >= n ||
                       res[nr][nc] != '.') {
                        ok = false;
                        break;
                    }
                }

                if(!ok) {
                    continue;
                }

                char letter = g.letters.back();
                g.letters.pop_back();
                for(auto& [r, c]: orient) {
                    res[tr + r - ar][tc + c - ac] = letter;
                }

                if(backtrack()) {
                    return true;
                }

                for(auto& [r, c]: orient) {
                    res[tr + r - ar][tc + c - ac] = '.';
                }
                g.letters.push_back(letter);
            }
        }

        return false;
    };

    backtrack();

    for(auto& row: res) {
        cout << row << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution with Detailed Comments

```python
import sys


def normalize(cells):
    """
    Normalize a shape.

    Given a list of cells [(r, c), ...], shift all cells so that
    the minimum row and minimum column become 0.

    The result is returned as a sorted tuple of pairs so it can be:
    - compared lexicographically,
    - used as a dictionary key.
    """

    # Find the topmost row used by the shape.
    min_r = min(r for r, c in cells)

    # Find the leftmost column used by the shape.
    min_c = min(c for r, c in cells)

    # Shift every cell by subtracting the minimum row and column.
    shifted = [(r - min_r, c - min_c) for r, c in cells]

    # Sort to get a deterministic representation.
    shifted.sort()

    # Return tuple because lists are not hashable in Python.
    return tuple(shifted)


def rotate(cells):
    """
    Rotate a shape by 90 degrees.

    Rotation formula:
        (r, c) -> (c, -r)

    After rotation, normalize the result.
    """

    # Apply the rotation transformation to every cell.
    rotated = [(c, -r) for r, c in cells]

    # Normalize the rotated shape before returning it.
    return normalize(rotated)


def get_orientations(cells):
    """
    Generate all distinct rotations of a shape.

    A piece may be rotated by:
    - 0 degrees,
    - 90 degrees,
    - 180 degrees,
    - 270 degrees.

    Symmetric pieces may have duplicate rotations, so duplicates are removed.
    """

    # Start from normalized original shape.
    cur = normalize(cells)

    # Stores unique orientations.
    orientations = []

    # Generate four rotations.
    for _ in range(4):
        # Add only if this orientation has not appeared before.
        if cur not in orientations:
            orientations.append(cur)

        # Rotate for the next iteration.
        cur = rotate(cur)

    # Return unique rotations.
    return orientations


def solve():
    # Read all input lines.
    data = sys.stdin.read().splitlines()

    # First line is N.
    n = int(data[0])

    # Next 20 lines describe the table.
    grid = data[1:21]

    # Dictionary from piece letter to list of occupied cells.
    piece_cells = {}

    # Scan the 20 x 20 table.
    for i in range(20):
        for j in range(20):
            ch = grid[i][j]

            # Dot means empty table cell.
            if ch == ".":
                continue

            # Add this coordinate to the corresponding piece.
            piece_cells.setdefault(ch, []).append((i, j))

    # Groups identical pieces up to rotation.
    #
    # Key:
    #   canonical shape representation.
    #
    # Value:
    #   dictionary containing:
    #   - "orients": list of unique orientations,
    #   - "letters": unused letters of this shape.
    grouped = {}

    # Process pieces in sorted letter order for deterministic output.
    for letter in sorted(piece_cells):
        # Generate all orientations of this piece.
        orients = get_orientations(piece_cells[letter])

        # Canonical key is the lexicographically smallest orientation.
        key = min(orients)

        # Create group if not present.
        if key not in grouped:
            grouped[key] = {
                "orients": orients,
                "letters": []
            }

        # Add this piece letter to its group.
        grouped[key]["letters"].append(letter)

    # Convert groups to a list for iteration in backtracking.
    groups = list(grouped.values())

    # Current result board, initially empty.
    board = [["." for _ in range(n)] for _ in range(n)]

    def backtrack():
        """
        Recursive exact-cover search.

        Finds the first empty cell and tries to place one remaining piece
        so that its first normalized cell lands there.
        """

        # First empty cell coordinates.
        target_r = -1
        target_c = -1

        # Find first empty cell in row-major order.
        for i in range(n):
            found = False
            for j in range(n):
                if board[i][j] == ".":
                    target_r = i
                    target_c = j
                    found = True
                    break
            if found:
                break

        # If no empty cell exists, the board is completely tiled.
        if target_r == -1:
            return True

        # Try every group of identical shapes.
        for group in groups:
            # If no unused pieces of this shape remain, skip.
            if not group["letters"]:
                continue

            # Try each possible rotation of this shape.
            for orient in group["orients"]:
                # First cell of this normalized orientation.
                anchor_r, anchor_c = orient[0]

                # Actual cells this placement would occupy.
                placed_cells = []

                # Assume valid until proven otherwise.
                ok = True

                # Check every cell of the piece.
                for r, c in orient:
                    # Translate this cell so anchor goes to target.
                    nr = target_r + r - anchor_r
                    nc = target_c + c - anchor_c

                    # Check board bounds.
                    if nr < 0 or nr >= n or nc < 0 or nc >= n:
                        ok = False
                        break

                    # Check overlap.
                    if board[nr][nc] != ".":
                        ok = False
                        break

                    # Remember cell for placement if valid.
                    placed_cells.append((nr, nc))

                # If this orientation cannot be placed here, try another.
                if not ok:
                    continue

                # Choose one unused letter from this shape group.
                letter = group["letters"].pop()

                # Place the piece.
                for r, c in placed_cells:
                    board[r][c] = letter

                # Continue recursively.
                if backtrack():
                    return True

                # Undo placement.
                for r, c in placed_cells:
                    board[r][c] = "."

                # Restore the letter.
                group["letters"].append(letter)

        # No option worked.
        return False

    # A solution is guaranteed, so this should succeed.
    backtrack()

    # Print the constructed board.
    print("\n".join("".join(row) for row in board))


if __name__ == "__main__":
    solve()
```

---

## 5. Compressed Editorial

Extract every piece from the `20 × 20` grid. Represent a piece as sorted relative coordinates after shifting it to the top-left. Generate its four rotations using `(r, c) -> (c, -r)`, normalizing after each rotation and removing duplicates.

Pieces with the same shape up to rotation are interchangeable, so group them by the lexicographically smallest orientation. Each group stores its possible orientations and the remaining letters belonging to that shape.

Use backtracking on an initially empty `N × N` board. At each step, find the first empty cell. For every remaining shape group and every orientation, align the orientation’s first cell with this empty cell and test whether the piece fits without overlap. If it fits, place it, recurse, and undo on failure.

This is complete because in any valid continuation, the first empty board cell must be occupied by the lexicographically first cell of the next placed piece; otherwise the piece would also occupy an earlier already-filled cell. Since `N ≤ 5`, the search is small enough, especially with grouping identical pieces.