Kubicschach (Cubic Chess Path Finding)

Statement

Goal

In 1851, Lionel Kieseritzky invented one of the first variations of a 3D Chess game, "Kubikschach", or Cubic Chess in German.

In this puzzle, you must calculate the least number of moves for a specific piece to move from one position to another on an empty 8x8x8 chess board based on the movements defined below.

Each position is indexed by a capital letter, a number, and a lowercase letter, for the its row, column, and slice (YXZ => RCS => A1a). The game's "board" is made by creating 8 "slices" which are A1a -> H8h with the bottom board being "a" and the top board being "h". Thus the space A1a is the back, left, bottom corner of the board.

The two players, Black and White, each have a "Home Row" located opposite one another, that being row A within the h-slice for Black and row H within the a-slice for White. The color of the given piece will only affect the movement of the pawn.


       A1h A2h A3h A4h A5h A6h A7h A8h     <-- Black Home Row
       A1g  .   .   .   .   .   .  A8g
       A1f  .   .   .   .   .   .  A8f
       A1e  .   .   .   .   .   .  A8e
       A1d  .   .   .   .   .   .  A8d
       A1c  .   .   .   .   .   .  A8c
       A1b  .   .   .   .   .   .  A8b
       A1a A2a A3a A4a A5a A6a A7a A8a     <-- "Slice" a
      B1a  .   .   .   .   .   .  B8a        /
     C1a  .   .   .   .   .   .  C8a     <--
    D1a  .   .   .   .   .   .  D8a        /
   E1a  .   .   .   .   .   .  E8a     <--
  F1a  .   .   .   .   .   .  F8a
 G1a  .   .   .   .   .   .  G8a
H1a H2a H3a H4a H5a H6a H7a H8a     <-- White Home Row

Here are the rules governing the movement of each piece:

King may move 1 space to any adjacent space
(Ex: A1a -> A1b, or A2b, or B2b, etc.)

Pawn may move 1 space towards the opponent's home row. Since Pawn's can only move towards their opponent's home row, the color of the Pawn determines if it can move in OR up or out OR down. A Pawn is not allowed to leave the column it starts in at any point. (i.e. A1a -> A2a is not allowed)
(Ex-White Pawn: H1a -> G1a, H1a -> H1b, NOT H1a -> G1b, NOT A1a -> B1a)

Rook may move S spaces along only 1 axis
(Ex: F3d -> F8d, A1a -> H1a, D6c -> D6b)

Bishop may move S spaces and must move along 3 axes
(Ex: A1a -> H8h, D4f -> A7b, NOT A1a -> H8a)

Queen may move S spaces along 1 or 3 axes on any turn
(Ex: A1a -> B2b, A1a -> B1a, A1a -> A2a, NOT A1a -> B2a)

Knight must move 1 space along 1 axis AND 2 spaces along 1 other axis
(Ex: A1a -> B3a, A1a -> B1c, A1a -> C1b, F4d -> G2d)

No piece may ever leave the chess board. For this level the pawn will always move 1 space and will not need to be promoted to reach the final space.

Input

Line 1: A name of a chess piece, piece, followed by the first initial, color, of the color of the piece, separated by a space
Line 2: A 3-character String, startingPosition
Line 3: A 3-character String, finalPosition

Output

The least number of moves, N, that a chess piece, piece, can move from startingPosition to finalPosition, or -1 if it cannot move to the desired position.

Constraints

A1a <= startingPosition, finalPosition <= H8h
piece is always the White Player's Piece

Example

Input

King W
A1a
B3d

Output

Rate this contribution

Comments

13 Comments

Djoums Unnamed CodinGamer

over 3 years ago

Is your cell notation part of the rules of Kubikschach ? Because usually in regular chess, the white player's home row is a1-h1 and the black player's home row if a8-h8. Converted to 3D they should become Aa1-Ah1 and Ha8-Hh8 (the 3rd dimension put first makes it a lot clearer imo).

Unnamed CodinGamer

over 3 years ago

I think I did switch numbers with upper-letters actually. I’ll look into a fix tomorrow. I have the coordinates in XYZ form but as you noted it might be a bit confusing.

luke-guyton Unnamed CodinGamer

over 3 years ago

HI, it's still unclear if the King's "adjacent" space can mean diagonally through all three axes, e.g. A1a -> B2b Perhaps list more examples for the King. In regards to the "The piece is always white" - perhaps this doesn't need to be the case, it only matters if the piece is a pawn, so perhaps you could have "white pawn" and "black pawn", and list their moves separately; and provide additional test cases. This would make it seem less bias towards white, if you catch my drift. (alternatively you could reduce the bias to just a statement about pawns "for the purpose of simplifying the puzzle")

Unnamed CodinGamer

