Lecture 18 ECE264F12Lu - Rhea

John Ribeiro - Lecture 18

A square refers to a single building block the composes a piece. A piece refers to a compilation of multiple squares.

Duplicates are formed through:

Rotation Mirroring

Suppose you want to generate pieces of n squares:

1) Break n into the sum of positive integers. Each integer is the number of squares in each row. 2) Shift the squares to create different pieces 3) Eliminate Duplicates

void f ( int n ) { int i; if ( n == 0 ) {

 return;

} for ( i = 1 ; i < n ; i ++ ) {

 f ( n - i );

} }

That means that each integer can be partitioned into its components, for example,

4 = 1 + 3 4 = 2 + 2 4 = 3 + 1 4 = 4

For each n integer, there will be n partitions

This algorithm will not generate a non-continuous piece

NOT:

xox oxo xox

OR:

oxo oxo ooo

BUT:

ooo oxx ooo

• Where o denotes a block and x an empty space.

Lecture notes_Lecture18_Mar 20_Kailu Song

1. The explanation of program 2

  a. the square and piece(one piece have several square)
  b. duplicates: rotate the piece will generate another duplicate piece
  c. rotation mirror: horizontal mirror and vertical mirror
  e. invalid piece: there is a space between two square in one row(eg.010 101 010)
  For this assignment, give the number of squares, generate all picecs(delete invalid piece, deplicate piece and mirror piece) using one dimensional array.

2. Hint for this assignment:

  first stage: partition integers:
  ex. 4 = 1+1+1+1
      4 = 1+1+2
      4 = 1+2+1
      4 = 1+3
      4 = 2+2...
  Use recursion
  void f(int n)
  {
    int i;
    if (n==0)
      {
          return;
      }
     if (i=1;i<n;i++)
      {
        f(n-i);
      }
  }