Welcome to the Kanoodle Extreme Solver wiki!

Kanoodle Extreme, cousin to the original Kanoodle and Kanoodle Genius releases, is a fun portable puzzle game that consists of 12 unique puzzle pieces (or molecules) that may be arranged in a 2D or 3D fashion to solve over 300 puzzles provided in the Kanoodle instruction book. The pieces and puzzle booklet store conveniently in a plastic box, that also serves as the board for laying out puzzles, making it a great game for traveling and playing on-the-go.

In Kanoodle Extreme, there are three types of puzzle games to choose from:

1. 2D puzzles, where a full 12-piece board is prompted with a few starting pieces in place, and you must complete the puzzle by placing the remaining pieces to fill the board. Games get progressively harder with fewer prompting pieces in place to begin more advanced games.
2. "Sliding" 2D puzzles, which prescribe 5 specific pieces that must be laid out to fill a small 2D space and then incrementally gets harder by adding one piece to the mix and sliding the board out to reveal a slightly larger space to solve. Each puzzle progresses to 9 total pieces.
3. 3D puzzles, where all 12 pieces are used to build a 6x6x6 pyramid. Games get progressively harder, with beginner games (level 1) starting with 10 pieces in place, and you must solve the remaining 2 - all the way to level 100 where you may be prompted with 2 pieces in place, and you must successfully place the remaining 10 to complete the pyramid. 3D puzzles are much more difficult, relative to the 2D, because each piece must be oriented in 3 dimensions to interlock with other pieces on different levels of the pyramid.

A 3D Pyramid Coordinate System

One of the first things that I needed to define was a coordinate system to describe the various points or "locations" on the pyramid. The most logical system that I could think of is a simple 3-dimension X, Y, Z system. Assuming the board is always oriented such that you are always looking at a face of the pyramid (as is the case with the Kanoodle board layout), the X axis runs left-to-right, Y axis runs front-to-back, and the Z axis runs from base-to-peak of the pyramid.

Locations are described as [X, Y, Z]. Therefore the lower left corner of the pyramid would be represented as [0, 0, 0], lower right would be [5, 0, 0], the rear base is [0, 5, 0], and the tip of the pyramid is [0, 0, 5]. Here are some more examples of how the coordinate system applies to the visual representation of the pyramid used in the Kanoodle Extreme instructions.

Defining Pieces

Pieces are like molecules made up of atoms. Each molecule is unique in shape and color. Some contain four atoms, and others contain five. In the domain language I used, I refer to these molecules simply as Pieces which are composed of Nodes.

When we consider how Pieces fit onto the board, we need to define a few things:

Piece Shape definition

Each piece in the Kanoodle Extreme game has a unique shape consisting of either four or five atoms or Nodes. If you were to describe some of the pieces to someone, you may use language like "The white piece is shaped like the letter 'V'" or "The gray piece is like a diamond". Describing the shape of a piece programmatically however is not a trivial task. There's really no straight forward way to codify the "V shape" of the White piece. Depending on how you look at the piece, does does the V point down? or up? or to the right? left?... The coordinate system of the board unfortunately doesn't offer much help, because we need to define the shape of a piece before we can even consider how it will be placed onto the coordinate system of the board.

Looking at the pieces as arrays of nodes, it seemed like a natural fit to define the shape of the piece as an array of nodes relative locations. Relative to what? We need a root node to serve as an absolute point of reference. So, therefore the definition of each color piece's shape is achieved by:

1. The notion of a RootPosition for the piece, which will represent the location where the piece's root node is placed, and
2. a description of the location of the piece's Nodes relative to the Root, which I call the Node's Offset.

Placing pieces on the board

...

Piece rotation and orientation

When we think about how pieces can rotate and be oriented in different ways, we need to define a way to represent that rotation behavior.

It is simplest if we start with the assumption that each color piece has a default starting Orientation, defined by a root position and Nodes offset from the root in a pre-defined direction. The image below shows the default orientation for each piece, and these layouts are codified in the Color classes in Kanoodle.Core. The left-most node of each piece is the root node.

