/[cmucl]/src/benchmarks/gabriel/puzzle.c
ViewVC logotype

Contents of /src/benchmarks/gabriel/puzzle.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.1 - (show annotations)
Mon Dec 17 19:47:48 1990 UTC (23 years, 4 months ago) by ram
Branch: MAIN
CVS Tags: sparc-tramp-assem-base, double-double-array-base, post-merge-intl-branch, release-19b-pre1, release-19b-pre2, merged-unicode-utf16-extfmt-2009-06-11, double-double-init-sparc-2, unicode-utf16-extfmt-2009-03-27, double-double-base, snapshot-2007-09, snapshot-2007-08, snapshot-2008-08, snapshot-2008-09, ppc_gencgc_snap_2006-01-06, sse2-packed-2008-11-12, snapshot-2008-05, snapshot-2008-06, snapshot-2008-07, snapshot-2007-05, snapshot-2008-01, snapshot-2008-02, snapshot-2008-03, intl-branch-working-2010-02-19-1000, snapshot-2006-11, snapshot-2006-10, double-double-init-sparc, snapshot-2006-12, unicode-string-buffer-impl-base, sse2-base, release-20b-pre1, release-20b-pre2, unicode-string-buffer-base, sse2-packed-base, sparc-tramp-assem-2010-07-19, amd64-dd-start, snapshot-2003-10, snapshot-2004-10, release-18e-base, release-19f-pre1, snapshot-2008-12, snapshot-2008-11, intl-2-branch-base, snapshot-2004-08, snapshot-2004-09, remove_negative_zero_not_zero, snapshot-2007-01, snapshot-2007-02, snapshot-2004-05, snapshot-2004-06, snapshot-2004-07, release-19e, release-19d, GIT-CONVERSION, double-double-init-ppc, release-19c, dynamic-extent-base, unicode-utf16-sync-2008-12, LINKAGE_TABLE, release-19c-base, cross-sol-x86-merged, label-2009-03-16, release-19f-base, PRE_LINKAGE_TABLE, merge-sse2-packed, mod-arith-base, sparc_gencgc_merge, merge-with-19f, snapshot-2004-12, snapshot-2004-11, intl-branch-working-2010-02-11-1000, unicode-snapshot-2009-05, unicode-snapshot-2009-06, amd64-merge-start, ppc_gencgc_snap_2005-12-17, double-double-init-%make-sparc, unicode-utf16-sync-2008-07, release-18e-pre2, unicode-utf16-sync-2008-09, unicode-utf16-extfmts-sync-2008-12, prm-before-macosx-merge-tag, cold-pcl-base, RELEASE_20b, snapshot-2008-04, snapshot-2003-11, snapshot-2005-07, unicode-utf16-sync-label-2009-03-16, RELEASE_19f, snapshot-2007-03, release-20a-base, cross-sol-x86-base, unicode-utf16-char-support-2009-03-26, unicode-utf16-char-support-2009-03-25, release-19a-base, unicode-utf16-extfmts-pre-sync-2008-11, snapshot-2008-10, sparc_gencgc, snapshot-2007-04, snapshot-2010-12, snapshot-2010-11, unicode-utf16-sync-2008-11, snapshot-2007-07, snapshot-2011-09, snapshot-2011-06, snapshot-2011-07, snapshot-2011-04, snapshot-2007-06, snapshot-2011-02, snapshot-2011-03, snapshot-2011-01, snapshot-2003-12, release-19a-pre1, release-19a-pre3, release-19a-pre2, pre-merge-intl-branch, release-19a, UNICODE-BASE, double-double-array-checkpoint, double-double-reader-checkpoint-1, release-19d-base, release-19e-pre1, double-double-irrat-end, release-19e-pre2, snapshot-2010-05, snapshot-2010-04, snapshot-2010-07, snapshot-2010-06, snapshot-2010-01, snapshot-2010-03, snapshot-2010-02, release-19d-pre2, release-19d-pre1, snapshot-2010-08, release-18e, double-double-init-checkpoint-1, double-double-reader-base, label-2009-03-25, snapshot-2005-03, release-19b-base, cross-sol-x86-2010-12-20, double-double-init-x86, sse2-checkpoint-2008-10-01, intl-branch-2010-03-18-1300, snapshot-2005-11, double-double-sparc-checkpoint-1, snapshot-2004-04, sse2-merge-with-2008-11, sse2-merge-with-2008-10, snapshot-2005-10, RELEASE_20a, snapshot-2005-12, release-20a-pre1, snapshot-2005-01, snapshot-2009-11, snapshot-2009-12, unicode-utf16-extfmt-2009-06-11, portable-clx-import-2009-06-16, unicode-utf16-string-support, release-19c-pre1, cross-sparc-branch-base, release-19e-base, intl-branch-base, double-double-irrat-start, snapshot-2005-06, snapshot-2005-05, snapshot-2005-04, ppc_gencgc_snap_2005-05-14, snapshot-2005-02, unicode-utf16-base, portable-clx-base, snapshot-2005-09, snapshot-2005-08, lisp-executable-base, snapshot-2009-08, snapshot-2007-12, snapshot-2007-10, snapshot-2007-11, snapshot-2009-02, snapshot-2009-01, snapshot-2009-07, snapshot-2009-05, snapshot-2009-04, snapshot-2006-02, snapshot-2006-03, release-18e-pre1, snapshot-2006-01, snapshot-2006-06, snapshot-2006-07, snapshot-2006-04, snapshot-2006-05, pre-telent-clx, snapshot-2006-08, snapshot-2006-09, HEAD
Branch point for: release-19b-branch, double-double-reader-branch, double-double-array-branch, mod-arith-branch, RELEASE-19F-BRANCH, portable-clx-branch, sparc_gencgc_branch, cross-sparc-branch, RELEASE-20B-BRANCH, unicode-string-buffer-branch, sparc-tramp-assem-branch, dynamic-extent, UNICODE-BRANCH, release-19d-branch, ppc_gencgc_branch, sse2-packed-branch, lisp-executable, RELEASE-20A-BRANCH, amd64-dd-branch, double-double-branch, unicode-string-buffer-impl-branch, intl-branch, release-18e-branch, cold-pcl, unicode-utf16-branch, cross-sol-x86-branch, release-19e-branch, sse2-branch, release-19a-branch, release-19c-branch, intl-2-branch, unicode-utf16-extfmt-branch
File MIME type: text/plain
Initial revision
1 # define size 511
2 # define classMax 3
3 # define typeMax 12
4 # define d 8
5 # define true 1
6 # define false 0
7
8 static int class[typeMax+1];
9 static int pieceCount[classMax+1];
10 static int pieceMax[typeMax+1];
11 static int puzzle[size+1];
12 static int p[typeMax+1][size+1];
13 static int kount,clock;
14
15
16 fit(i,j)
17 int i,j;
18 {
19 register k,plim;
20 plim = pieceMax[i];
21 for (k=0; k <= plim; k++)
22 {
23 if (p[i][k])
24 {
25 if (puzzle[j+k]) return (false);
26 }
27 }
28 return(true);
29 }
30
31 int place (i,j)
32 int i,j;
33 {
34 register k,plim;
35 plim = pieceMax[i];
36 for (k = 0; k <= plim; k++)
37 if (p[i][k]) puzzle[j+k] = true;
38 pieceCount[class[i]] = pieceCount[class[i]] - 1;
39 for (k=j; k <= size; k++)
40 if (!puzzle[k])
41 {
42 return(k);
43 }
44 printf("Puzzle filled.\n");
45 return(0);
46 }
47
48 remove(i,j)
49 int i,j;
50 {
51 register k,plim;
52 plim = pieceMax[i];
53 for (k=0; k<=plim; k++)
54 if (p[i][k]) puzzle[j+k] = false;
55 pieceCount[class[i]] = pieceCount[class[i]] + 1;
56 }
57
58 trial(j)
59 int j;
60 {
61 register i,k;
62 for (i = 0; i <= typeMax; i++)
63 if (pieceCount[class[i]] != 0)
64 if (fit (i, j))
65 {
66 k = place (i, j);
67 if (trial(k)||(k == 0))
68 {
69 /* printf("piece %d at %d\n",i+1,k+1); */
70 kount = kount + 1;
71 return(true);
72 }
73 else remove (i, j);
74 }
75 kount = kount + 1;
76 return(false);
77 }
78
79 main()
80 {
81 register i,j,k,m,n;
82
83 /* printf("starting\n"); */
84
85 for (m = 0; m<=size; m++)
86 puzzle[m] = true;
87
88 for (i=1; i <= 5; i++)
89 for (j=1; j<=5; j++)
90 for (k=1; k<=5 ; k++)
91 puzzle[i+d*(j+d*k)] = false;
92
93 for (i=0;i<=typeMax;i++)
94 for (j=0;j<=size;j++)
95 p[i][j] = false;
96
97 for (i=0;i<=3;i++)
98 for (j=0;j<=1;j++)
99 for (k = 0;k<=0;k++)
100 p[0][i+d*(j+d*k)] = true;
101
102 class[0] = 0;
103 pieceMax[0] = 3+d*1+d*d*0;
104
105 for (i=0;i<=1;i++)
106 for (j=0;j<=0;j++)
107 for (k=0;k<=3;k++)
108 p[1][i+d*(j+d*k)] = true;
109
110 class[1] = 0;
111 pieceMax[1] = 1+d*0+d*d*3;
112
113 for (i=0;i<=0;i++)
114 for (j=0;j<=3;j++)
115 for (k=0;k<=1;k++)
116 p[2][i+d*(j+d*k)] = true;
117
118 class[2] = 0;
119 pieceMax[2] = 0+d*3+d*d*1;
120
121 for (i=0;i<=1;i++)
122 for (j=0;j<=3;j++)
123 for (k=0;k<=0;k++)
124 p[3][i+d*(j+d*k)] = true;
125
126 class[3] = 0;
127 pieceMax[3] = 1+d*3+d*d*0;
128
129 for (i=0;i<=3;i++)
130 for (j=0;j<=0;j++)
131 for (k=0;k<=1;k++)
132 p[4][i+d*(j+d*k)] = true;
133
134 class[4] = 0;
135 pieceMax[4] = 3+d*0+d*d*1;
136
137 for (i=0;i<=0;i++)
138 for (j=0;j<=1;j++)
139 for (k=0;k<=3;k++)
140 p[5][i+d*(j+d*k)] = true;
141
142 class[5] = 0;
143 pieceMax[5] = 0+d*1+d*d*3;
144
145 for (i=0;i<=2;i++)
146 for (j=0;j<=0;j++)
147 for (k=0;k<=0;k++)
148 p[6][i+d*(j+d*k)] = true;
149
150 class[6] = 1;
151 pieceMax[6] = 2+d*0+d*d*0;
152
153 for (i=0;i<=0;i++)
154 for (j=0;j<=2;j++)
155 for (k=0;k<=0;k++)
156 p[7][i+d*(j+d*k)] = true;
157
158 class[7] = 1;
159 pieceMax[7] = 0+d*2+d*d*0;
160
161 for (i=0;i<=0;i++)
162 for (j=0;j<=0;j++)
163 for (k=0;k<=2;k++)
164 p[8][i+d*(j+d*k)] = true;
165
166 class[8] = 1;
167 pieceMax[8] = 0+d*0+d*d*2;
168
169 for (i=0;i<=1;i++)
170 for (j=0;j<=1;j++)
171 for (k=0;k<=0;k++)
172 p[9][i+d*(j+d*k)] = true;
173
174 class[9] = 2;
175 pieceMax[9] = 1+d*1+d*d*0;
176
177 for (i=0;i<=1;i++)
178 for (j=0;j<=0;j++)
179 for (k=0;k<=1;k++)
180 p[10][i+d*(j+d*k)] = true;
181
182 class[10] = 2;
183 pieceMax[10] = 1+d*0+d*d*1;
184
185 for (i=0;i<=0;i++)
186 for (j=0;j<=1;j++)
187 for (k=0;k<=1;k++)
188 p[11][i+d*(j+d*k)] = true;
189
190 class[11] = 2;
191 pieceMax[11] = 0+d*1+d*d*1;
192
193 for (i=0;i<=1;i++)
194 for (j=0;j<=1;j++)
195 for (k=0;k<=1;k++)
196 p[12][i+d*(j+d*k)] = true;
197
198 class[12] = 3;
199 pieceMax[12] = 1+d*1+d*d*1;
200 pieceCount[0] = 13;
201 pieceCount[1] = 3;
202 pieceCount[2] = 1;
203 pieceCount[3] = 1;
204 m = 1+d*(1+d*1);
205 kount = 0;
206
207 if (fit(0, m))
208 {
209 n = place(0, m) ;
210 }
211 else
212 {
213 printf("error 1\n");
214 }
215
216 /* printf("n = %d n\n",n); */
217
218 if (trial(n))
219 {
220 printf("success in %d trials\n", kount);
221 }
222 else
223 {
224 printf("failure\n");
225 }
226
227 /* printf("elapsed user time:\n"); */
228 }
229
230

  ViewVC Help
Powered by ViewVC 1.1.5