puzzle.h

   1 /* Copyright (c) 2006 Scott Gasch
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #ifndef _PUZZLE_H_
  17 #define _PUZZLE_H_
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21
  22 typedef unsigned long ULONG;
  23 typedef unsigned long BITV;
  24 typedef unsigned long COOR;
  25 #define RANDOM_COOR (rand() % 81)
  26 typedef unsigned long BOOL;
  27
  28 #if 0
  29 #define ASSERT(x)                  if (x)    \
  30                                    { ; }     \
  31                                    else      \
  32                                    { _assert(__FILE__, __LINE__); }
  33 #define VERIFY(x)                  ASSERT(x)
  34 #else
  35 #define ASSERT(x)                      ;
  36 #define VERIFY(x)                  x;
  37 #endif // DEBUG
  38
  39 #ifdef PERF_COUNTERS
  40 #define INC(x)                     ((x) += 1)
  41 #else
  42 #define INC(x)
  43 #endif
  44
  45 typedef struct _SQUARE
  46 {
  47     BITV bvPossibilities;
  48     ULONG uValue;
  49     ULONG cCol;
  50     ULONG cRow;
  51     ULONG cGroup;
  52 } SQUARE;
  53
  54 //
  55 //  0  1  2    3  4  5    6  7  8
  56 //  9 10 11   12 13 14   15 16 17
  57 // 18 19 20   21 22 23   24 25 26
  58 //
  59 // 27 28 29   30 31 32   33 34 35
  60 // 36 37 38   39 40 41   42 43 44
  61 // 45 46 47   48 49 50   51 52 53
  62 //
  63 // 54 55 56   57 58 59   60 61 62
  64 // 63 64 65   66 67 68   69 70 71
  65 // 72 73 74   75 76 77   78 79 80
  66 //
  67 COOR g_cGroup[81] = {
  68     0, 0, 0, 1, 1, 1, 2, 2, 2,
  69     0, 0, 0, 1, 1, 1, 2, 2, 2,
  70     0, 0, 0, 1, 1, 1, 2, 2, 2,
  71     3, 3, 3, 4, 4, 4, 5, 5, 5,
  72     3, 3, 3, 4, 4, 4, 5, 5, 5,
  73     3, 3, 3, 4, 4, 4, 5, 5, 5,
  74     6, 6, 6, 7, 7, 7, 8, 8, 8,
  75     6, 6, 6, 7, 7, 7, 8, 8, 8,
  76     6, 6, 6, 7, 7, 7, 8, 8, 8
  77 };
  78
  79 COOR g_cSquareByGroup[9][9] =
  80 {
  81     {  0,  1,  2,  9, 10, 11, 18, 19, 20 },
  82     {  3,  4,  5, 12, 13, 14, 21, 22, 23 },
  83     {  6,  7,  8, 15, 16, 17, 24, 25, 26 },
  84     { 27, 28, 29, 36, 37, 38, 45, 46, 47 },
  85     { 30, 31, 32, 39, 40, 41, 48, 49, 50 },
  86     { 33, 34, 35, 42, 43, 44, 51, 52, 53 },
  87     { 54, 55, 56, 63, 64, 65, 72, 73, 74 },
  88     { 57, 58, 59, 66, 67, 68, 75, 76, 77 },
  89     { 60, 61, 62, 69, 70, 71, 78, 79, 80 }
  90 };
  91
  92 #define IS_EMPTY(x) ((x) == 0)
  93 #define COL(c) ((c) % 9)
  94 #define FIRST_OF_COL(c) (c)
  95 #define ROW(c) ((c) / 9)
  96 #define FIRST_OF_ROW(c) ((c) * 9)
  97 #define FOREACH_ROW(c, r) \
  98     for((c) = FIRST_OF_ROW(r); (c) < FIRST_OF_ROW((r) + 1); (c)++)
  99 #define FOREACH_COL(c, f) \
 100     for((c) = FIRST_OF_COL(f); (c) < 81; (c) += 9)
 101 #define FOREACH_GROUP(c, g, x) \
 102     for((x) = 0, (c) = g_cSquareByGroup[(g)][(x)]; \
 103         (x) < 9; \
 104         (x)++, (c) = g_cSquareByGroup[(g)][(x)])
 105 #define FOREACH_SQUARE(x) \
 106     for((x) = 0; (x) < 81; (x)++)
 107 COOR g_cGroupsByRow[9][3] =
 108 {
 109     { 0, 1, 2 },
 110     { 0, 1, 2 },
 111     { 0, 1, 2 },
 112     { 3, 4, 5 },
 113     { 3, 4, 5 },
 114     { 3, 4, 5 },
 115     { 6, 7, 8 },
 116     { 6, 7, 8 },
 117     { 6, 7, 8 }
 118 };
 119
 120 COOR g_cRowsByGroup[9][3] =
 121 {
 122     { 0, 1, 2 },
 123     { 0, 1, 2 },
 124     { 0, 1, 2 },
 125     { 3, 4, 5 },
 126     { 3, 4, 5 },
 127     { 3, 4, 5 },
 128     { 6, 7, 8 },
 129     { 6, 7, 8 },
 130     { 6, 7, 8 }
 131 };
 132
 133 COOR g_cGroupsByCol[9][3] =
 134 {
 135     { 0, 3, 6 },
 136     { 0, 3, 6 },
 137     { 0, 3, 6 },
 138     { 1, 4, 7 },
 139     { 1, 4, 7 },
 140     { 1, 4, 7 },
 141     { 2, 5, 8 },
 142     { 2, 5, 8 },
 143     { 2, 5, 8 }
 144 };
 145
 146 COOR g_cColsByGroup[9][3] =
 147 {
 148     { 0, 1, 2 },
 149     { 3, 4, 5 },
 150     { 6, 7, 8 },
 151     { 0, 1, 2 },
 152     { 3, 4, 5 },
 153     { 6, 7, 8 },
 154     { 0, 1, 2 },
 155     { 3, 4, 5 },
 156     { 6, 7, 8 }
 157 };
 158
 159 typedef struct _POSITION
 160 {
 161     SQUARE rgSquare[81];
 162     BITV bvRemainingByGroup[9];
 163     BITV bvRemainingByCol[9];
 164     BITV bvRemainingByRow[9];
 165     ULONG uEmpty;
 166 } POSITION;
 167
 168 #define ONE_BIT(x) (((x) & (x - 1)) == 0)
 169
 170 #define TRUE (1)
 171 #define FALSE (0)
 172
 173 #endif /* _PUZZLE_H_ */