With this default orientation defined, we can define a system of Rotation. Wrapping my head around how rotation occurs in a 3D honeycomb system proved to be much harder than I expected. My first approach was to think about rotation occurring on each of the three axes - just like how we describe rotation of an airplane in typical 3D space - in terms of X axis rotation (pitch), Y axis rotation (roll), and Z axis rotation (yaw).

Unfortunately, in the honeycomb/pyramid paradigm this construct doesn't work well, because the concepts of pitch and roll start to break down. It even becomes more complex when you consider how a piece could rotate across two or more axes at the same time - e.g. if I begin with a piece laying flat, and pitch it up slightly, and roll it over another axis - is that even a valid position? The answer turned out to be No - under the three-axes of rotation model, there are orientations you could arrive at that are not valid placements on the game board. For example...

The image above shows a placement of the Gray piece that appears at first glance to be valid, but in fact it is an invalid placement.

Another view of the same placement shows that the Gray nodes are sitting directly atop the light-blue nodes on the lower level of the pyramid.

Leaning the Gray piece in the opposite direction, parallel to the right face of the pyramid, leads to a valid placement and you can see how the Orange piece is able to fit nicely (validly) in the space provided.

Another view of the Orange piece placement shows that the nodes fit in between the light-blue nodes on the level below.

A construct of rotating along the X, Y, and Z axis unfortunately would not work. This required me to go back to the drawing board to search for a new model to represent rotation behavior. I blocked out of my mind any notion of axes of rotation, and tried to look at the problem from a clean slate. How is it that there are some valid rotations, and some invalid?

Eventually, I noticed a couple things:

1. All rotations of flat pieces (i.e. in 2D space along the base of the pyramid) were valid. I can turn a flat piece into five distinct positions and they always work as valid orientations.
2. When I tilt a flat piece up into a leaning position - sometimes, it is a valid orientation, and sometimes when I lean the piece in the opposite direction, it is invalid - as we saw with the example of the Gray piece above.
3. The valid orientations were always leaning parallel with the nearest face of the pyramid.

Which logically made sense! #1 and #3 are related. The reason point #1 above is true is because flat pieces are always parallel with the bottom face of the pyramid. If I transpose that same piece to any of the three other faces (or simply rotate the entire pyramid) I can perform the same valid rotation of the piece. The concept of leaning is simply orienting the piece to be parallel to a given face of the pyramid.

Therefore, I decided to redefine the model for piece positioning in terms of

1. A default orientation of a given color piece, which is defined by a root node and an array of nodes offset from the root to define Shape
2. Placement of the root node onto a location on the board defined by the coordinate system
3. A concept of Rotation along a single planar dimension (i.e. flat rotation) to define different possible orientations of the starting position. In the Rool/Pitch/Yaw paradigm, the type of rotation I am describing is Yaw
4. Describing whether the piece is oriented parallel to the plane or not (i.e. is it leaning relative to the side of the pyramid)
5. Transposing the rotated piece onto one of the four faces (or planes) of the pyramid

A System for Piece Placement

We've already covered the default orientation of each color piece above. Moving to #2 in our sequence of placement operations, we need to place the piece on the board lying flat (i.e. parallel to the X-Y face). Note this could be at any level of the pyramid, so long as the piece is lying flat.

In the image above, the Yellow piece has been positioned with the root node sitting at [1,0,0]. Therefore, the location of each node in the Yellow piece can be calculated using some simple coordinate algebra.

[Actual Node Position] = [Root Node Position] + [Node offset from Root]

You can see the calculated actual positions in the example above.

Rotation

I defined Rotation as the counter-clockwise turn of a piece on the flat plane, i.e. as though the piece is sitting flat on the table. Given the honeycomb layout of the Kanoodle board, there are 5 distinct orientations of a piece as you rotate from the root position - the 6th rotation returns you to the starting position. Therefore, when describing the orientation of a piece on the board, I assume there is a starting default orientation and then assign a value 1-5 to describe the counter clockwise rotation of that layout, keeping the root node in place.

The five images above depict the five rotation positions of the Gray piece, the sixth rotation returning the piece to the original position.

Missing Positions

Even after accounting for all 6 rotation positions for a given piece, there are still some valid positions on the board that are left unaccounted for. This is due to the fact that the default starting orientation will never rotate to a position that matches it's mirror along the X-Axis. This example with the Orange piece will help explain.

