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