Fragment Description:



This program tries to find a solution for a puzzle attributed to mathematician Ernst Specker (http://www.math.ethz.ch/~engeler/Specker_Nachruf.pdf, p.
11).
The puzzle goes as follows:
Imagine a 3x3x3 cube of cheese, made of 27 subcubes (like a Rubic's cube).
A mouse eats the cube one subcube at a time and then advances to one of the immediately adjacent subcubes.
Is there a path through all subcubes such that the mouse finishes with the subcube in the center as the very last? There's an elegant proof that there is no solution.
This program mainly serves as an illustration of how one might approach this problem using a brute-force backtracking algorithm.
(Robert Griesemer - 2/3/2013)


aBacktrackingAlgo

Go Playground

Last update, on 2015, Fri 9 Oct, 16:15:32

/* ... <== see fragment description ... */

package main

import (
    "fmt"
    "time"
)

// To simplify the program logic the cube is embedded in a larger 5x5x5
// "padded"
// cube which itself is mapped onto a array of 125 bytes. The padding makes
// it
// easy to see if one is "outside" the cube, and the serialization makes it
// easy
// to move in all six directions with a single "stride" value (no need for
// three
// coordinates).
//
const (
    w  = 3         // cube width
    n  = w * w * w // number of subcubes
    pw = 1 + w + 1 // padded cube width
    dx = 1         // x axis stride
    dy = pw        // y axis stride
    dz = pw * pw   // z axis stride
)

// Non-existing or eaten subcubes are marked with 0. Existing
// subcubes have a non-zero value. They are conventienly numbered
// from 1 to 27 so that it's easy to print the mouse's path if a
// solution is found.
//
var cube = [pw * pw * pw]byte{
    // bottom layer is all zeros
    dz: 0, 0, 0, 0, 0,
    0, 1, 2, 3, 0,
    0, 4, 5, 6, 0,
    0, 7, 8, 9, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0,
    0, 10, 11, 12, 0,
    0, 13, 14, 15, 0,
    0, 16, 17, 18, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0,
    0, 19, 20, 21, 0,
    0, 22, 23, 24, 0,
    0, 25, 26, 27, 0,
    0, 0, 0, 0, 0,
    // top layer is all zeros
}
var (
    path      []byte // list of subcubes on the mouse's path
    paths     int    // number of complete paths tried
    solutions int    // number of paths ending in the center
)

// try tries to find a path through the rest of the cube starting
// with the subcube at pos (which may not exist).
//
func try(pos int) {
    c := cube[pos]
    if c == 0 {
        // no subcube present
        return
    }
    // subcube present - add it to path
    path = append(path, c)
    if len(path) == n {
        // all subcubes eaten - we have a path through the entire cube
        paths++
        if c == 14 {
            // the last subcube was in the center - we have a solution
            solutions++
            fmt.Println(path)
        }
    } else {
        // there are subcubes left - try eating each immediately
        // adjacent subcube
        cube[pos] = 0 // mark the current subcube as eaten
        for _, dir := range [...]int{dx, dy, dz, -dx, -dy, -dz} {
            try(pos + dir)
        }
        cube[pos] = c // restore the current subcube (backtrack)
    }
    path = path[0 : len(path)-1]
}

// find returns a subcube's position.
//
func find(subcube byte) int {
    for pos, c := range cube {
        if c == subcube {
            return pos
        }
    }
    panic("no such subcube")
}
func main() {
    // Because of symmetry it's sufficient to start with the following three
    // subcubes.
    // If run in the Go Playground, uncomment one try call at a time to avoid
    // timeout.
    start := time.Now()
    try(find(1))
    // try(find(2))
    // try(find(5))
    elapsed := time.Since(start).Seconds()
    fmt.Printf("found %d solutions (%d paths tried)\n In: %vseconds!\n", solutions, paths, elapsed)
}

/* Expected Output:
found 0 solutions (392628 paths tried)
In: 1.9441112seconds!
*/



Comments