over 3 years ago

I have considered your suggestion before about colored pawns and I think you could be onto a good idea. I think I’ll add an input line for the color of the piece. I’m on my phone right now so I’ll look at the king more tomorrow and maybe clarify it. I realize it was kind of awkward but I wanted the statements to all be parallel and short.

UnicornP Unnamed CodinGamer

over 3 years ago

Here are my thoughts: * The opponent's "home row" should be Axh, not Ax8 right? * Providing an example of an extreme movement for each piece would be good. For example, Kings can go from B3c to C4d (all 3 axes being used). * I'm still not confident with Pawn movement. If a pawn is at G2b and the opponent's home row is Axh, does it mean that the only legal movements are to F2b and G2c? * It might be better to use [[S]] spaces instead of [[N]] spaces to remove the conflict with K{{N}}ight. It probably doesn't matter to most people though. * Without prior chess knowledge, I would have had a hard time understanding the difference between King and Bishop movement. Maybe something like "{{B}}ishops may move [[N]] spaces only along all 3 axes at once}} * Regarding solving Knight movement, I don't think a BFS would be too difficult to implement in 3D, but Medium is probably the right difficulty. In any case, I think all pieces can be calculated semi-analytically. For the knight, see if something like the following works: Loop Calculate distance for each axis Jump 2 spaces along furthest axis, 1 space along next-furthest axis Are we on target? Break Is target adjacent? Add 3 and break Is target diagonally-adjacent? Add 2 and break End loop It might even be possible to do this without a loop. The "add 3" and "add 2" are what you would need for 2D chess; the numbers might be difference in 3D.

Unnamed CodinGamer

over 3 years ago

You are correct about the home row and pawn movement, I will reconsider how to define that. The will change the other few things you noted. I think your approach to the knight will help me, thanks. Also, every piece except the knight is completely analytic. I’m still early in this process but I have enjoyed solving it especially when it came to the bishop and the extension of the room and bishop with the queen so I’m hopeful that others will as well. Again thank you so much for taking your time to provide feedback. Additional thought: previously I had to consider what I would allow the queen to do movement wise and I was between allowing 1,2,3; 1,2; 1,3 movement, here’s a better description: 1. Queen can move like this: <2,0,0> <2,2,0> <2,2,2> 2. <2,0,0> <2,2,2> 3. <2,0,0> <2,2,0> Originally I had it as 1. but for the purpose of the puzzle I’m happy to have gone with 2. I’ll not spoil it so it can be a surprise when being solved. I deleted the original comment I made because someone game me really good insights as to why it should 2. but I wanted to have it here so that it was clear I have considered it as well as the bishop.

Unnamed CodinGamer

over 3 years ago

Please excuse this unfinished puzzle, I was eager to get feedback on a few things and thankfully I have for the most part sorted out some things I was unsure of. In the next few coming days I will hopefully finished the test cases and solution.

Unnamed CodinGamer

over 3 years ago

So, I'm getting the bishop now and im realizing it might be a bit harder, which is a good thing, but it means I'll have to spend more time than originally expected I will keep the puzzle as WIP so those who are interested in keeping track of its progress can do so.

Unnamed CodinGamer

over 3 years ago

For the "level 2" version I plan on adding two "fairy pieces" as well as making test cases / validators that require the pawn to be promoted and utilize home plane augmented movement (i.e. moves 2 spaces instead of 1 if within the plane adjacent to the home plane). Here are the descriptions that would go along with those: The movements of these fairy pieces have been altered and described to fit this 3D variation of chess. (https://en.wikipedia.org/...) In 2D chess, the Knightrider can move the same way as a knight but may also chain identical legs to open sames. (i.e. 2 forward 1 right, 2 forward 1 right is a legal move if both the interim and final spaces are open). Knightrider(R) may move like a knight and may continue making the same EXACT movement any number of times In Kubikschach, a Unicorn was allowed to move first like a Knight, then outwardly as a bishop. Unicorn(U) must first move like a knight, then may move diagonally along the 2 axes it had previously moved in, any number of units. It may not get closer in any direction to its original position during the second phase of its movement. (i.e. if a Unicorn moves Forward 1 and Up 2, it may move X spaces in both the Forward and Up direction). Pawn(P) may only move 1 space towards the opponents home row OR towards the top of the board, unless the pawn occupies the plane adjacent to the player's home "plane", in which case the pawn may move 2 spaces while it is still within that plane. Upon reaching the opponent's home plane, a pawn may be promoted to any other unit (bar King). ***Should promotion only be in the top home row? Or does the home plane make sense here? Any feedback is appreciated.

ABOUT US CAREERS PRIVACY FAQ BLOG

The #1 tech hiring platform

SCREENING INTERVIEWING