#include <stdio.h>
#include <memory.h>
#include <time.h>
#define BLOCK_SIZE 3
#define MAP_SIZE (BLOCK_SIZE * BLOCK_SIZE)
#define DETERMINED(cell) (!((cell) & ((cell)-1)))
#define GROUP_NUM (MAP_SIZE * 3)
#define CELL_ALL (((cell_t)1 << MAP_SIZE) - (cell_t)1)
#define UPDATED (1U<<0)
#define UNSOLVED (1U<<1)
#define IMPOSSIBLE (1U<<2)
typedef unsigned long cell_t;
typedef unsigned status_t;
cell_t g_map[MAP_SIZE * MAP_SIZE][MAP_SIZE * MAP_SIZE];
int g_group[GROUP_NUM][MAP_SIZE];
void init_map (cell_t map[])
{
static const unsigned initial[MAP_SIZE * MAP_SIZE] = {
// >>231の超難問
0, 0, 0, 0, 0, 0, 0, 1, 0,
4, 0, 0, 0, 0, 0, 0, 0, 0,
0, 2, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 5, 0, 4, 0, 7,
0, 0, 8, 0, 0, 0, 3, 0, 0,
0, 0, 1, 0, 9, 0, 0, 0, 0,
3, 0, 0, 4, 0, 0, 2, 0, 0,
0, 5, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 8, 0, 6, 0, 0, 0,
/*
// >>213
#define BLOCK_SIZE 5
0, 0, 0, 0, 3, 0, 13, 0, 0, 0, 0, 6, 10, 18, 17, 11, 0, 14, 0, 20, 0, 9, 0, 24, 22,
4, 0, 0, 17, 13, 0, 8, 21, 0, 0, 0, 12, 23, 0, 20, 10, 2, 1, 3, 0, 0, 15, 16, 19, 0,
0, 5, 0, 11, 7, 0, 0, 6, 15, 16, 0, 3, 2, 0, 0, 12, 0, 22, 9, 0, 0, 0, 25, 0, 18,
0, 8, 18, 16, 0, 14, 0, 0, 0, 23, 0, 1, 0, 24, 0, 19, 0, 0, 17, 21, 0, 0, 0, 0, 11,
14, 0, 23, 0, 0, 3, 0, 0, 25, 2, 8, 0, 0, 0, 0, 0, 4, 0, 0, 7, 0, 0, 0, 13, 17,
2, 0, 1, 10, 16, 19, 6, 0, 0, 22, 18, 0, 25, 0, 0, 17, 21, 0, 13, 0, 0, 0, 14, 0, 0,
3, 0, 0, 0, 24, 0, 5, 14, 0, 15, 0, 11, 4, 23, 0, 0, 0, 0, 7, 0, 25, 16, 0, 0, 0,
0, 0, 0, 15, 0, 0, 0, 1, 18, 0, 13, 0, 9, 0, 10, 0, 22, 24, 0, 0, 7, 21, 0, 20, 8,
0, 0, 0, 19, 0, 0, 12, 20, 9, 25, 0, 24, 0, 14, 0, 6, 0, 0, 5, 16, 11, 4, 15, 18, 13,
0, 13, 0, 18, 23, 24, 21, 0, 2, 7, 5, 22, 0, 16, 0, 0, 0, 0, 0, 12, 17, 0, 9, 0, 0,
0, 0, 0, 22, 0, 5, 17, 25, 0, 0, 0, 0, 0, 21, 11, 1, 20, 0, 0, 0, 0, 10, 23, 0, 4,
24, 0, 6, 0, 0, 0, 18, 0, 4, 0, 7, 14, 0, 19, 0, 0, 8, 23, 16, 0, 13, 0, 0, 0, 5,
10, 16, 15, 0, 0, 2, 7, 8, 22, 0, 0, 0, 0, 17, 5, 9, 18, 0, 19, 0, 1, 0, 3, 0, 0,
20, 23, 0, 0, 12, 21, 0, 9, 0, 14, 2, 0, 0, 0, 22, 0, 13, 3, 11, 6, 0, 0, 0, 7, 0,
11, 0, 21, 25, 19, 10, 0, 0, 23, 0, 0, 0, 0, 20, 24, 0, 0, 17, 0, 15, 0, 0, 8, 2, 6,
8, 9, 22, 0, 0, 11, 19, 15, 24, 20, 17, 16, 0, 0, 13, 18, 0, 10, 21, 0, 0, 0, 4, 0, 0,
0, 12, 0, 1, 20, 25, 0, 18, 10, 0, 23, 7, 0, 0, 3, 0, 5, 9, 14, 4, 0, 0, 0, 0, 0,
0, 17, 25, 0, 0, 0, 0, 0, 0, 0, 0, 5, 1, 8, 4, 0, 12, 7, 0, 13, 16, 11, 0, 0, 24,
16, 0, 0, 21, 0, 0, 0, 0, 13, 0, 0, 15, 22, 0, 6, 3, 19, 25, 23, 0, 5, 0, 7, 8, 2,
0, 6, 0, 0, 10, 0, 22, 0, 0, 3, 0, 0, 0, 25, 2, 0, 0, 0, 15, 0, 21, 19, 0, 12, 0,
9, 0, 16, 13, 14, 1, 25, 0, 0, 0, 12, 8, 0, 15, 0, 7, 0, 0, 2, 22, 0, 0, 17, 3, 19,
0, 1, 10, 0, 0, 0, 9, 16, 7, 19, 0, 0, 24, 0, 14, 20, 0, 15, 0, 17, 0, 0, 5, 0, 0,
17, 22, 7, 0, 2, 0, 20, 4, 0, 12, 0, 19, 0, 0, 21, 25, 14, 6, 1, 8, 0, 0, 0, 23, 0,
23, 0, 5, 0, 0, 15, 0, 11, 21, 0, 0, 25, 0, 4, 0, 0, 0, 0, 0, 24, 14, 22, 6, 10, 0,
0, 0, 3, 0, 25, 0, 0, 0, 5, 13, 0, 17, 0, 0, 23, 0, 0, 0, 0, 19, 12, 7, 18, 0, 1,
*/
};
int p;
for (p = 0; p < MAP_SIZE * MAP_SIZE; p ++) {
if (initial[p] == 0) {
map[p] = CELL_ALL;
} else {
map[p] = (cell_t)1 << (initial[p] - 1);
}
}
}
void init_group ()
{
int g = 0;
int x, y;
// horizontal groups
for (y = 0; y < MAP_SIZE; y ++) {
for (x = 0; x < MAP_SIZE; x ++) {
g_group[g][x] = y * MAP_SIZE + x;
}
g ++;
}
// vertical groups
for (x = 0; x < MAP_SIZE; x ++) {
for (y = 0; y < MAP_SIZE; y ++) {
g_group[g][y] = y * MAP_SIZE + x;
}
g ++;
}
// block groups
for (y = 0; y < BLOCK_SIZE; y ++) {
for (x = 0; x < BLOCK_SIZE; x ++) {
int xx, yy, i = 0;
for (yy = 0; yy < BLOCK_SIZE; yy ++) {
for (xx = 0; xx < BLOCK_SIZE; xx ++) {
g_group[g][i++] = (y*BLOCK_SIZE+yy) * MAP_SIZE + (x*BLOCK_SIZE+xx);
}
}
g ++;
}
}
}
unsigned to_value (cell_t cell) // cell must be determined
{
unsigned v;
for (v = 0; cell; v ++) cell >>= 1;
return v;
}
void disp_map (const cell_t map[])
{
int x, y;
for (y = 0; y < MAP_SIZE; y ++) {
for (x = 0; x < MAP_SIZE; x ++) {
cell_t cell = map[y * MAP_SIZE + x];
if (DETERMINED (cell)) {
printf ("%3d", to_value (cell));
} else {
printf (" _");
}
}
printf ("\n");
}
}
status_t solve_group (cell_t map[], int group[])
{
status_t status = 0;
cell_t candidate = CELL_ALL;
int i;
for (i = 0; i < MAP_SIZE; i ++) {
cell_t cell = map[group[i]];
if (DETERMINED (cell)) {
if (candidate & cell) {
candidate &= ~cell;
} else {
status |= IMPOSSIBLE; // duplicated
}
}
}
if (status & IMPOSSIBLE) {
return status;
}
for (i = 0; i < MAP_SIZE; i ++) {
cell_t* pcell = &map[group[i]];
cell_t cell = *pcell;
if (!DETERMINED (cell)) {
if ((cell & candidate) != cell) {
*pcell = (cell &= candidate);
if (cell) {
status |= UPDATED;
if (!DETERMINED (cell)) {
status |= UNSOLVED;
}
} else {
status |= IMPOSSIBLE; // no candidate
}
} else {
status |= UNSOLVED;
}
}
}
return status;
}
status_t solve_simple (cell_t map[])
{
status_t status, updated = 0;
int i;
do {
status = 0;
for (i = 0; i < GROUP_NUM; i ++) {
status |= solve_group (map, g_group[i]);
}
updated |= status & UPDATED;
} while (!(status & IMPOSSIBLE) && (status & UPDATED));
return status | updated;
}
int bitcount (cell_t cell, int limit)
{
int c;
for (c = 0; cell && c < limit; c ++) {
cell &= cell-1;
}
return c;
}
status_t solve (cell_t map[])
{
status_t status;
cell_t cell, supposed;
do {
status = solve_simple (map);
if (status & IMPOSSIBLE) {
return status;
}
if (status & UNSOLVED) {
int min_count = MAP_SIZE*MAP_SIZE, min_pos, count, pos;
for (pos = 0; pos < MAP_SIZE*MAP_SIZE && min_count > 2; pos ++) {
if (!DETERMINED (map[pos])) {
count = bitcount (map[pos], min_count);
if (count < min_count) {
min_count = count;
min_pos = pos;
}
}
}
pos = min_pos;
for (cell = map[pos]; supposed = (cell & -cell); cell ^= supposed) { // for each candidate
cell_t* map_new = map + MAP_SIZE * MAP_SIZE;
status_t status_new;
memcpy (map_new, map, sizeof (cell_t) * MAP_SIZE * MAP_SIZE);
map_new[pos] = supposed;
status_new = solve (map_new);
if (status_new & IMPOSSIBLE) {
if (!(map[pos] ^= supposed)) {
return IMPOSSIBLE; // no candidates
}
status |= UPDATED;
break;
} else if (!(status_new & UNSOLVED)) {
memcpy (map, map_new, sizeof (cell_t) * MAP_SIZE * MAP_SIZE);
return status_new;
}
}
}
} while (status & UPDATED);
return status;
}
int main()
{
const int repeat = 64;
int i;
clock_t start, end;
int status;
init_map (g_map[0]);
printf ("before:\n"); disp_map (g_map[0]);
start = clock ();
for (i = 0; i < repeat; i ++) {
init_map (g_map[0]);
init_group ();
status = solve (g_map[0]);
}
end = clock ();
if (status & UNSOLVED) {
printf ("unsolved.\n");
} else {
printf ("solved.\n");
}
printf ("after:\n"); disp_map (g_map[0]);
printf ("average time=%fsec\n", (double)(end - start) / CLOCKS_PER_SEC / repeat);
return 0;
}