Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include "dlx.h"
- typedef struct {
- const char *name;
- int width;
- int height;
- int (*pieces)[4];
- } puzinfo;
- #include "pieces.h"
- int main(int argc, char *argv[]) {
- puzinfo *p;
- int i, j, rownum=0, size, pos, pos2=0, piecenum, row, col, width, height, rot, edgebits=0, edges[4], edge, edge2;
- // Initialize a new exact cover instance.
- dlx_t dlx = dlx_new();
- char *puz_name = argv[1];
- for(i=0;;i++) {
- if(!strcmp(pi[i].name, puz_name)) {
- p = &pi[i];
- break;
- }
- }
- width = p->width;
- height = p->height;
- printf("width = %d\n", p->width);
- printf("height = %d\n", p->height);
- size = p->width * p->height;
- // count the edgebits
- j = 0;
- for (piecenum=0; piecenum<size; piecenum++) {
- for (i=0; i<4; i++) {
- if (p->pieces[piecenum][i] > j) {
- j = p->pieces[piecenum][i];
- }
- }
- }
- printf("max edge = %d\n", j);
- while (j > 0) {
- edgebits++;
- j /= 2;
- }
- printf("edge bits = %d\n", edgebits);
- char **rownames = calloc(size*size*4, sizeof(char *));
- for (pos = 0; pos < size; pos++) {
- row = pos / width;
- col = pos % width;
- for (piecenum = 0; piecenum < size; piecenum++) {
- for (i=0; i<4; i++) {
- edges[i] = p->pieces[piecenum][i];
- }
- for (rot=0; rot<4; rot++) {
- if (((pos == 0) == (piecenum == 0)) &&
- (((edges[0] == 0) == (row == 0)) &&
- ((edges[1] == 0) == (col+1 == width)) &&
- ((edges[2] == 0) == (row+1 == height)) &&
- ((edges[3] == 0) == (col == 0)))) {
- // legal piece placement, proceed
- // mark the position occupied
- dlx_set(dlx, rownum, pos);
- printf("dlx_set(dlx, %d, %d);\n", rownum, pos);
- // mark the piece used
- dlx_set(dlx, rownum, size+piecenum);
- printf("dlx_set(dlx, %d, %d);\n", rownum, size+piecenum);
- // mark the edge placement
- for (edge=0; edge<4; edge++) {
- for (j=0; j<edgebits; j++) {
- if ((edges[edge] & (1<<j)) ||
- (edge == 0 && row == 0) ||
- (edge == 1 && col+1 == width) ||
- (edge == 2 && row+1 == height) ||
- (edge == 3 && col == 0)) {
- // mark this edge
- pos2 = pos;
- edge2 = edge;
- } else {
- pos2 = pos + (int []){-width, 1, width, -1}[edge];
- edge2 = (edge + 2) % 4;
- }
- dlx_set(dlx, rownum, size*2 + (pos2*4 + edge2)*edgebits + j);
- printf("dlx_set(dlx, %d, %d);\n", rownum, size*2 + (pos2*4 + edge2)*edgebits + j);
- }
- }
- rownames[rownum] = malloc(32);
- sprintf(rownames[rownum], "%d,%d,%d/%d", row, col, piecenum, rot);
- //printf("pos %d, piece %d/%d\n", pos, piecenum, rot);
- fflush(stdout);
- rownum++;
- } else {
- //printf("skipping pos %d, piece %d/%d\n", pos, piecenum, rot);
- }
- // rotate the piece
- j = edges[3];
- for (i=3; i>0; i--) {
- edges[i] = edges[i-1];
- }
- edges[0] = j;
- }
- }
- }
- printf("row count = %d\n", rownum);
- // Mark the last column as optional.
- //dlx_mark_optional(dlx, 2);
- void f(int row[], int n) {
- printf("Solution: rows:");
- for(int i = 0; i < n; i++) {
- printf(" %s", rownames[row[i]]);
- }
- printf("\n");
- }
- dlx_forall_cover(dlx, f);
- dlx_clear(dlx);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement