我需要写一个程序,它将获取一组块块并将它们排列,如果可能的话,形成一个4 x 4网格的正方形。
棋子可以是4 × 4网格内的任何形状。如果不可能,我应该返回null。
输入: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}})
输出:该方法将返回4x4矩阵的正方形网格作为
2 1 1 1
2 3 3 3
2 3 4 3
2 4 4 4
请参阅此处的输出说明
这个谜题与著名的八皇后谜题非常相似,所以查找那个问题,看看它是如何解决的,并尝试将这些新知识应用到这个谜题中。
主要的区别是你的方块有一个比皇后更复杂的形状,但其余的都是一样的。
解决方案的基本成分是以下任务的方法:
- 某个块是否适合网格上的某个位置?
- 将某个块放置在网格上的某个位置。
- 从它在网格上的位置拿走一个特定的块。
当您为这三个任务编写方法时,您只需要一些回溯,就完成了。
就用蛮力吧。尝试所有可能的位置,看看他们是否工作。NxN网格的一般问题是np完备的,所以这几乎是你能得到的最好的解决方案。