\datethis
\def\adj{\mathrel{\!\mathrel-\mkern-8mu\mathrel-\mkern-8mu\mathrel-\!}}
@*Intro. This is an experimental program in which I try to cut a square
into a given number of pieces, in such a way that the pieces can be reassembled
to fill another given shape. (Everything is done pixelwise, without
``diagonal cuts.'') The pieces can be rotated but not flipped over.
I don't insist that the pieces be internally connected.
With change files I can add further restrictions.
The input on |stdin| is a sequence of lines containing
periods and asterisks, where the asterisks mark usable positions.
The number of asterisks should be a perfect square.
The desired number of pieces is a command-line parameter.
@d maxn 32 /* maximum number of input lines and characters per line */
@d maxd 7 /* maximum number of pieces */
@d bufsize maxn+5 /* size of the input buffer */
@c
#include
#include
@@;
int d; /* command-line parameter: the number of colors */
char buf[bufsize];
int maxrow; /* largest row number used in the shape */
int maxcol; /* largest column number used in the shape */
char aname[maxn*maxn][8]; /* symbolic names of the cells in the square */
char bname[maxn*maxn][8]; /* symbolic names of the cells in the shape */
int site[maxn*maxn]; /* where the cells are in the shape */
int vbose; /* level of verbosity */
@;
@;
main (int argc,char*argv[]) {
register int a,b,dd,i,j,k,l,ll,lll,m,n,nn,slack;
@;
@;
@;
@;
}
@ @=
if (argc<2 || sscanf(argv[1],"%d",
&d)!=1) {
fprintf(stderr,"Usage: %s d [verbose] [extra verbose] < foo.dots\n",
argv[0]);
exit(-1);
}
if (d<2 || d>maxd) {
fprintf(stderr,"The number of pieces should be between 2 and %d, not %d!\n",
maxd,d);
exit(-2);
}
vbose=argc-2;
@ @d place(i,j) ((i)*maxn+(j))
@=
for (i=nn=0;;i++) {
if (!fgets(buf,bufsize,stdin)) break;
if (i>=maxn) {
fprintf(stderr,"Recompile me: I allow at most %d lines of input!\n",
maxn);
exit(-3);
}
@;
}
maxrow=i-1;
if (maxrow<0) {
fprintf(stderr,"There was no input!\n");
exit(-666);
}
fprintf(stderr,"OK, I've got a shape with %d lines and %d cells.\n",
i,nn);
for (n=1;n*n=
for (j=0;buf[j] && buf[j]!='\n';j++) {
if (buf[j]=='*') {
if (j>maxcol) {
maxcol=j;
if (j>=maxn) {
fprintf(stderr,"Recompile me: I allow at most %d columns of input!\n",
maxn);
exit(-5);
}
}
site[nn++]=place(i,j);
sprintf(bname[place(i,j)],"%02db%02d",
i,j);
}
}
@*The algorithm. Let's consider a special case of the problem, in order
to build some intuition and clarify the concepts. Suppose the input is
$$\vcenter{\halign{\tt#\hfil\cr
****\cr *..*\cr .***\cr}}$$
and we want to cut the eight cells specified by these asterisks
into $d=2$ pieces that can be assembled into a $3\times3$ square.
You can probably see one way to do the job: Break off the
two cells in the leftmost column, rotate them $90^\circ$, and
stick them into the ``jaws'' of the remaining seven. How can we
get a computer to discover this?
A solution to the general problem can be regarded as a way to color
the square with $d$ colors. The cells of the square are $(i,j)$ for
$0\le i,j=
@;
while (1) {
@;
counta++;
@;
shapenot:@+for (k=d;s[k]==m-1;k--) ;
if (k==0) break;
for (j=s[k]+1;k<=d;k++) s[k]=j;
}
@ @=
for (k=2;k<=d;k++) t[k]=0;
while (1) {
for (k=2;k<=d;k++)
if (s[k]==s[k-1] && t[k]==t[k-1]) goto squarenot;
@;
countb++;
@;
squarenot:@+for (k=d; t[k]==3; k--) t[k]=0;
if (k==1) break;
t[k]++;
}
@ @=
for (m=0,a=1-n;a<=maxrow;a++) for (b=1-n;b<=maxcol;b++) {
for (k=0,i=(a<0?-a:0);i1) fprintf(stderr," S[%d]=(%d,%d)\n",
m,a,b);
shift[m]=place(a,b), bcovered[m++]=k;
}
}
if (vbose) fprintf(stderr,"There are %d legal shifts.\n",
m);
@ @=
for (slack=-nn,k=1;k<=d;k++) slack+=bcovered[s[k]];
if (slack<0) goto shapenot;
for (k=0;k=
for (k=0;k=
char alen[maxn*maxn]; /* how many moves remain at this cell in the square */
char blen[maxn*maxn]; /* how many moves remain at this cell in the shape */
int aa[maxn*maxn][maxd]; /* moves for the square */
int bb[maxn*maxn][maxd]; /* moves for the shape */
int shift[4*maxn*maxn]; /* offsets in the shifts */
int complement; /* offset used for 180-degree rotation */
int bcover[4*maxn*maxn][maxn*maxn]; /* cells covered by the shifts */
int bcovered[4*maxn*maxn]; /* how many cells are covered */
int s[maxd+1]; /* the current sequence of shifts */
int t[maxd+1]; /* the current sequence of rotations */
@*Prematching.
When we've managed to jump through all those hoops, we're left with
a perfect matching problem. And most of the time that matching problem
is quite trivial; so we might as well throw out the easy cases before
trying to do anything fancy.
In most cases some of the moves turn out to be forced, because a
cell of the square has only one possible shape-mate or vice versa.
We start by making all of those no-brainer moves.
@=
if (vbose>1) @;
@;
countc++;
@;
@;
countd++;
@;
done:
@ @=
{
fprintf(stderr," Trying to match");
for (k=1;k<=d;k++) fprintf(stderr," %d^%d",
s[k],t[k]);
fprintf(stderr,":\n");
for (i=0;i>16);
fprintf(stderr,"\n");
}
}
@ @=
for (acount=i=0;i1) apos[place(i,j)]=acount,alist[acount++]=place(i,j);
else {
l=aa[place(i,j)][0]&0xffff;
if (!blen[l]) goto done; /* that position of the shape is already taken */
acolor[place(i,j)]=bcolor[l]=aa[place(i,j)][0]>>16;
if (blen[l]==1) blen[l]=0;
else @;
}
}
@ Premature optimization is the root of all evil in programming.
Yet I couldn't resist trying to make this program efficient in special cases.
The removal of edges might reduce |alen| to 1 for square cells that are
in the |alist|, thus forcing further moves.
I won't worry about that until later.
@=
{
for (k=0;kdd) debug("ahi");
if (a!=dd) aa[ll][a]=aa[ll][dd];
}
}
blen[l]=0;
}
@ @=
if (acount) {
for (bcount=i=0;i1) bpos[l]=bcount,blist[bcount++]=l;
else {
ll=bb[l][0]&0xffff;
if (!alen[ll]) goto done; /* that position of the square is already taken */
acolor[ll]=bcolor[l]=bb[l][0]>>16;
acount--;
@;
}
}
if (acount!=bcount) debug("count mismatch");
}
@ @=
j=apos[ll];
if (j!=acount)
lll=alist[acount], alist[j]=lll, apos[lll]=j;
if (alen[ll]!=1) {
for (k=0;kdd) debug("bhi");
if (b!=dd) bb[lll][b]=bb[lll][dd];
}
}
alen[ll]=0;
}
@ Beware: I'm using |acount| and |bcount| in a somewhat tricky way here:
The old |acount| is kept in |bcount| so that a change can be detected.
(Again I apologize for weak resistance.)
@=
while (acount) {
for (i=0;i;
for (i=0;i;
if (acount==bcount) break;
bcount=acount;
}
@ @=
{
acount--;
if (i>16;
@;
}
@ @=
j=bpos[l];
if (jdd) debug("chi");
if (a!=dd) aa[lll][a]=aa[lll][dd];
}
}
}
@ @=
{
acount--;
if (i>16;
@;
}
@ @=
int alist[maxn*maxn], blist[maxn*maxn]; /* list of cells not yet matched */
int apos[maxn*maxn], bpos[maxn*maxn]; /* inverses of those lists */
int acount,bcount; /* the lengths of those lists */
int acolor[maxn*maxn], bcolor[maxn*maxn]; /* color patterns in a solution */
unsigned long long count; /* the number of solutions */
unsigned long long counta,countb,countc,countd,counte;
/* the number of times we reached key points */
@*Matching. Sometimes we actually have real work to do.
At first I didn't think the problem would often be challenging.
So I just used brute-force backtracking, \`a~la Algorithm 7.2.2B.
But a surprising number of large subproblems arose. So I'm now implementing
a version of the original dancing links algorithm,
hacked from {\mc DANCE}.
@=
if (acount==0) @@;
else {
@;
counte++;
if (vbose>1) @;
@;
@;
}
@ @=
{
fprintf(stderr," which reduces to:\n");
for (i=0;i>16);
fprintf(stderr,"\n");
}
}
@ The {\mc DANCE} program was developed to solve exact cover problems,
and bipartite matching is a particularly easy case of that problem:
Every column to be covered is a primary column, and every row specifies
exactly two primary columns.
Each column of the exact cover matrix is represented by a \&{column} struct,
and each row is represented as a linked list of \&{node} structs. There's one
node for each nonzero entry in the matrix.
More precisely, the nodes are linked circularly within each row, in
both directions. The nodes are also linked circularly within each column;
the column lists each include a header node, but the row lists do not.
Column header nodes are part of a \&{column} struct, which
contains further info about the column.
Each node contains six fields. Four are the pointers of doubly linked lists,
already mentioned; the fifth points to the column containing the node;
the sixth ties this node to the dissection problem we're solving.
@s col_struct int
@=
typedef struct node_struct {
struct node_struct *left,*right; /* predecessor and successor in row */
struct node_struct *up,*down; /* predecessor and successor in column */
struct col_struct *col; /* the column containing this node */
int info; /* square position, shape position, and color of this edge */
} node;
@ Each \&{column} struct contains five fields:
The |head| is a node that stands at the head of its list of nodes;
the |len| tells the length of that list of nodes, not counting the header;
the |name| is a user-specified identifier;
|next| and |prev| point to adjacent columns, when this
column is part of a doubly linked list.
As backtracking proceeds, nodes
will be deleted from column lists when their row has been blocked by
other rows in the partial solution.
But when backtracking is complete, the data structures will be
restored to their original state.
@=
typedef struct col_struct {
node head; /* the list header */
int len; /* the number of non-header items currently in this column's list */
char* name; /* symbolic identification of the column, for printing */
struct col_struct *prev,*next; /* neighbors of this column */
} column;
@ One |column| struct is called the root. It serves as the head of the
list of columns that need to be covered, and is identifiable by the fact
that its |name| is empty.
@d root col_array[0] /* gateway to the unsettled columns */
@=
register column *cur_col;
register node *cur_node;
@ @d max_cols (2*maxn*maxn)
@d max_nodes (maxn*maxn*maxn*maxn*maxd)
@=
column col_array[max_cols+2]; /* place for column records */
node node_array[max_nodes]; /* place for nodes */
column *acol[maxn*maxn], *bcol[maxn*maxn];
node *choice[maxn*maxn]; /* the row and column chosen on each level */
@ @=
for (i=0;inext=&root;
for (cur_col=col_array+1;cur_col<=root.prev;cur_col++) {
cur_col->head.up=cur_col->head.down=&cur_col->head;
cur_col->len=0;
cur_col->prev=cur_col-1, (cur_col-1)->next=cur_col;
}
for (cur_node=node_array,i=0;i;
}
@ @=
{
register column *ccol;
l=aa[ll][k]&0xffff;
j=((aa[ll][k]>>16)<<24)+(l<<12)+ll;
ccol=acol[ll];
cur_node->left=cur_node->right=cur_node+1;
cur_node->col=ccol,cur_node->info=j;
cur_node->up=ccol->head.up, ccol->head.up->down=cur_node;
ccol->head.up=cur_node, cur_node->down=&ccol->head;
ccol->len++;
cur_node++;
ccol=bcol[l];
cur_node->left=cur_node->right=cur_node-1;
cur_node->col=ccol,cur_node->info=j;
cur_node->up=ccol->head.up, ccol->head.up->down=cur_node;
ccol->head.up=cur_node, cur_node->down=&ccol->head;
ccol->len++;
cur_node++;
}
@ Our strategy for generating all exact covers will be to repeatedly
choose always the column that appears to be hardest to cover, namely the
column with shortest list, from all columns that still need to be covered.
And we explore all possibilities via depth-first search.
The neat part of this algorithm is the way the lists are maintained.
Depth-first search means last-in-first-out maintenance of data structures;
and it turns out that we need no auxiliary tables to undelete elements from
lists when backing up. The nodes removed from doubly linked lists remember
their former neighbors, because we do no garbage collection.
The basic operation is ``covering a column.'' This means removing it
from the list of columns needing to be covered, and ``blocking'' its
rows: removing nodes from other lists whenever they belong to a row of
a node in this column's list.
@=
level=0;
forward: @;
cover(best_col);
cur_node=choice[level]=best_col->head.down;
advance:if (cur_node==&(best_col->head)) goto backup;
if (vbose>1)
fprintf(stderr,"L%d: %s %s\n",
level,cur_node->col->name,cur_node->right->col->name);
@;
if (root.next==&root) @;
level++;
goto forward;
backup: uncover(best_col);
if (level==0) goto done;
level--;
cur_node=choice[level];@+best_col=cur_node->col;
recover: @;
cur_node=choice[level]=cur_node->down;@+goto advance;
@ @=
register int level;
register column *best_col; /* column chosen for branching */
@ When a row is blocked, it leaves all lists except the list of the
column that is being covered. Thus a node is never removed from a list
twice.
@=
cover(c)
column *c;
{@+register column *l,*r;
register node *rr,*nn,*uu,*dd;
register k=1; /* updates */
l=c->prev;@+r=c->next;
l->next=r;@+r->prev=l;
for (rr=c->head.down;rr!=&(c->head);rr=rr->down)
for (nn=rr->right;nn!=rr;nn=nn->right) {
uu=nn->up;@+dd=nn->down;
uu->down=dd;@+dd->up=uu;
k++;
nn->col->len--;
}
}
@ Uncovering is done in precisely the reverse order. The pointers thereby
execute an exquisitely choreo\-graphed dance which returns them almost
magically to their former state.
@=
uncover(c)
column *c;
{@+register column *l,*r;
register node *rr,*nn,*uu,*dd;
for (rr=c->head.up;rr!=&(c->head);rr=rr->up)
for (nn=rr->left;nn!=rr;nn=nn->left) {
uu=nn->up;@+dd=nn->down;
uu->down=dd->up=nn;
nn->col->len++;
}
l=c->prev;@+r=c->next;
l->next=r->prev=c;
}
@ @=
cover(cur_node->right->col);
@ We included |left| links, thereby making the rows doubly linked, so
that columns would be uncovered in the correct LIFO order in this
part of the program. (The |uncover| routine itself could have done its
job with |right| links only.) (Think about it.)
(Thus the present implementation is overkill, for the special
case of bipartite matching.)
@=
uncover(cur_node->left->col);
@ @=
minlen=max_nodes;
if (vbose>2) fprintf(stderr,"Level %d:",level);
for (cur_col=root.next;cur_col!=&root;cur_col=cur_col->next) {
if (vbose>2) fprintf(stderr," %s(%d)",cur_col->name,cur_col->len);
if (cur_col->lenlen;
}
if (vbose>2) fprintf(stderr," branching on %s(%d)\n",best_col->name,minlen);
@ @=
register int minlen;
register int j,k,x;
@ @=
{
if (vbose>1) fprintf(stderr,"(a good dance)\n");
for (k=0;k<=level;k++) {
j=choice[k]->info;
acolor[j&0xfff]=bcolor[(j>>12)&0xfff]=j>>24;
}
@;
goto recover;
}
@ @=
{
register int OK=1; /* this (declaration facilitates change files) */
if (OK) {
count++;
printf("Solution %lld, from",
count);
for (k=1;k<=d;k++) printf(" %d^%d",
s[k],t[k]);
printf(":\n");
for (i=0;i=
fprintf(stderr,"%lld solutions; run stats %d,%lld,%lld,%lld,%lld,%lld.\n",
count,m,counta,countb,countc,countd,counte);
@ @=
void debug(char*s) {
fflush(stdout);
fprintf(stderr,"***%s!\n",
s);
}
@*Index.