Skip to content

metasoarous/block_puzzle_solver

Repository files navigation

= Puzzle Solver Program

This program is designed to solve the block puzzle illustrated in the
image file at the root of the directory. There are 64 pieces, and they
are connected with a string that runs between them. Where the blocks
change directions, it is possible to twist the blocks that follow by
rotating. In this way, it is possible to reconfigure the blocks into a
4x4x4 cube. This program counts all of the possible solutions, though
possibly with some repitition when isomorphism is considered. It is the
eventual aim of this program to account for isomorphisms as well, and will
certainly need to in order to maximize effeciency.


== Algorithm outline:

The block puzzle is represented as an array of the number of blocks till a
turn. We represent configurations of the blocks as a 3x3 "matrix" of 1s where
there are blocks. The matrix is implemented as a disctinary mapping tuples
of integer coordinates to 1 for spots which have a block. The basic idea is
to iterate over the possible rotations at the bends, and throw out any
rotation that would force an overlap of...

Actually, maybe we need to implement this as a set of tuples instead. That
seems more efficient. Yeah... Let's do that.


== Todo

* Write in isomorphism testing. It seems to be the case that once you pass
  through a node with no isomorphic valid moves, none of the moves therein
  will be isomorphic anywhere within. If further reflection reveals that this
  is the case, we should be able to pass along a flag which specifies whether
  to check for isomporphisms or not, to save time over the majority of the
  tree structure.
* Would be great to multithread this with an input for number of threads.
  * Should probably just put this in a separate branch
  * Is there a good way of measuring time while spreading computations out
    over multiple threads?
* R analysis code
  * There are a lot of questions that can be asked here, and more will probably
    arise as analysis ensues
  * Look at distribution of computational time on the tree
* It's probably worth throwing in some code using SQLAlchemy that will make it
  easier to do analysis in python; could prove useful.
* Might be nice to have a start_time value that makes it easier to see how long
  the computation has been running on a given node (given it's still running)

About

Program for computing the solutions to a specific block puzzle

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published