#include #include /* random(3) */ /* Dimensions of the puzzle grid. */ #define GRID_HEIGHT 15 #define GRID_WIDTH 15 /* How large to display PostScript cells, in points. */ #define PS_CELL_SIZE 20 /* Where on the page to locate the PostScript grid. */ #define PS_LEFT_MARGIN 72 #define PS_TOP_MARGIN 400 #define CELL(p,X,Y) (p[Y*GRID_HEIGHT+X]) void getrands (int p[9]); void populate_grid (int *grid); int check_dupes (int *grid, int x, int y, int candidate); void draw_grid (int *grid); void ps_start_grid (int *grid); void ps_draw_cell (int *grid, int x, int y); void ps_draw_block (int *grid, int x, int y, int hsum, int vsum); void ps_finish_grid (int *grid); void html_start_grid (int *grid); void html_draw_cell (int *grid, int x, int y); void html_draw_block (int *grid, int x, int y, int hsum, int vsum); void html_finish_grid (int *grid); void (*start_grid)(); void (*draw_cell)(); void (*draw_block)(); void (*finish_grid)(); int grid[GRID_HEIGHT*GRID_WIDTH] = { -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1, 0, 0, 0,-1,-1, 0, 0, 0, 0,-1, 0, 0, 0, 0, -1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1, 0, 0, 0, 0, -1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0,-1,-1, 0, 0, 0,-1, 0, 0, 0, -1,-1,-1,-1, 0, 0, 0, 0,-1,-1, 0, 0, 0, 0, 0, -1, 0, 0, 0,-1, 0, 0, 0,-1, 0, 0, 0,-1,-1,-1, -1, 0, 0, 0, 0,-1,-1, 0, 0, 0,-1, 0, 0, 0, 0, -1, 0, 0, 0, 0,-1, 0, 0, 0,-1,-1, 0, 0, 0, 0, -1,-1,-1,-1, 0, 0, 0,-1, 0, 0, 0,-1, 0, 0, 0, -1, 0, 0, 0, 0, 0,-1,-1, 0, 0, 0, 0,-1,-1,-1, -1, 0, 0, 0,-1, 0, 0, 0,-1,-1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1, 0, 0, 0, 0, -1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1, 0, 0, 0, 0, -1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1,-1, 0, 0, 0 }; int main (int argc, char **argv) { start_grid = html_start_grid; draw_cell = html_draw_cell; draw_block = html_draw_block; finish_grid = html_finish_grid; start_grid (grid); populate_grid (grid); draw_grid (grid); finish_grid (grid); } /* * populate_grid * Fill the puzzle grid with random digits, obeying the rule * that no row or column may contain the same digit more than * once. */ void populate_grid (int *grid) { int x, y; for (y = 0; y < GRID_HEIGHT; ++y) { for (x = 0; x < GRID_WIDTH; ++x) { if (CELL(grid,x,y) == 0) { int i, rands[9]; getrands(rands); for (i = 0; i < 9; ++i) { if (check_dupes (grid, x, y, rands[i]) == 0) { CELL(grid,x,y) = rands[i]; break; } } if (CELL(grid,x,y) == 0) { fprintf (stderr, "ERROR: no legal value at (%d,%d)\n", x, y); return; } } } } } /* * Check the row and column at grid[x,y] for duplicate ints. */ int check_dupes (int *grid, int x, int y, int candidate) { int xp, yp; /* Check row number `y'. */ for (xp = x; xp >= 0 && CELL(grid,xp,y) >= 0; --xp) if (CELL(grid,xp,y) == candidate) return -1; for (xp = x+1; xp < GRID_WIDTH && CELL(grid,xp,y) >= 0; ++xp) if (CELL(grid,xp,y) == candidate) return -1; /* Check column number `x'. */ for (yp = y; yp >= 0 && CELL(grid,x,yp) >= 0; --yp) if (CELL(grid,x,yp) == candidate) return -1; for (yp = y+1; yp < GRID_HEIGHT && CELL(grid,x,yp) >= 0; ++yp) if (CELL(grid,x,yp) == candidate) return -1; /* The candidate is cleared. All is right with the world. */ return 0; } /* * Shuffle the numbers from 1 to 9 at random and store them in `p'. */ void getrands (int p[9]) { int i, j, temp; for (i = 0; i < 9; ++i) p[i] = i + 1; for (i = 0; i < 9; ++i) { j = random() % 9; temp = p[j]; p[j] = p[i]; p[i] = temp; } } /* ============================== */ /* Draw the puzzle and/or its key. */ /* * draw_grid * Draw the puzzle grid. This function should be completely generic, * i.e. not depend on any particular graphics system. */ void draw_grid (int *grid) { int x, y; for (y = 0; y < GRID_HEIGHT; ++y) { for (x = 0; x < GRID_WIDTH; ++x) { draw_cell(grid, x, y); if (CELL(grid,x,y) < 0) { int hsum, vsum, xp, yp; hsum = 0; vsum = 0; for (xp = x + 1; xp < GRID_WIDTH && CELL(grid,xp,y) >= 0; ++xp) hsum += CELL(grid,xp,y); for (yp = y + 1; yp < GRID_HEIGHT && CELL(grid,x,yp) >= 0; ++yp) vsum += CELL(grid,x,yp); draw_block (grid, x, y, hsum, vsum); } } } } /* ============================== */ /* * PostScript primitives. */ /* * start_grid * Begin printing the puzzle grid: a preamble, macro definitions, etc. */ void ps_start_grid (int *grid) { puts ("%!PS-Adobe-3.0"); printf ("\n"); } /* * draw_cell * Draw the outline for a puzzle cell. If this is a solution * square, also draw the answer. */ void ps_draw_cell (int *grid, int x, int y) { int xpix = PS_LEFT_MARGIN + (x * PS_CELL_SIZE); int ypix = PS_TOP_MARGIN - (y * PS_CELL_SIZE); printf ("\t0.1 setlinewidth\n\n"); printf ("\t%d %d %d %d rectstroke\n", xpix, ypix, PS_CELL_SIZE, -PS_CELL_SIZE); if (CELL(grid,x,y) > 0) { printf ("\t/TimesRoman 12 selectfont\n"); printf ("\t%d %d moveto 5 -16 rmoveto (%d) show stroke\n", xpix, ypix, CELL(grid,x,y)); } } /* * draw_block * Draw a black square at position (X,Y) in the grid. HSUM * and VSUM are the sums of the row and the column adjacent * to this square. If either one is greater than zero, it * should be printed in white on top of the black square. */ void ps_draw_block (int *grid, int x, int y, int hsum, int vsum) { int xpix = PS_LEFT_MARGIN + (x * PS_CELL_SIZE); int ypix = PS_TOP_MARGIN - (y * PS_CELL_SIZE); printf ("\t%d %d %d %d rectfill\n", xpix, ypix, PS_CELL_SIZE, -PS_CELL_SIZE); if (hsum > 0 || vsum > 0) { printf ("\t\t1 setcolor\n"); printf ("\t\t1 setlinewidth\n"); printf ("\t\t/Helvetica-Demi 8 selectfont\n"); printf ("\t\t%d %d moveto\n", xpix, ypix); printf ("\t\t%d %d rlineto\n", PS_CELL_SIZE, -PS_CELL_SIZE); if (hsum > 0) printf ("\t\t%d 11 add %d 9 sub moveto (%d) show\n", xpix, ypix, hsum); if (vsum > 0) printf ("\t\t%d 2 add %d 18 sub moveto (%d) show\n", xpix,ypix,vsum); printf ("\t\tstroke\n"); printf ("\t\t0 setcolor\n"); } } /* * finish_grid * Finish printing the grid ("showpage", "" or whatever). */ void ps_finish_grid (int *grid) { puts ("showpage"); } /* ============================== */ /* HTML primitives. */ void html_start_grid (int *grid) { puts (""); puts (""); puts (""); } void html_draw_cell (int *grid, int x, int y) { if (x == 0) { if (y > 0) { puts (""); } puts (""); } if (CELL(grid,x,y) > 0) { printf ("", CELL(grid,x,y)); } } void html_draw_block (int *grid, int x, int y, int hsum, int vsum) { printf (""); } void html_finish_grid (int *grid) { puts(""); puts("
%d"); if (hsum > 0 || vsum > 0) { printf (""); if (vsum > 0) printf ("%d", vsum); printf ("\\"); if (hsum > 0) printf ("%d", hsum); printf (""); } else printf (" "); printf ("
"); puts(""); }