Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 600c74c8d0
595 lines (548 sloc) 16.987 kb
/*
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
Copyright © 2009 Andrew Brown <brownan@gmail.com>
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "edgetable.h"
#include "cube.h"
#include "stack.h"
/*
* This file holds two edge hashing functions. For any six of the twelve edge
* cubies, there are 42577920 possible permutations. There are two hash
* functions, one for the first 6 edge cubies, and another for the second.
*
* There will be two tables, both are admissible heuristics for solving the
* cube.
*
* I'd like to try and find a generalized way of hashing an arbitrary subset of
* cubies, but I don't think it's feasable. So I just need to write a new
* function for every subset.
*/
/*
* This hashes the edge cubies
* 1, 3, 4, 6, 8, and 9
*/
int edge_hash1(const char *cubestr)
{
char positions[] = {1, 3, 4, 6, 8, 9, 10, 11, 13, 15, 16, 18};
int index = 0;
int pos, rot, num, i;
const char *cubie;
/*
* First split hash space (42577920) into 24 slices:
* 1774080
* then into 22 slices:
* 80640
* and so forth (each cubie eliminates 2 positions):
* 4032
* 224
* 14
* 1
*/
/* first */
cubie = CUBIE(cubestr, 1);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<11; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 12;
/*
* pos is range 0-11
* rot is 0 or 12
* so pos+rot has range 0-23 as expected
*/
index += (pos+rot) * 1774080;
#ifdef DEBUG_ASSERTS
if (pos>11 || (rot != 0 && rot != 12)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
fprintf(stderr, "Pos: %d, Rot: %d\n", pos, rot);
fprintf(stderr, "Cubie[] = [%d, %d]\n", (int)cubie[0], (int)cubie[1]);
cube_print(stderr, cubestr);
fprintf(stderr, "Positions:\n");
for (i=0; i<12; ++i)
fprintf(stderr, "%d ", positions[i]);
index = *((int *)0x0); /* sigsev */
}
#endif
/* second */
cubie = CUBIE(cubestr, 3);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<10; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 11;
/*
* pos is range 0-10
* rot is 0 or 11
* so pos+rot has range 0-21
*/
index += (pos+rot) * 80640;
#ifdef DEBUG_ASSERTS
if (pos>10 || (rot != 0 && rot != 11)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
/* third */
cubie = CUBIE(cubestr, 4);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<9; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 10;
/*
* pos is range 0-9
* rot is 0 or 10
* so pos+rot has range 0-19
*/
index += (pos+rot) * 4032;
#ifdef DEBUG_ASSERTS
if (pos>9 || (rot != 0 && rot != 10)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
/* fourth */
cubie = CUBIE(cubestr, 6);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<8; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 9;
/*
* pos is range 0-8
* rot is 0 or 9
* so pos+rot has range 0-17
*/
index += (pos+rot) * 224;
#ifdef DEBUG_ASSERTS
if (pos>8 || (rot != 0 && rot != 9)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
/* fifth */
cubie = CUBIE(cubestr, 8);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<7; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 8;
/*
* pos is range 0-7
* rot is 0 or 8
* so pos+rot has range 0-15
*/
index += (pos+rot) * 14;
#ifdef DEBUG_ASSERTS
if (pos>7 || (rot != 0 && rot != 8)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
/* sixth */
cubie = CUBIE(cubestr, 9);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<6; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 7;
/*
* pos is range 0-6
* rot is 0 or 7
* so pos+rot has range 0-13
*/
index += (pos+rot);
#ifdef DEBUG_ASSERTS
if (pos>6 || (rot != 0 && rot != 7)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
#ifdef DEBUG_ASSERTS
if (index >= 42577920) {
fprintf(stderr, "\nWARNING: HASH RETURNED %d\n", index);
index = *((int *)0x0); /* sigsev */
}
#endif
return index;
}
/*
* This hashes the edge cubies
* 10, 11, 13, 15, 16, and 18
*/
int edge_hash2(const char *cubestr)
{
char positions[] = {1, 3, 4, 6, 8, 9, 10, 11, 13, 15, 16, 18};
int index = 0;
int pos, rot, num, i;
const char *cubie;
/*
* First split hash space (42577920) into 24 slices:
* 1774080
* then into 22 slices:
* 80640
* and so forth (each cubie eliminates 2 positions):
* 4032
* 224
* 14
* 1
*/
/* first */
cubie = CUBIE(cubestr, 10);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<11; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 12;
/*
* pos is range 0-11
* rot is 0 or 12
* so pos+rot has range 0-23 as expected
*/
index += (pos+rot) * 1774080;
#ifdef DEBUG_ASSERTS
if (pos>11 || (rot != 0 && rot != 12)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
fprintf(stderr, "Pos: %d, Rot: %d\n", pos, rot);
fprintf(stderr, "Cubie[] = [%d, %d]\n", (int)cubie[0], (int)cubie[1]);
cube_print(stderr, cubestr);
fprintf(stderr, "Positions:\n");
for (i=0; i<12; ++i)
fprintf(stderr, "%d ", positions[i]);
index = *((int *)0x0); /* sigsev */
}
#endif
/* second */
cubie = CUBIE(cubestr, 11);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<10; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 11;
/*
* pos is range 0-10
* rot is 0 or 11
* so pos+rot has range 0-21
*/
index += (pos+rot) * 80640;
#ifdef DEBUG_ASSERTS
if (pos>10 || (rot != 0 && rot != 11)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
/* third */
cubie = CUBIE(cubestr, 13);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<9; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 10;
/*
* pos is range 0-9
* rot is 0 or 10
* so pos+rot has range 0-19
*/
index += (pos+rot) * 4032;
#ifdef DEBUG_ASSERTS
if (pos>9 || (rot != 0 && rot != 10)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
/* fourth */
cubie = CUBIE(cubestr, 15);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<8; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 9;
/*
* pos is range 0-8
* rot is 0 or 9
* so pos+rot has range 0-17
*/
index += (pos+rot) * 224;
#ifdef DEBUG_ASSERTS
if (pos>8 || (rot != 0 && rot != 9)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
/* fifth */
cubie = CUBIE(cubestr, 16);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<7; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 8;
/*
* pos is range 0-7
* rot is 0 or 8
* so pos+rot has range 0-15
*/
index += (pos+rot) * 14;
#ifdef DEBUG_ASSERTS
if (pos>7 || (rot != 0 && rot != 8)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
/* sixth */
cubie = CUBIE(cubestr, 18);
num = cubie[0]; /* position id on the cube */
/* find its index in the positions array */
pos = 0;
while (num != positions[pos])
++pos;
/* remove that pos from the array */
for (i=pos; i<6; ++i)
positions[i] = positions[i+1];
rot = cubie[1] * 7;
/*
* pos is range 0-6
* rot is 0 or 7
* so pos+rot has range 0-13
*/
index += (pos+rot);
#ifdef DEBUG_ASSERTS
if (pos>6 || (rot != 0 && rot != 7)) {
fprintf(stderr, "\nWARNING: BAD POS/ROT\n");
index = *((int *)0x0); /* sigsev */
}
#endif
#ifdef DEBUG_ASSERTS
if (index >= 42577920) {
fprintf(stderr, "\nWARNING: HASH RETURNED %d\n", index);
index = *((int *)0x0); /* sigsev */
}
#endif
return index;
}
/*
* Similar to corner_generate, this generates the hash table for the edge
* cubies. There are two edge cubie tables to choose from. The tablenum
* variable should specify which table is being generated. Either 1 or 2.
*
* Mostly copied from corner_generate
*/
int edge_generate(unsigned char *table, const char *solution, int tablenum)
{
stacktype *stack;
/*
* qdata is a struct, holding cube string 'cube_data',
* an int representing the turn that was made, 'turn',
* and an int representing the distance, 'distance'
*/
qdata current;
int count = 0; /* total hashed */
int popcount = 0; /* total traversed */
int hash;
int i;
unsigned char *instack;
int depth;
cube_type turned;
/* Which edge hashing function to use */
int (*hashfunc)(const char *);
switch (tablenum) {
case 1:
hashfunc = edge_hash1;
break;
case 2:
hashfunc = edge_hash2;
break;
default:
return 0;
}
/* Create a stack */
stack = STACK_NEW;
/*
* create a temporary table to keep track of the stack This holds the value
* of each item that has been added to the stack, and its distance. This
* way, we know if we encounter the same node but at a further distance we
* can throw it away. This heuristic cuts down on processing time by quite
* a bit, and is only as time intensive as the hashing algorithm, at the
* expense of using more memory.
*/
instack = EDGE_TABLE_NEW;
depth = 0;
while (count < 42577920)
{
/* if stack is empty, go up a level */
if (stack->length == 0)
{
stack_push(stack, solution, -1, 0);
depth++;
/* clear out instack table */
EDGE_TABLE_CLEAR(instack);
}
/* Pop the first item off, put it in current */
stack_peek_cube(stack, &(current.cube_data));
current.turn = stack_peek_turn(stack);
current.distance = stack_peek_distance(stack);
stack_pop(stack);
popcount++;
/* Print out status every 2^18 pops (approx every 200k)*/
if ((popcount & 0777777) == 0777777) {
fprintf(stderr, "\r%d/42577920 hashed, on level:%d/10, total traversed:%d", count, depth, popcount);
}
#ifdef PROFILE_MODE
/* For profiling, so I don't have to wait an hour to gather data */
if (count == 10000000) {
return 0;
}
#endif
/* Look at all turns of the current cube */
for (i=0; i<18; i++) {
/* Determine if we should skip this turn */
if (current.turn != -1 && SHOULDIAVOID(i, current.turn)) {
continue;
}
memcpy(turned, current.cube_data, CUBELEN);
cube_turn(turned, i);
/*
* Check if turned is in instack and is greater than
* or equal to the depth. If so, skip
*/
hash = hashfunc(turned);
if (hash&1 ? \
((instack[(hash-1)/2] >> 4) <= (current.distance+1)) : \
((instack[hash/2] & 15) <= (current.distance+1))) {
continue;
}
/* add to instack */
if (hash&1) {
instack[(hash-1)/2] &= 15;
instack[(hash-1)/2] |= (current.distance+1) << 4;
} else {
instack[hash/2] &= 15<<4;
instack[hash/2] |= (current.distance+1);
}
if (current.distance+1 == depth) {
/*
* if item is at our current target depth, add it to hash table
*/
if (hash & 1) {
if (!(table[(hash-1)/2] >> 4)) {
table[(hash-1)/2] |= (current.distance+1) << 4;
count++;
} else {
/* A duplicate, skip */
}
} else {
if (!(table[hash/2]&15)) {
table[hash/2] |= current.distance + 1;
count++;
} else {
/* a duplicate */
}
}
} else {
/* Add to real stack */
stack_push(stack, turned, i, current.distance+1);
}
}
}
/*
* This sets the value for the solved cube to 0, as it should be. This
* exceptional case comes about because there are moves which don't change
* the hash (this table only involves 6 of the 12 edge cubies.) Therefore,
* an edge is turned, and while the edge cubies are still "solved", an
* entry is inserted in the table with distance 1, which ruins the
* admissibility of the heuristic.
*
* This wasn't an issue with the corner table because every turn from the
* solved state brought it to an unsolved state (unlike this table). So
* the 18 cubes that are 1 position away from solved go into the 'instack'
* table, which prevents the search from coming back to the solved state.
* The 18 moves around the solved state form a kind of barrier.
*/
hash = hashfunc(cube_solved);
if (hash & 1) {
/* zero out upper bits */
table[(hash-1)/2] &= 15;
} else {
/* zero out lower bits */
table[hash/2] &= (15<<4);
}
free(instack);
while(stack->length) {
stack_pop(stack);
}
free(stack);
fprintf(stderr, "\n");
return 1;
}
int edge_write(unsigned char *edgetable, FILE *output)
{
int written;
written = fwrite(edgetable, 1, 21288960, output);
if (written < 21288960)
return 0;
return 1;
}
int edge_read(unsigned char *edgetable, FILE *input)
{
int read;
read = fread(edgetable, 1, 21288960, input);
if (read < 21288960) {
return 0;
}
return 1;
}
Jump to Line
Something went wrong with that request. Please try again.