/**
* @file
* Code to create and handle the isomorphisms of the game cube.
* Last Modified: Thu May 25 13:03:49 PDT 2017
* @author Kevin O'Gorman
*/
/*
* Copyright 2012-2014,2016 Kevin O'Gorman <kogorman@gmail.com>.
* Distributed under the GNU General Public License.
*
* This file is part of libqubist, the library of functions for playing
* 4x4x4 tic-tac-toe, also known by some other names outside the USA.
*
* Libqubist 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 version 2.
*
* Libqubist 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/>.
*
*/
/**
* @file
* Code to create and handle the isomorphisms of the game cube.
*
* The Qubic board has 192 isomorphisms, which may seem a lot if you're just thinking
* about rotations and reflections. It is; that would account for only 48 isomorphisms.
* The others can be generated by two additional ones, to which I've given somewhat
* arbitrary names. The "eversion" isomorphism exchanges the extremes of each dimension
* for the middle. The "scramble" isomorphism exchanges the two middle positions of
* each dimension (the two outers could be exchanged instead, but it would generate the
* same group of isomorphisms -- just in a different order).
*
* The group of 192 isomorphisms is generated, and the operation table is built in
* 'mulcache'. The actual board (and some other things) will always be viewed through
* one of these isomorphisms (perhaps the first one, the identity).
*
* If you don't know what an isomorphism is, here's a simple way to look at it. If you
* had an actual cube, you could hold it 24 ways: there are 6 sides, and any one of
* them could be on top. For each side, there are four ways you could place the cube
* with that side on top. 24 combinations. Whichever way you held it, the game would
* look different, but it would really be the same game in a way. On top of that, for
* each of these ways of holding the cube, you could look at it in a mirror, ("apply the
* reflection isomorphism"), and you would still have the same game, but again it would
* look different. 48 combinations. The other two isomorphisms are less obvious
* changes to the Qubic board that still leave the substance of the game unchanged.
* These two are self-inverse and independent of the others, so they increase the
* combinations by a factor of 4. Thus, 192 isomorphisms.
*
*/
#include <stdlib.h>
#include <stdio.h>
#include "iso.h"
#include "state.h"
#include "base64.h"
#undef NDEBUG
#define NDEBUG
#include <assert.h>
static int qb_compare_views(Qube* board, int iso1, int iso2) ;
/**
* The isomorphisms themselves.
*/
Isomorphism isos[193]; /* one extra for convenience */
/**
* Count of the isomorphisms that have been created.
*/
static int isonum = 0;
#if 0 /* Not currently used */
/**
* A multiplication table for isomorphisms. Sort of. They actually form
* a non-abelian group, and this is the operation table.
*/
static int isomul[192][192];
#endif
/**
* Compose (multiply) isomorphisms. Used to generate the full list of isomorphisms from
* the six generators.
*/
void
qb_iso_compose(Isomorphism *left, Isomorphism *right, Isomorphism *result)
{
int i;
for (i = 0; i < 64; i++) {
result->map[i] = left->map[right->map[i]];
}
}
/**
* Compare isomorphisms for equality. This is performed on the isomorphisms themselves, and
* is used only to prevent duplication.
* @param left the left parameter.
* @param right the right parameter.
* @return 1 (true) if equal, 0 if not. */
int
qb_iso_compare(Isomorphism *left, Isomorphism *right)
{
int i;
for (i = 0; i < 64; i++) {
if (left->map[i] != right->map[i]) {
return 0;
}
}
return 1;
}
/**
* Compare two isomorphisms of the current position.
* @param board a pointer to the Qube object.
* @param iso1 an Isomorphism number.
* @param iso2 an Isomorphism number.
* @return +1 if the first view is greater, 0 if they are the same, and -1 otherwise.
*/
int
qb_compare_views(Qube* board, int iso1, int iso2)
{
int i;
Isomorphism *map1;
Isomorphism *map2;
square_state_t state1, state2;
if (iso1 == iso2) return 0;
map1 = isos + iso1;
map2 = isos + iso2;
for (i = 0; i < 64; i++) {
state1 = board->squares[map1->map[i]].square_state;
state2 = board->squares[map2->map[i]].square_state;
if (state1 < state2) {
return -1;
} else if (state1 == state2) {
continue;
} else {
return 1;
}
}
return 0;
}
/**
* Find an isomorphism that shows the canonical form of the board position. Return the
* lowest-numbered of equivalent isomorphisms. The canonic form is the "largest" in the
* collation order.
* @param b the Qube object.
* @return the index of an isomorphism that shows the Qube's position in canonical form.
*/
int
qb_find_canonical_iso(Qube *b)
{
int bestiso = 0;
int trialiso;
for (trialiso = 0; trialiso < 192; trialiso++ ) {
if (qb_compare_views(b, trialiso, bestiso) > 0) {
bestiso = trialiso;
}
}
return bestiso;
}
/**
* Test if the Qube's position is in canonical form. This is the same as saying that there's
* no iso better than the identity (iso number 0).
* @param b the Qube object.
* @return 1 if it's canonical, 0 if not.
*/
int
qb_is_canonic(Qube *b)
{
return qb_find_canonical_iso(b) == 0;
}
/**
* Translate a move number
* @param iso the isomorphism.
* @param num the move-number to translate.
* @return the translated move-number.
*/
int
qb_move_from_iso(int iso, int num)
{
return isos[iso].map[num];
}
/**
* Inverse-translate a move number, or else abort.
* @param iso the isomorphism that produced the move number
* @param num the move-number produced.
* @return the move-number that was translated into 'num'.
*/
int
qb_inverse_move_from_iso(int iso, int num)
{
int sq;
for (sq = 0; sq < 64; sq++) {
if (isos[iso].map[sq] == num) {
return sq;
}
}
abort();
}
/**
* Write the position string of the Qube object's position, as seen through the given
* Isomorphism.
* @param b a pointer to the Qube object.
* @param iso the index of the Isomorphism.
* @param string a pointer to the string where the description will be put (requires 65 bytes).
*/
void
qb_write_qube_through_iso(Qube *b, int iso, char *string)
{
int i;
char ch;
int state;
for (i = 0; i < 64; i++) {
state = b->squares[isos[iso].map[i]].square_state;
if (state == COMP) {
ch = 'x';
} else if (state == PLAYER) {
ch = 'o';
} else {
ch = '-';
}
string[i] = ch;
}
string[64] = '\0';
}
/**
* Encode the given iso into a 65-byte string (counting terminating NUL byte.
* @param iso the index to the isomorphism.
* @param string where to put the result. Must have a capacity of at least 65.
*/
void
qb_write_iso(int iso, char *string)
{
int i;
for (i = 0; i < 64; i++) {
string[i] = base64_encode(isos[iso].map[i]);
}
string[64] = '\0';
}
/**
* Create the isomorphisms.
* Initialize a list of the isomorphisms, with 6 basic and independent "generators".
* isos[0] is the identity (initialized by constructor)
* isos[1] is a reflection
* isos[2] is a rotation around the first axis (board)
* isos[3] is a rotation around the second axis (line)
* isos[4] is the "inversion" isomorphism
* isos[5] is the "scramble" isomorphism
* all the others are generated from these.
* @return the address of the array of isomorphisms.
*/
Isomorphism *
qb_create_isos(void)
{
int evert[] = {1,0,3,2};
int scramble[] = {0,2,1,3};
int i, j, k;
isonum = 0;
/* Begin with the identity isomorphism */
isos[isonum].inverse = isonum; /* self-inverse */
for (i = 0; i < 64; i++) {
isos[isonum].map[i] = i;
}
isonum++;
/* A reflection of the identity (any one will do) */
isos[isonum].inverse = isonum; /* self-inverse */
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
for (k=0; k<4; k++) {
isos[isonum].ISOCELL(i,j,k) = isos[0].ISOCELL(i,j,3-k);
}
}
}
isonum++;
/* rotate the identity around the i-axis */
isos[isonum].inverse = -1; /* not known yet */
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
for (k=0; k<4; k++) {
isos[isonum].ISOCELL(i,j,k) = isos[0].ISOCELL(i,k,3-j);
}
}
}
isonum++;
/* rotate the identity around the j-axis */
isos[isonum].inverse = -1; /* not known yet */
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
for (k=0; k<4; k++) {
isos[isonum].ISOCELL(i,j,k) = isos[0].ISOCELL(k,j,3-i);
}
}
}
isonum++;
/* The "eversion" isomorphism turns the cube inside-out. */
isos[isonum].inverse = isonum; /* self-inverse */
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
for (k=0; k<4; k++) {
isos[isonum].ISOCELL(i,j,k) = isos[0].ISOCELL(evert[i], evert[j], evert[k]);
}
}
}
isonum++;
/* The "scramble" isomorphism swaps the inner coordinates. */
isos[isonum].inverse = isonum; /* self-inverse */
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
for (k=0; k<4; k++) {
isos[isonum].ISOCELL(i,j,k) = isos[0].ISOCELL(scramble[i], scramble[j], scramble[k]);
}
}
}
isonum++;
/*
* Now do all possible compositions. This is brute-force, and it takes a few seconds on
* modern machines as of 2000, but the code is clearly correct, so I let it stand.
*
* We optimize slightly by not using the identity at all, and not composing a known
* self-inverse with itself.
*
* We optimize a whole bunch more by noting that we only need the first six generators
* on the left. The others will be generated in the first pass. What luck!
*
* Each new combination is built in-place, before it is known if it will be kept.
* This requires the array to be one larger than otherwise necessary, expecting that
* the last few will turn out to be duplicates.
*/
{
int newiso = 6;
int thisiso;
for (i=1; i<6; i++) {
for (j=2; j<newiso; j++) {
thisiso = newiso++;
isos[thisiso].inverse = -1;
if (newiso>193) {
fprintf(stderr, "There are too many (%d) isomorphisms", newiso);
exit(EXIT_FAILURE);
}
qb_iso_compose(isos + i, isos + j, isos + thisiso);
for (k=0; k+1<newiso; k++) {
if (qb_iso_compare(isos + thisiso, isos + k)) {
newiso--;
break;
}
}
}
}
assert(newiso == 192);
/* Next, we find the inverses of all the isomorphisms. They should all be here
* already; we just have to find them.
*/
for (i=0; i<newiso; i++) {
// Skip those whose inverse is already known
if (isos[i].inverse == -1) {
for (j=i; j<newiso; j++) {
if (isos[j].inverse == -1) {
for (k=0; k<64; k++) {
if (k != isos[j].map[isos[i].map[k]]){
break; /* not the inverse */
}
}
if (k < 64) {
continue; /* not the inverse */
}
isos[i].inverse = j;
isos[j].inverse = i;
break;
}
}
assert(j < newiso);
}
} /* end scope of thisiso, newiso */
#if 0 /* Not sure this will ever be needed; not tested. */
/* Finally, the isomul table of the group operation is filled. */
{
Isomorphism product;
for (i = 0; i < 192; i++) {
for (j = 0; j < 192; j++) {
/* form the product */
for (k = 0; k < 64; k++) {
qb_iso_compose(isos + i, isos + j, &product);
}
/* find it in the table */
for (k = 0; k < 192; k++) {
if (qb_iso_compare(&product, isos + k)) {
break; /* got it */
}
}
assert(k < 192);
isomul[i][j] = k;
}
}
} /* end scope of product */
#endif
#ifndef NDEBUG
for (i = 0; i < 192; i++) {
fprintf(stderr, "%3d: %3d", i, isos[i].inverse);
for (j = 0; j < 64; j+=16) {
fprintf(stderr, " %3d%3d%3d%3d %3d%3d%3d%3d %3d%3d%3d%3d %3d%3d%3d%3d",
isos[i].map[j + 0],
isos[i].map[j + 1],
isos[i].map[j + 2],
isos[i].map[j + 3],
isos[i].map[j + 4],
isos[i].map[j + 5],
isos[i].map[j + 6],
isos[i].map[j + 7],
isos[i].map[j + 8],
isos[i].map[j + 9],
isos[i].map[j + 10],
isos[i].map[j + 11],
isos[i].map[j + 12],
isos[i].map[j + 13],
isos[i].map[j + 14],
isos[i].map[j + 15]);
}
fprintf(stderr, "\n");
}
#endif
}
return isos;
}
/* vim: set expandtab autoindent shiftround nosmartindent tabstop=8 softtabstop=2 shiftwidth=2: */