Program which will take an array of block pieces and arrange them, if possible, to form a square in 4 x 4 grid

I need to write a program, which will take an array of block pieces and arrange them, if possible, to form a square in 4 x 4 grid.

The pieces could be of any shape within开发者_运维技巧 4 X 4 grid. If it is not possible I should return null.

Input :

Blocks[] pieces = new Blocks[4]
pieces[0] = new Blocks(1, new int[][]{{1, 1, 1}})
pieces[1] = new Blocks(2, new int[][]{{1, 0}, {1, 0}, {1, 0}, {1, 0}})
pieces[2] = new Blocks(3, new int[][]{{1, 1, 1}, {1, 0, 1}})
pieces[3] = new Blocks(4, new int[][]{{0, 1, 0}, {1, 1, 1}}) 

Output : The method will return square grid of 4x4 matrix as

2   1   1   1 
2   3   3   3 
2   3   4   3 
2   4   4   4 

Please see the explanation for the output here

---

This puzzle is pretty much the same as the famous eight queens puzzle, so look up that problem, see how it is solved, and try to apply this new knowledge to this puzzle.

The main diffeerence is that your blocks have a more complicated shape than a queen, but the rest is quite the same.

The basic ingredients to the solution are methods for the following tasks:

• does a certain block fit at a certain position on the grid?
• place a certain block at a certain position on the grid.
• take away a certain block from its position on the grid.

When you write methods for these three tasks, you only need some backtracking, and you're done.

---

Just brute-force it. Try all possible positions of the blocks and see if they work. The general problem for an NxN grid is NP-complete so this is pretty much as good of a solution as you'll get.