Question:
A traditional russion square is made by 4 blocks, and has 7 different patterns.
Given N blocks, how many different patterns would be.
N = 1, P# = 1
N = 2, P# = 1
N = 3, P# = 3
N = 4, P# = 7.
Assume N = k, P# = Pk
then when N = k+1, P# = for each P in Pk, append one more block around P, remove dups.
class Pattern
{
List<Block> blocks;
// Return true if this pattern can be translated to another patter p by rotate or moving.
boolean isSame(Pattern p)
{
// TODO
}
}
List<Pattern> allPatthens(n)
{
if (n == 1)
{
return Pattern.builder().build();
}
List<Pattern> patternsForNMinusOne = numOfPattern(n - 1);
List<Pattern> toReturn = new ArrayList<>();
for (Pattern p : patternsForNMinus1)
{
List<Pattern> patternsWithOneMoreBlock = patternsWithOneMoreBlock(p);
for (Pattern newP : patternsWithOneMoreBlock)
{
if (!contains(toReturn, newP))
{
toReturn.add(newP);
}
}
}
return toReturn;
}
boolean contains(List<Pattern> list, Pattern p)
{
for (Pattern pInList : list)
{
if (pInList.isSame(p))
return true;
}
return false;
}
// Given pattern p.
// Return all unique valid patterns with one more block.
List<Pattern> patternsWithOneMoreBlock(Pattern p)
{
List<Pattern> toReturn = new ArrayList<>();
for (Block b : p.blocks())
{
List<Block> newBlocks = Arrays.as(b.left(), b.right(), b.up(), b.down());
for (Block newBlock : newBlocks)
{
if (!p.contains(newBlock))
{
// A new pattern found
Pattern newP = p.appendBlock(newBlock);
if (!contains(toReturn, newP))
{
toReturn.add(newP);
}
}
}
}
return toReturn;
}
// Too complicated.all possible patterns for N russian squares
原文：http://7371901.blog.51cto.com/7361901/1589958