How do I keep track of different ways I can structure a 2D array

Question

As of recently I've been trying to get better at algorithms and I've stumbled onto one that I can't seem to solve.

The idea behind the algorithm is to try to find as many different ways as possible to store each object of size K in an array of N*N given certain restraints.

So take this grid right here

.X.X
.XX.
...X
....

There are 6 possible ways to store 4 different objects of sizes 1 - 4

4X.X
4XX1
422X
4333

4X1X
4XX.
422X
4333

3X.X
3XX1
322X
4444

3X1X
3XX.
322X
4444

2X1X
2XX.
333X
4444

2X.X
2XX1
333X
4444

The problem I'm facing is trying to come up with an algorithm that could solve this problem. The first thing that comes to mind is to utilize recursion to find each possible solution for each size, but then I draw a blank. I've also read about backtracking but I can't seem to make it fit this problem even though I feel as if it should be possible by creating some sort of state space tree.

What's a good way to approach this problem? Is there a typical algorithm one would use? I'm not looking to have the problem solved for me but rather having broken down into logical steps if possible.

The original description for the problem can be found here https://vjudge.net/problem/Kattis-minibattleship

Answer 1

This is an example of an exact cover problem. It is NP-complete in general.

There are many algorithms that can solve exact cover problems reasonably efficiently on moderate-sized examples, but Knuth's Algorithm X is probably your best bet.

Answer 2

The most natural solution is probably exactly to use recursive backtracking. Since you haven't told us what difficulty you had in applying that, it's not clear how to help you.

The statespace is the set of all partially-filled out grids. Given a state (a partially filled-out grid), a transition is obtained by picking the lowest-numbered shape that is not already in the grid, picking any valid location and orientation for it, and placing it in the grid there. This yields a state space tree, which can be explored through recursive backtracking (which you can think of as depth-first search in that tree).