The image above shows the Orange piece in the default orientation. Remember, the Root node is the left-most node. In this example the piece's RootLocation is [0,2,0] but that is insignificant for this example. Now, if you rotate this piece counter-clockwise, around the root location, you can imagine how the "arm" of the Orange piece will rotate around and eventually end up back in the same starting position - just like with the example of the Gray piece above. But, notice that in this Root position, and rotating in that manner, you would never be able to match the position below, which also shares the same Root position.

Notice that this position is simply the mirror image of the orientation above, mirrored along the X-Axis. We need to account for this orientation of the piece at each root location, and to do so we have a boolean property on the Piece.cs class called MirrorX. If true the default starting orientation of the piece is flipped along the X-Axis prior to any Rotation or Lean.

Relative Plane

Assigning a relative plane solves the problem of rotating along multiple axes. If we specify that a piece is placed relative to one of the pyramid faces, it implies a roll or pitch of the piece such that it is always sitting parallel to that face. This will always result in a valid "lean" of the piece, stacking the Atoms in the proper pyramid structure.

Lean

The concept of Lean is a binary condition of whether the piece is lying parallel to the base of the pyramid, or if the piece is tilted up parallel to the relative Plane. Lean is always performed relative to the X axis, which should align the piece parallel to the front face of the pyramid. If Lean == true, then the piece is rotated by keeping the root node and any other nodes on the same row in place and rotating the remaining pieces up to a parallel alignment with the face of the pyramid.

Order of Operations

To place a piece on the board, the following sequence of steps are performed

1. Start with the default starting layout for a given shape and set the location of the root node
2. Apply the Mirror orientation along the X-Axis
3. Apply Rotation to rotate the shape relative to the root node in the flat/base plane
4. Apply Lean to tilt the shape up from the flat position to the leaning position, relative to Plane 0 (the front face of the pyramid).
5. Transpose the shape onto the relative plane

The following example help bring these steps to life. In this example we will assume the following:

1. We are starting with the default layout of the Red piece
2. We will rotate to position 2
3. We are assuming Lean == true
4. We will transpose to Plane 2 (Left face)

In this first image (above) you can see how the Red piece is initially placed with the root node at location [4,1,0] in our coordinate system. Notice that the piece itself extends out of bounds, off of the board. This is ok for the initial placement, and is even necessary to achieve some valid positions after the following steps are applied.

In this second figure, we've rotated the starting position 2 steps - again, rotations are counter-clockwise.

The next step is to lean the piece. Lean is always performed relative to the X axis or parallel to the front face of the pyramid. In the image above, I've used the Gray piece to hold the leaning Red piece in valid position.

And, in the final step, we transpose the leaned piece onto the desired plane. In this example we are transposing onto plane number 1, the right face of the pyramid. The result of this transpose step is the same as if you rotated the entire board 1/3rd of a full rotation counter-clockwise. The red piece is now leaning parallel to the right face.

The end result of this sequence is how you would achieve the starting position for the Red piece in Puzzle #82 in the Kanoodle instruction book.

Each of the steps above can be represented as Coordinate Algebra formulas (which I will dive into more below), and the net result can be described as a final Actual Location of each Node of the piece. In this example, the actual location would be described as follows:

Codifying the Placement System - Honeycomb Pyramid Coordinate Algebra

The following functions are part of the Piece.cs class. Check here for the latest code - https://github.com/benelder/Kanoodle/blob/master/Kanoodle.Core/Piece.cs

Rotation Algebra

Rotating a piece in the flat X-Y plane assumes you start with the default piece orientation, which is equivalent to Rotation == 0. The algorithm for calculating the net effect on a given Node of rotating is as follows:

private Location Rotate(Location location) 
{
     // rotation is performed first, in the order of placement operations
     // location input is the Node offset, relative to Root
     if (Rotation == 0)
         return location;

     if (Rotation > 5)
         throw new Exception("Invalid rotation");

     var toRet = new Location(location.X, location.Y, location.Z);

     for (int i = 0; i < Rotation; i++)
     {
          toRet = new Location(-toRet.Y, toRet.X + toRet.Y, toRet.Z);
     }

     return toRet;
}

Lean Algebra

