void print_partition(int size,int *partition) {
printf("[");
int i;
for (i=0;i<size;i++)
{
printf("%d",partition[i]);
}
printf("]\n");
}
int emptyFirstColumn(char *data,int dim) {
int empty=1;
int i;
for (i=0;i<dim;i++)
{
if (data[i*dim]!='0')empty=0; } return empty;
}
Blokus *gen_row(int row,int prevCol, int size,int *partition, char *data,int dim) {
//base case:gone through all rows
if(row==size)
{if(emptyFirstColumn(data,dim))return NULL;
return Blokus_create(data,dim);
}
// recursive case: we stil have not assigned all blocks in
// this partition
int col;
int start=0;
int stop =dim-partition[row]+1;
if(row!=0)
{
start=prevCol - partition[row]+1;
if(start<0)start=0;
stop=prevCol+partition[row-1];
if (stop + partition[row]>dim)
stop=dim-partition[row]+1;
}
Blokus *head =NULL;
for (col=start;col<stop;col++)
{
memset(data+row*dim,'0',sizeof(char)* dim);
memset(data+row*dim+col,'1',sizeof(char)*partition[row]);
Blokus *list= gen_row(row+1,col,size,partition,data,dim);
head=BlokusL_append(head,list);
} return head;
}
Blokus *gen_shifts(int *partition,int size, int dim)
{
char *data=malloc(sizeof(char)*dim*dim); memset(data,'0',sizeof(char)*dim*dim); Blokus *list= gen_row(0,0,size,partition,data,dim);
free(data); return list;
}
Blokus *gen_partition(int budget, int pos, int *partition,int dim)
{
//base case:no more budget spin spin everything
if(budget==0)
{print_partition(pos,partition);
Blokus *list=gen_shifts(partition,pos,dim);
return list;
}
//recursive case:we have budget
Blokus *head =NULL;
int spending;
for (spending=1;spending<=budget;spending++)
{
partition[pos]=spending;
Blokus *list= gen_partition(budget-spending,pos+1,partition,dim);
head =BlokusL_append(head,list);
}
return head;
} Blokus *make_unique(Blokus*head) {
return head;
}
Blokus *generate_pieces(int n)
{
int *partition=malloc(sizeof(int)*n); // step 1+2:partition+shift valid Blokus *head =gen_partition(n,0,partition,n); // step 3:uniqueness
head =make_unique(head);
free(partition);
return head;
}
int main(int argc, char *argv[])
{
if(argc !=2)
{
return EXIT_FAILURE;
}
int n=strtol(argv[1],NULL,10); Blokus *head = generate_pieces(n); BlokusL_print(head); BlokusL_destroy(head);
return EXIT_SUCCESS;
}
