Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

The Goal

Your task is to carefully arrange all the given polyominoes to perfectly fill the predefined shape. Rotate and flip the pieces as needed, but make sure everything fits!

Rules

You will be given a predefined shape that must be entirely covered using the available polyominoes.

Each polyomino can be rotated by 0°, 90°, 180°, or 270°.
Polyominoes can also be flipped horizontally or vertically, giving each piece up to 8 possible orientations.
Below is an overview of all polyominoes used in the puzzle:

All available shapes - for example polyomino with id A forms L-like shape

Example

Consider the first test case. You need to use the A and D polyominoes to completely fill the following shape:

OOO OOO O.O

There are two possible solutions:

DAA AAD DDA or ADD D.A A.D

So you should print either one of them.

Additional Info

Background image from Freepik.com
And sources in my Github repo
Have a look at this great tutorial on Algorithm X by Timinator

Game Input

Input

Line 1: ids of remaining polyominoes to place on board for example: ABEFN

Line 2: space separated h - height and w - width of game board

Following lines: h strings of length w representing game board, where

. - must remain unoccupied
O - must be occupied

Output

h lines of length w representing final board where

. - is unoccupied
A-N - as ID of polyomino that covers given cell

Constraints

Maximum of14 ids
2<h,w<20
Allotted response time to output is ≤ 5s

Solve it

A higher resolution is required to access the IDE