Applying lean is always calculated relative to the X-Z plane, or the front face of the pyramid, and occurs in the positioning order-of-operations prior to transposing onto another plane. This makes the lean calculation very simple. If no-lean, return the flat orientation which we are starting with. If Lean == true, then X is unchanged, Y = 0 always and Z = offset.Y always. Important to note, the coordinates referenced here are the relative-to-root offset values, not absolute positional coordinates of the piece placement.

private Location ApplyLean(Location offset)
{
     if (Lean)
     {
          return new Location { X = offset.X, Y = 0, Z = offset.Y };
     }
     else
     {
          return offset;
     }
}

Transposing to Relative Plane

Transposing to a plane is always done from the default position which is relative to the X-Z plane (Plane 0) or the front face of the pyramid. Therefore, there are two other planes that we can transpose to, 1 and 2 (right face and left face respectively).

Again, this calculation returns the relative offset of a given node relative to the root, not the final placement coordinates.

private Location TransposeToPlane(Location origin)
{
     if (Plane == 0)
     {
          return origin; // transposition is based on Plane 0, so no change if Plane == 0
     }

     else if (Plane == 1)
     {
          return new Location { X = 5 - (origin.X + origin.Y + origin.Z), Y = origin.X, Z = origin.Z };
     }

     else if (Plane == 2)
     {
          return new Location { X = origin.Y, Y = 5 - (origin.X + origin.Y + origin.Z), Z = origin.Z };
     }

     throw new Exception("Plane must be between 0 and 2");
}

Brute Forcing a Solution

The approach I took to brute forcing a solution for a given Kanoodle puzzle prompt is the following logical steps:

1. Build an in-state collection of all possible valid positions for each puzzle piece
2. Load a game state onto the board
3. Recursively, place a piece on the board and check for validity. If not a valid placement (out of bounds, or colliding with another piece) remove the piece and try another. If valid, keep the piece there and move to the next color piece and repeat. If all possible positions of a given color piece have been tried unsuccessfully, bubble up and continue.

Step 1 above is accomplished by looping through..

• for all color pieces
• for all possible root positions
• for all possible rotations
• for each plane
• for both Mirrored and Default orientations - for both Leaning and Not-Leaning... record the absolute position of the resulting location of the piece.

There will certainly be many duplications of the same absolute position for a given color piece, so we only add unique positions to the collection.

Based on this approach, here are the total number of unique valid positions for each color:

Color	Total Positions
Lime	336
Yellow	480
Dark Blue	96
Light Blue	336
Red	360
Pink	168
Green	480
White	288
Orange	480
Peach	240
Gray	240
Purple	720

With this inventory of all possible valid positions for each color piece, we can now build an algorithm to recursively add a color piece to the board, test if it's a valid fit both within bounds and not colliding with other pieces. The logic is basically this:

For each Color that has not been placed on the board, start with a color and place its first valid position on the board. If the fit is valid, we can continue by repeating the same step again with the next unplaced Color piece. If it is invalid, we move to the next possible position for the Color and try again. If we make it through all positions for a given Color and are unsuccessful at finding a valid fit, we know that the puzzle can't be solved in the current state, so we need to go back and remove the last piece that was placed and try a different position for that piece.. and repeat until either all pieces are placed, OR until we have unsuccessfully tried all possible positions for the first color - in which case, the puzzle has no valid solution.

This approach is able to solve all 100 Kanoodle 3D puzzles, plus many others that I have created at random during testing!

Explore the Kanoodle Solver Wiki features and capabilities here

Walkthrough of Kanoodle Extreme Console App Functionality

Final thoughts

Overall, the system of coordinates, piece shape, and placement that I devised here seems to work really well. I have been able to successfully solve each puzzle that I have attempted from the Kanoodle booklet, and many that I randomly created from scratch. The time to solve on my c2017 desktop is ~50 seconds for level 95-100 puzzles. Level 20-40s solve in milliseconds.

Is this code base the optimal solution for performance or code brevity, etc.? Probably not. If there are simpler, more efficient algorithms or patterns for defining a schema for brute-forcing a solution I would love to hear and learn more.

Notes from the hours at breakfast table breaking down the domain model and coordinate algebra behind the Kanoodle Solver algorithms