Problem Statement

Takashi is playing a puzzle game. The puzzle involves placing several puzzle pieces on a square board so that every cell of the board is filled, with no gaps left over. The board and the pieces are described as follows: The board is a square of size N x N , divided into unit cells of size 1 x 1 . Each piece is made of one or more unit tiles of size 1 x 1 . The tiles of a single piece are connected: from any tile you can reach any other tile of the same piece by repeatedly stepping to a tile that shares a full edge with the current one. The rules of the game are: A piece may only be placed so that each of its tiles exactly covers one cell of the board. A piece may be rotated by any multiple of 90 degrees, but it may not be flipped over (reflected). No two pieces may cover the same cell. No piece may extend beyond the edge of the board. Every piece must be used exactly once. If, after placing all the pieces, the board is completely covered with no overlaps and no gaps, the pieces form a