API tools faq
paste
Guest User

Untitled

a guest
Jan 24th, 2026
168
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 14.58 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <wchar.h>
  5. #include <errno.h>
  6.  
  7. #define SHOW    1
  8. #define CLEAR   0  
  9. #define LABELS  0
  10.  
  11. int opt_show = SHOW;
  12. int opt_clear = CLEAR;
  13. int opt_labels = LABELS;
  14.  
  15. typedef struct {
  16.     int y;          /* row */
  17.     int x;          /* col */
  18.     int pips;       /* -1 if empty, # of pips if not empty */
  19.     char * group;   /* name of group */
  20.     int neighbors[4];
  21.     int (*constraint)();
  22. } Square;
  23.  
  24. typedef struct {
  25.     int nA;     /* # of pips on A end */
  26.     int nB;     /* # of pips on B end */
  27.     int sA;     /* where A end is placed (-1 if not placed) */
  28.     int sB;     /* where B end is placed (-1 if not placed) */
  29. } Tile;
  30.  
  31. typedef struct {
  32.     char * group;
  33.     int y;
  34.     int x;
  35. } Group_Base;
  36.  
  37. char *** rows = 0;
  38. int solution_count = 0;
  39.  
  40. int c_none();
  41. int c_0_1();
  42. int c_2_8();
  43. int c_3_9();
  44. int c_4_5_6_11_19_25();
  45. int c_7();
  46. int c_10();
  47. int c_12_13_14_15_16_17();
  48. int c_18_24();
  49. int c_20_21();
  50. int c_22_26();
  51. int c_23();
  52. int c_27_31();
  53. int c_28_29();
  54. Group_Base group_base[] = {
  55.   {"12", 0, 1},
  56.   {"6", 1, 6},
  57.   {"4", 1, 7},
  58.   {"=", 4, 1},
  59.   {"0", 1, 5},
  60.   {"0", 2, 0},
  61.   {"=", 2, 7},
  62.   {"=", 4, 0},
  63.   {"=", 3, 4},
  64.   {"5", 4, 6},
  65.   {"0", 3, 7},
  66.   {"=", 5, 7},
  67.   {"12", 5, 1},
  68. };
  69. Square board[32] = {
  70. /* 0*/ {0, 0, -1, "A", { 1,  4, -1, -1}, c_0_1},
  71. /* 1*/ {0, 1, -1, "A", { 0,  5, -1, -1}, c_0_1},
  72. /* 2*/ {0, 6, -1, "B", { 3,  8, -1, -1}, c_2_8},
  73. /* 3*/ {0, 7, -1, "C", { 2,  9, -1, -1}, c_3_9},
  74. /* 4*/ {1, 0, -1, "D", { 0,  5, 10, -1}, c_4_5_6_11_19_25},
  75. /* 5*/ {1, 1, -1, "D", { 1,  4,  6, 11}, c_4_5_6_11_19_25},
  76. /* 6*/ {1, 2, -1, "D", { 5, 12, -1, -1}, c_4_5_6_11_19_25},
  77. /* 7*/ {1, 5, -1, "E", { 8, 15, -1, -1}, c_7},
  78. /* 8*/ {1, 6, -1, "B", { 2,  7,  9, 16}, c_2_8},
  79. /* 9*/ {1, 7, -1, "C", { 3,  8, 17, -1}, c_3_9},
  80. /*10*/ {2, 0, -1, "F", { 4, 11, 18, -1}, c_10},
  81. /*11*/ {2, 1, -1, "D", { 5, 10, 12, 19}, c_4_5_6_11_19_25},
  82. /*12*/ {2, 2, -1, "G", { 6, 11, 13, -1}, c_12_13_14_15_16_17},
  83. /*13*/ {2, 3, -1, "G", {12, 14, 20, -1}, c_12_13_14_15_16_17},
  84. /*14*/ {2, 4, -1, "G", {13, 15, 21, -1}, c_12_13_14_15_16_17},
  85. /*15*/ {2, 5, -1, "G", { 7, 14, 16, -1}, c_12_13_14_15_16_17},
  86. /*16*/ {2, 6, -1, "G", { 8, 15, 17, 22}, c_12_13_14_15_16_17},
  87. /*17*/ {2, 7, -1, "G", { 9, 16, 23, -1}, c_12_13_14_15_16_17},
  88. /*18*/ {3, 0, -1, "H", {10, 19, 24, -1}, c_18_24},
  89. /*19*/ {3, 1, -1, "D", {11, 18, 25, -1}, c_4_5_6_11_19_25},
  90. /*20*/ {3, 3, -1, "I", {13, 21, -1, -1}, c_20_21},
  91. /*21*/ {3, 4, -1, "I", {14, 20, -1, -1}, c_20_21},
  92. /*22*/ {3, 6, -1, "J", {16, 23, 26, -1}, c_22_26},
  93. /*23*/ {3, 7, -1, "K", {17, 22, 27, -1}, c_23},
  94. /*24*/ {4, 0, -1, "H", {18, 25, 28, -1}, c_18_24},
  95. /*25*/ {4, 1, -1, "D", {19, 24, 29, -1}, c_4_5_6_11_19_25},
  96. /*26*/ {4, 6, -1, "J", {22, 27, 30, -1}, c_22_26},
  97. /*27*/ {4, 7, -1, "L", {23, 26, 31, -1}, c_27_31},
  98. /*28*/ {5, 0, -1, "M", {24, 29, -1, -1}, c_28_29},
  99. /*29*/ {5, 1, -1, "M", {25, 28, -1, -1}, c_28_29},
  100. /*30*/ {5, 6, -1, " ", {26, 31, -1, -1}, c_none},
  101. /*31*/ {5, 7, -1, "L", {27, 30, -1, -1}, c_27_31},
  102. };
  103. #define ROWS 6
  104. #define COLS 8
  105. #define SQ0 board[0].pips
  106. #define SQ1 board[1].pips
  107. #define SQ2 board[2].pips
  108. #define SQ3 board[3].pips
  109. #define SQ4 board[4].pips
  110. #define SQ5 board[5].pips
  111. #define SQ6 board[6].pips
  112. #define SQ7 board[7].pips
  113. #define SQ8 board[8].pips
  114. #define SQ9 board[9].pips
  115. #define SQ10 board[10].pips
  116. #define SQ11 board[11].pips
  117. #define SQ12 board[12].pips
  118. #define SQ13 board[13].pips
  119. #define SQ14 board[14].pips
  120. #define SQ15 board[15].pips
  121. #define SQ16 board[16].pips
  122. #define SQ17 board[17].pips
  123. #define SQ18 board[18].pips
  124. #define SQ19 board[19].pips
  125. #define SQ20 board[20].pips
  126. #define SQ21 board[21].pips
  127. #define SQ22 board[22].pips
  128. #define SQ23 board[23].pips
  129. #define SQ24 board[24].pips
  130. #define SQ25 board[25].pips
  131. #define SQ26 board[26].pips
  132. #define SQ27 board[27].pips
  133. #define SQ28 board[28].pips
  134. #define SQ29 board[29].pips
  135. #define SQ30 board[30].pips
  136. #define SQ31 board[31].pips
  137. int c_none()
  138. {
  139.   return 1;
  140. }
  141. int c_0_1()
  142. {
  143.   if (SQ0 == -1 || SQ1 == -1) return 1;
  144.   if (SQ0 + SQ1 == 12) return 1;
  145.   else return 0;
  146. }
  147. int c_2_8()
  148. {
  149.   if (SQ2 == -1 || SQ8 == -1) return 1;
  150.   if (SQ2 + SQ8 == 6) return 1;
  151.   else return 0;
  152. }
  153. int c_3_9()
  154. {
  155.   if (SQ3 == -1 || SQ9 == -1) return 1;
  156.   if (SQ3 + SQ9 == 4) return 1;
  157.   else return 0;
  158. }
  159. int c_4_5_6_11_19_25()
  160. {
  161.   if (SQ4 == -1 || SQ5 == -1 || SQ6 == -1 || SQ11 == -1 || SQ19 == -1 || SQ25 == -1) return 1;
  162.   if (SQ4 == SQ5 && SQ4 == SQ6 && SQ4 == SQ11 && SQ4 == SQ19 && SQ4 == SQ25) return 1;
  163.   else return 0;
  164. }
  165. int c_7()
  166. {
  167.   if (SQ7 == -1) return 1;
  168.   if (SQ7 == 0) return 1;
  169.   else return 0;
  170. }
  171. int c_10()
  172. {
  173.   if (SQ10 == -1) return 1;
  174.   if (SQ10 == 0) return 1;
  175.   else return 0;
  176. }
  177. int c_12_13_14_15_16_17()
  178. {
  179.   if (SQ12 == -1 || SQ13 == -1 || SQ14 == -1 || SQ15 == -1 || SQ16 == -1 || SQ17 == -1) return 1;
  180.   if (SQ12 == SQ13 && SQ12 == SQ14 && SQ12 == SQ15 && SQ12 == SQ16 && SQ12 == SQ17) return 1;
  181.   else return 0;
  182. }
  183. int c_18_24()
  184. {
  185.   if (SQ18 == -1 || SQ24 == -1) return 1;
  186.   if (SQ18 == SQ24) return 1;
  187.   else return 0;
  188. }
  189. int c_20_21()
  190. {
  191.   if (SQ20 == -1 || SQ21 == -1) return 1;
  192.   if (SQ20 == SQ21) return 1;
  193.   else return 0;
  194. }
  195. int c_22_26()
  196. {
  197.   if (SQ22 == -1 || SQ26 == -1) return 1;
  198.   if (SQ22 + SQ26 == 5) return 1;
  199.   else return 0;
  200. }
  201. int c_23()
  202. {
  203.   if (SQ23 == -1) return 1;
  204.   if (SQ23 == 0) return 1;
  205.   else return 0;
  206. }
  207. int c_27_31()
  208. {
  209.   if (SQ27 == -1 || SQ31 == -1) return 1;
  210.   if (SQ27 == SQ31) return 1;
  211.   else return 0;
  212. }
  213. int c_28_29()
  214. {
  215.   if (SQ28 == -1 || SQ29 == -1) return 1;
  216.   if (SQ28 + SQ29 == 12) return 1;
  217.   else return 0;
  218. }
  219. Tile tiles[16] = {
  220.   {2, 2, -1, -1},
  221.   {1, 2, -1, -1},
  222.   {4, 4, -1, -1},
  223.   {4, 0, -1, -1},
  224.   {0, 5, -1, -1},
  225.   {3, 5, -1, -1},
  226.   {6, 6, -1, -1},
  227.   {3, 0, -1, -1},
  228.   {3, 2, -1, -1},
  229.   {2, 5, -1, -1},
  230.   {4, 3, -1, -1},
  231.   {3, 6, -1, -1},
  232.   {5, 4, -1, -1},
  233.   {3, 1, -1, -1},
  234.   {4, 6, -1, -1},
  235.   {5, 5, -1, -1},
  236. };
  237.  
  238. void show_tiles_graphic(void);
  239. void show_tiles_text(void);
  240. int place(char * lp, char * cp, int pos);
  241. void solve(int depth);
  242. void draw_square(int y, int x, int pips, int up);
  243. void erase_line(int py, int px, int dy, int dx, int n, char * what);
  244. void draw_tile(int y, int x, int pips1, int pips2,
  245.     char * g1, char * g2,  int dir);
  246. void label_square(int y, int x, char * label);
  247.  
  248.  
  249. int main(int argc, char *argv[]) {
  250.     for (int i = 1; i < argc; ++i) {
  251.         if (strcmp(argv[i], "-c") == 0) { opt_clear = 1; }
  252.         if (strcmp(argv[i], "-l") == 0) { opt_labels = 1; }
  253.         if (strcmp(argv[i], "-q") == 0) { opt_show = 0; }
  254.     }
  255.     solve(0);
  256.     printf("Solutions: %d\n", solution_count);
  257.     return 0;
  258. }
  259.  
  260. #define TL "┌"
  261. #define TR "┐"
  262. #define BL "└"
  263. #define BR "┘"
  264. #define TT "┬"
  265. #define BT "┴"
  266. #define LT "├"
  267. #define RT "┤"
  268. #define HL "─"
  269. #define VL "│"
  270. #define CC "┼"
  271. #define PIP "◎";
  272.  
  273. #define SQ_X 7
  274. #define SQ_Y 3
  275.  
  276. #define PIX_X ((SQ_X+1)*COLS+1)
  277. #define PIX_Y ((SQ_Y+1)*ROWS+1)
  278.  
  279. #define PX 2
  280. #define PY 1
  281.  
  282. void show_tiles_text(void)
  283. {
  284.     char * sep = "";
  285.     for (int t = 0; t < sizeof tiles / sizeof(Tile); ++t) {
  286.         printf("%s%d/%d(%d,%d)", sep, tiles[t].nA, tiles[t].nB,
  287.             tiles[t].sA, tiles[t].sB);
  288.         sep = " ";
  289.     }
  290.     printf("\n");
  291. }
  292.  
  293. void show_tiles_graphic(void)
  294. {
  295.     static int inited = 0;
  296.     printf("board is %d rows x %d cols\n", PIX_Y, PIX_X);
  297.     if (! inited) rows = (char ***)malloc(PIX_Y * sizeof(char *));
  298.     for (int i = 0; i < PIX_Y; ++i) {
  299.         char ** line = inited ? rows[i] : (char **)malloc(PIX_X * sizeof(char *));
  300.         for (int j = 0; j < PIX_X; ++j) {
  301.             line[j] = " ";
  302.         }
  303.         rows[i] = line;
  304.     }
  305.     inited = 1;
  306.  
  307.     for (int t = 0; t < sizeof tiles / sizeof(Tile); ++t) {
  308.         int dir = 0;
  309.         int rA = board[tiles[t].sA].y;
  310.         int cA = board[tiles[t].sA].x;
  311.         int nA = tiles[t].nA;
  312.         char * gA = board[tiles[t].sA].group;
  313.         int rB = board[tiles[t].sB].y;
  314.         int cB = board[tiles[t].sB].x;
  315.         int nB = tiles[t].nB;
  316.         char * gB = board[tiles[t].sB].group;
  317.  
  318.         if (rA > rB) dir = 0;
  319.         else if (rA < rB) dir = 2;
  320.         else if (cA < cB) dir = 3;
  321.         else dir = 1;
  322.  
  323.         draw_tile(rA, cA, nA, nB, gA, gB, dir);
  324.     }
  325.     if (opt_labels) {
  326.         for (int i = 0; i < sizeof group_base / sizeof(group_base[0]); ++i) {
  327.             label_square(group_base[i].y, group_base[i].x, group_base[i].group);
  328.         }
  329.     }
  330.  
  331.     for (int i = 0; i < PIX_Y; ++i) {
  332.         for (int j = 0; j < PIX_X; ++j) {
  333.             printf("%s", rows[i][j]);
  334.         }
  335.         putchar('\n');
  336.     }
  337.     putchar('\n');
  338.     if (opt_clear) {
  339.         exit(0);
  340.     }
  341. }
  342.  
  343. void label_square(int y, int x, char * label)
  344. {
  345.     int px = 1 + x * (SQ_X + 1);
  346.     int py = 1 + y * (SQ_Y + 1);
  347.     int n = strlen(label);
  348.     if (n == 1) {
  349.         rows[py + SQ_Y][px + SQ_X] = label;
  350.     } else {
  351.         for (int i = 0; i < n; ++i) {
  352.             char * one = (char *)malloc(2); //TODO: when does this get freed?
  353.             one[0] = label[i];
  354.             one[1] = '\0';
  355.             rows[py + SQ_Y][px + SQ_X + i] = one;
  356.         }
  357.     }
  358. }
  359.  
  360. /* dir: 0 == up, 1 == left, 2 == down, 3 == right */
  361. void draw_tile(int y, int x, int pips1, int pips2,
  362.     char * g1, char * g2,  int dir)
  363. {
  364.     if (opt_clear) {
  365.         pips1 = pips2 = 0;
  366.     }
  367.     char * what = (strcmp(g1, g2) == 0) ? " " : ".";
  368.     int px = 1 + x * (SQ_X + 1);
  369.     int py = 1 + y * (SQ_Y + 1);
  370.     draw_square(y, x, pips1, (dir == 0 || dir == 2) ? 1 : 0);
  371.  
  372.     switch (dir) {
  373.         case 0: --y; break;
  374.         case 1: --x; break;
  375.         case 2: ++y; break;
  376.         case 3: ++x; break;
  377.     }
  378.  
  379.     int px2 = 1 + x * (SQ_X + 1);
  380.     int py2 = 1 + y * (SQ_Y + 1);
  381.     draw_square(y, x, pips2, (dir == 0 || dir == 2) ? 1 : 0);
  382.  
  383.     switch (dir) {
  384.         case 0:    
  385.             erase_line(py-1, px, 0, 1, 7, what);
  386.             break;
  387.         case 1:
  388.            erase_line(py, px-1, 1, 0, 3, what);
  389.             break;
  390.         case 2:
  391.            erase_line(py2-1, px, 0, 1, 7, what);
  392.             break;
  393.         case 3:
  394.            erase_line(py2, px2-1, 1, 0, 3, what);
  395.             break;
  396.     }
  397. }
  398.  
  399. void erase_line(int py, int px, int dy, int dx, int n, char * what)
  400. {
  401.     if (! opt_clear) {
  402.         while (n-- > 0) {
  403.             if (px > 0 && py > 0)
  404.                 rows[py][px] = what;
  405.             else {
  406.                 printf("Internal error: out of bounds\n");
  407.                 exit(1);
  408.             }
  409.             py += dy;
  410.             px += dx;
  411.         }
  412.     }
  413. }
  414.  
  415. void draw_square(int y, int x, int pips, int up)
  416. {
  417.     int i, j;
  418.     x = 1 + x * (SQ_X + 1);
  419.     y = 1 + y * (SQ_Y + 1);
  420.     for (i = y; i < y+SQ_Y; ++i)
  421.     for (j = x; j < x+SQ_X; ++j)
  422.         rows[i][j] = " ";
  423.  
  424.     // frame top and bottom
  425.     for (j = x; j < x+SQ_X; ++j) {
  426.         rows[y-1][j] = HL;
  427.         rows[y+SQ_Y][j] = HL;
  428.     }
  429.     // frame the sides
  430.     for (i = y; i < y+SQ_Y; ++i) {
  431.         rows[i][x-1] = VL;
  432.         rows[i][x+SQ_X] = VL;
  433.     }
  434.     // corners
  435.     rows[y-1][x-1] = TL;
  436.     rows[y+SQ_Y][x-1] = BL;
  437.     rows[y+SQ_Y][x+SQ_X] = BR;
  438.     rows[y-1][x+SQ_X] = TR;
  439.  
  440.     x += 1;
  441.     switch (pips) {
  442.         case 1:
  443.             rows[y+PY][x+PX] = PIP;
  444.             break;
  445.         case 2:
  446.             if (up) {
  447.                 rows[y][x] = PIP;
  448.                 rows[y+2*PY][x+2*PX] = PIP;
  449.             } else {
  450.                 rows[y][x+2*PX] = PIP;
  451.                 rows[y+2*PY][x] = PIP;
  452.             }
  453.             break;
  454.         case 3:
  455.             rows[y+PY][x+PX] = PIP;
  456.             if (up) {
  457.                 rows[y][x] = PIP;
  458.                 rows[y+2*PY][x+2*PX] = PIP;
  459.             } else {
  460.                 rows[y][x+2*PX] = PIP;
  461.                 rows[y+2*PY][x] = PIP;
  462.             }
  463.             break;
  464.         case 4:
  465.             rows[y][x] = PIP;
  466.             rows[y+2*PY][x] = PIP;
  467.             rows[y][x+2*PX] = PIP;
  468.             rows[y+2*PY][x+2*PX] = PIP;
  469.             break;
  470.         case 5:
  471.             rows[y+PY][x+PX] = PIP;
  472.             rows[y][x] = PIP;
  473.             rows[y+2*PY][x] = PIP;
  474.             rows[y][x+2*PX] = PIP;
  475.             rows[y+2*PY][x+2*PX] = PIP;
  476.             break;
  477.         case 6:
  478.             if (up) {
  479.                 rows[y][x] = PIP;
  480.                 rows[y+PY][x] = PIP;
  481.                 rows[y+2*PY][x] = PIP;
  482.                 rows[y][x+2*PX] = PIP;
  483.                 rows[y+PY][x+2*PX] = PIP;
  484.                 rows[y+2*PY][x+2*PX] = PIP;
  485.             } else {
  486.                 rows[y][x] = PIP;
  487.                 rows[y][x+PX] = PIP;
  488.                 rows[y][x+2*PX] = PIP;
  489.                 rows[y+2*PY][x] = PIP;
  490.                 rows[y+2*PY][x+PX] = PIP;
  491.                 rows[y+2*PY][x+2*PX] = PIP;
  492.             }
  493.             break;
  494.     }
  495. }
  496.  
  497. void indent(int depth)
  498. {
  499.     if (depth > 0) {
  500.         for (int i = 0; i < 2*depth; ++i) putchar('_');
  501.     }
  502. }
  503.  
  504. void solve(int depth)
  505. {
  506.     int sq;
  507.     int i;
  508.     int t;
  509.  
  510.  
  511.     /* find an empty square */
  512.     sq = sizeof board / sizeof(Square);
  513.     while (--sq >= 0) {
  514.         if (board[sq].pips == -1) break;
  515.     }
  516.     if ( sq < 0) {
  517.         ++solution_count;
  518.         if (opt_show) {
  519.             show_tiles_graphic();
  520.             show_tiles_text();
  521.         }
  522.         return;
  523.     }
  524.  
  525.     for (i = 0; i < 4; ++i) {
  526.         int ad = board[sq].neighbors[i];
  527.         if (ad >= 0 && board[ad].pips == -1) {
  528.             for (t = 0; t < sizeof tiles / sizeof(Tile); ++t) {
  529.                 if (tiles[t].sA != -1) continue;
  530.                 board[sq].pips = tiles[t].nA;
  531.                 board[ad].pips = tiles[t].nB;
  532.                 tiles[t].sA = sq;
  533.                 tiles[t].sB = ad;
  534.                 //indent(depth); printf("Try %d%d on %d/%d\n", board[sq].pips, board[ad].pips, sq, ad);
  535.                 if ((*board[sq].constraint)() && (*board[ad].constraint)()) {
  536.                     solve(depth+1);
  537.                 }
  538.                 if (tiles[t].nA != tiles[t].nB) {
  539.                     board[sq].pips = tiles[t].nB;
  540.                     board[ad].pips = tiles[t].nA;
  541.                     tiles[t].sB = sq;
  542.                     tiles[t].sA = ad;
  543.                     //indent(depth); printf("Try %d%d on %d/%d\n", board[sq].pips, board[ad].pips, sq, ad);
  544.                     if ((*board[sq].constraint)() && (*board[ad].constraint)()) {
  545.                         solve(depth+1);
  546.                     }
  547.                 }
  548.                 board[sq].pips = -1;
  549.                 board[ad].pips = -1;
  550.                 tiles[t].sA = -1;
  551.                 tiles[t].sB = -1;
  552.             }
  553.         }
  554.     }
  555. }
  556.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!