Three-Dimensional Chess

Question

In order to defend someone’s baffling decision, people often say that that person is going over everyone’s heads and playing “3-dimensional chess”. Now it’s your chance to play 3-dimensional chess!

Rules

There are many variants of 3D Chess, but for this challenge I’ve made up my own. My version is just like regular chess except that the pieces are inside cubes instead of squares, and now have an additional dimension of movement. To make this challenge simple there are no pawns and no castling.

Piece Movement

(Compass directions refer to movement that would occur on a standard chessboard, Up and Down refer to moving vertically on the 3D chess board).

• King - has 26 squares it can go to on a given turn: N,NE,E,SE,S,SW,W,NW; as well as up, down, and up/down + one of the compass directions.
• Queen - can move in the same directions as the King, but as far as she wants in those directions.
• Rook - can move in 6 directions: N,E,S,W, Up, and Down,
• Bishop - has 8 triagonal directions of travel: NE + Up/Down, SE + Up/Down, SW + Up/Down, NW + Up/Down
• Knight - moves 2 spaces one axis, then 1 space on another. Just like regular chess, the knight is the only piece that can hop over other pieces.

Piece Tester

Use this snippet to see how the different pieces move on the 3D board (tip: check out the *Test functions in the JS for quick ways to determine if a square is a valid move, simply based on its absolute distance from the piece.):

const color = "Black";
const pieces = ["N","B","R","Q","K"];
const urls = ["https://image.ibb.co/gyS9Cx/Black_N.png","https://image.ibb.co/dknnzc/Black_B.png","https://image.ibb.co/kb3hXx/Black_R.png","https://image.ibb.co/hGO5kH/Black_Q.png","https://image.ibb.co/jApd5H/Black_K.png"];
var dragPiece;
var size = 3;
var index = 0;
function start() {
Array.prototype.add = function(a) {return [this[0]+a[0],this[1]+a[1],this[2]+a[2]]};

document.getElementById("n").onchange=function() {
	size = parseInt(this.value);
	var s = document.getElementsByClassName("selected");
	var pos;
	if(s.length > 0) {
		pos = s[0].pos;
	}
	document.body.removeChild(document.body.firstChild);
	createBoards();
	if(pos != null && valid(...pos)) {
	cellAt(...pos).click();
	}
};
createBoards();
}

function createBoards() {
var boards = document.createElement("div");
boards.style.counterReset = "board-count "+(size+1);
boards.name=size;
for(var x = 0;x<size;x++) {
var t = document.createElement("table");
for(var i = 0;i<size;i++) {
  var row = document.createElement("tr");
  row.className="row";
  for(var j = 0;j<size;j++) {
  	var cell = document.createElement("td");
    cell.className = (size+i+j)%2 == 1 ? "black" : "white";
    var im = document.createElement("img");
    im.draggable = true;
    im.ondragstart = function(e) {dragPiece = this;e.dataTransfer.setData("piece",this.parentElement.name);
    this.parentElement.classList.add("start");
    this.classList.add("dragged");
    };
    im.ondragend = function(e) {this.parentElement.classList.remove("start");this.classList.remove("dragged");};
    im.hidden = true;
    cell.appendChild(im);
    cell.pos = [j,i,x];
    cell.ondragover = function(e) {e.preventDefault();};
    cell.ondragenter = function(e) {this.classList.add("drag");};
    cell.ondragleave = function(e) {this.classList.remove("drag");};
    cell.ondrop = function(e) { e.preventDefault();this.classList.remove("drag");
    if(this != dragPiece.parentElement && this.firstChild.hidden ){
    dragPiece.hidden=true;
    setPiece(this,e.dataTransfer.getData("piece"));
    }
    
    };
    cell.onclick = function() {
    if(this.firstChild.hidden == false && this.classList.contains("selected")) {
		index++;
    	if(index == pieces.length) index = 0;
    }
     	setPiece(this,pieces[index]);
    };
  
    
    row.appendChild(cell);
  }
  t.appendChild(row);
  }
  boards.appendChild(t);
  }
  document.body.insertBefore(boards,document.body.firstChild);
}



function clearHighlighted() {
	var sel =  document.getElementsByClassName("highlighted");
     while(sel.length > 0) {
     	sel[0].classList.remove("highlighted");
     }
}

function setPiece(cell,piece) {
var s=document.getElementsByClassName("selected");
if(s.length > 0){ s[0].firstChild.hidden=true;s[0].classList.remove("selected");}
cell.classList.add("selected");
cell.firstChild.hidden = false;
cell.name = piece;
     	cell.firstChild.src = urls[index];
     clearHighlighted();
     	showMoves(cell,piece);
}

function showMoves(cell,piece) {
	if(piece=="K") selector(cell,kingTest)
	else if(piece=="N") selector(cell,knightTest);
	else if(piece=="Q") selector(cell,queenTest);
	else if(piece=="R") selector(cell,rookTest);
	else if(piece=="B") selector(cell,bishopTest);
}

function cellAt(col,row,board) {
	return document.body.firstChild.children[board].children[row].children[col];
}

function valid(col,row,board) {
	return 0<=col && col<size && 0<=row && row<size && 0<=board && board<size;
}

function select(cell) {
if(cell != null && cell.firstChild.hidden) cell.classList.add("highlighted");
}



function rookTest(dist) {
	var d = [].concat(dist).sort();
	return d[0] == 0 && d[1] == 0;
}

function knightTest(dist) {
	var d = [].concat(dist).sort();
	return d[0] == 0 && d[1] == 1 && d[2] == 2;
}

function kingTest(dist) {
	return dist[0] <= 1 && dist[1] <= 1 && dist[2] <= 1;
}

function bishopTest(dist) {
	return dist[0]==dist[1] && dist[1]==dist[2];
}

function queenTest(dist) {
	var d = [].concat(dist).sort();
	return rookTest(dist) || bishopTest(dist) || (d[0]==0 && d[1]==d[2]) ;
}

function dist(cell,x,y,z) {
	return [Math.abs(cell.pos[0]-x),Math.abs(cell.pos[1]-y),Math.abs(cell.pos[2]-z)];
}

function selector(cell,test) {
	for(var i = 0;i<size;i++) {
		for(var j = 0;j<size;j++) {
			for(var k = 0;k<size;k++) {
			if(test(dist(cell,k,j,i))) {
				var c = cellAt(k,j,i);
				if(c != cell) select(c);
			}
			}
			}
			}
	
}

table
{
	padding: 10px;
  display:inline-block;
}

table:after
{
  counter-increment: board-count -1;
  content: "("counter(board-count,upper-roman)")";
  float:right;
}

td
{
  width:28px;
  height:28px;
  border: 1px solid;
  cursor: pointer;
}

.black
{
  background-color: rgba(127,127,127,0.6);
}

.white
{
  background-color: white;
}


.start {
background-color: rgba(0,204,0,0.6);
}

.highlighted {
background-color: rgba(0,255,0,0.6);
}

.drag
{
background-color: rgba(0,204,255,0.6);
}


.selected {
background-color: green;
cursor: grab;
}

.selected img
{
  display:block;
}

.dragged {
  cursor: grabbing;
}

<body data-size=3 onload="start()"
<label for="n">Size: </label><select id="n">
<option>2</option>
<option selected>3</option>
<option>4</option>
<option>5</option>
<option>6</option>
<option>7</option>
<option>8</option>
<option>9</option>
<option>10</option>
</select>
<div>Click or drag to place the piece. Click on the piece to change its type.</div>
</body>

Challenge

Given an nxnxn board, determine if the white king is in checkmate.

Input

• (Optional) n ≥ 2 - the size of the board
• The game board
  • Can be in the form of 1d- 2d- or 3d- array, or other similar format. Notation can be in any simple format. For example, KQRBN (White) and kqrbn (Black) with # for empty cubes. Or, use numbers for the different values.
  • Think of the 3D chess board as multiple boards stacked on top of each other and listed from top to bottom. Then, each individual board is notated from left to right, back to front (Black side to White side).
  • Imagine this 2x2x2 case given as a 3D array:

 [
[[bq][##]]
[[bn][KQ]]
]

"top" board: "bottom" board:

Output

• boolean (truthy/falsy value) - true if white king is in checkmate, false otherwise.

Checkmate

The white king is in check if a black piece threatens to capture it on Black's next turn. To get out of check, White needs to move his king to safety, defend it with another piece, or capture the threatening piece. If White has no way to get out of check, then the white king is in checkmate . Remember, if White is not in check, but can not move without getting into check, then it is a stalemate, which is not a checkmate.

Specification

• You won't be given a board where the black king is trying to "check" the white king, or a board where both kings are in check (impossible scenarios).

Test Cases

1. n=3, [###,n##,#rr],[#b#,###,###],[###,###,bRK]

   (III) (II) (I)

   Output: true

   Explanation: The king is receiving a check from the rook on the top floor. The white rook is unable to block the attack or capture the threatening rook, so the king must try to move out of the way. Let's consider the king's move options:

   1. c2(I) - guarded by bishop at b3(II)
   2. b2(I) - guarded by knight at a2(III)
   3. c1(II) - guarded by rook at c1(III)
   4. b1(II) - guarded by rook at b1(III)
   5. c2(II) - guarded by knight at a2(III)
   6. b2(II) - guarded by bishop at a1(I)

Since the king cannot escape check, it's a checkmate!

2. n=3, [b#b,###,###],[###,###,RNR],[#q#,###,#K#]

   (III) (II) (I)

   Output: false Explanation: The king is receiving a check from the queen, and has no moves to escape or block with. However, the knight can capture the queen.

3. n=3, [#q#,#b#,###],[n##,###,###],[#k#,###,#KB]

   (III) (II) (I)

Output: false Explanation: White has no way of capturing the threatening queen or moving his king to safety. However, by moving his bishop to b2(II), White can block the queen's threat.

4. n=4, [####,####,r###,####],[####,#q##,####,####],[##r#,###b,####,BRnn],[####,####,#N##,#KQ#]

   (IV) (III) (II) (I)

   Output: true Explanation: In this case the king is receiving a check from one of the knights and a queen. Even though White can capture/block one of the checking pieces, he can't capture/block both. Therefore, White must try to move his king out of check, but he has no options.

5. n=3, [###,##b,r#r],[###,###,###],[#k#,###,#K#]

   (III) (II) (I)

Output: false Explanation: White is not in check, but has no way of moving without getting into check. Therefore, it is a stalemate, but not a checkmate.

6. n=3, [##k,###,r#K],[###,n##,#N#],[###,###,#Q#]

   (III) (II) (I)

Output: true Explanation: White would like to swoop in with his queen to defend his king, but his knight is blocking the path.

7. n=3, [###,###,##q],[###,###,###],[#k#,###,rNK]

   (III) (II) (I)

Output: true Explanation: White can not take the queen with his knight, because then the rook will be checking White's king.

8. n=2, [#q,##],[##,K#]

   (II) (I)

Output: false Explanation: White can capture the queen with his king.

9. n=2, [rq,##],[##,K#]

   (II) (I)

Output: true Explanation: This time the rook is guarding, so the king can't capture the queen.

10. n=3, [###,###,#q#],[###,###,###],[#k#,###,BKn]

    (III) (II) (I)

Output: false Explanation: The white king can escape by capturing the knight.

Answer 1

Ruby, 412 413 bytes

->b,w=2{n=b=~/\n/
g=->h{h[0]-~n*(h[1]-~n*h[2])} 
r=1
(n**6).times{|i|a=b*1     
m=[]
9.times{|j|m<<(j<6?i/n**j%n:m[j-6]-m[j-3])}
x,y,z=v=m[6,3].map{|j|j*j}
d=v.max
e=x+y+z
q=95&o=(t=a[p=g[m[3,3]]]).ord
k=a[s=g[m]].ord
o/32==w&&(o^k>31||k==75)&&((q%8==2&&q%9*d==e||q==81&&x%d+y%d+z%d<1)&&((1...c=d**0.5).map{|j|a[p+g[m[6,3]]/c*j]}+[?#]).max<?A||q==78&&e==5||q==75&&e<4)&&(a[p]=?0;a[s]=t;r&&=w>2?a=~/K/:!f[a,3])}
r}

Try it online! Now checked on all test cases. Code increased by 1 byte to fix a bug on case 5 (stalemate case.)

Llambda function requiring input as a string in the format shown below. An optional second parameter can be given, indicating which group of 32 ASCII codes are to be considered on the next move (by default this 2 corresponding to uppercase/white characters, but the function calls itself recursively using 3 corresponding to lowercase/black characters.)

Recursion level 1: Tries all possible moves for white (any cube to any cube) and steps through all the legal ones. Recursion level 2: In each case it then calls itself to step through all possible moves for black. This returns true if the white king has survived all possible black moves. Recursion level 1: If all possible white moves lead to a situation where the white king does NOT survive all possible black moves, then return true (otherwise false.)

In general, a piece cannot move to a square occupied by a friendly piece. In order to consider the case where white does not move at all (hence checkmate not stalemate), the case where the king "moves" to the square he is already on is also allowed. For reasons of short code, the other white pieces are also allowed to move to the square occupied by the white king. This is a nonsense move, but allowing it does not affect the result so it is not a problem.

The following tests are used to check if a move is valid for each piece. x,y,z are the squares of the distances travelled in each axis. e is the sum of these (hence the square of the euclidean distance) and d is the maximum. The piece type is ANDed with 95 to convert lowercase ASCII values to uppercase ones.

Bishop and Rook (ASCII 66 and 82) For the rook e=1*d. For the bishop e=3*d. 
The same code is used for both with q%9 giving 1 and 3 respectively.

Queen (ASCII 81) x%d+y%d+z%d<1 Each axis must be 0 or d, so this sum must be 0.

For the above pieces, any cubes crossed must be checked to ensure they are empty.

Knight (ASCII 78) e=5

King (ASCII 75) e<4

Commented code

->b,w=2{                                                        #board, colour to move (default upcase/white)
  n=b=~/\n/                                                     #n=board size (index of first newline.)
  g=->h{h[0]-~n*(h[1]-~n*h[2])}                                 #Function to calculate position in string based on array of 3d coordinates.
  r=1                                                           #Return value = truthy.
  (n**6).times{|i|                                              #Iterate through n**6 moves (n**3 start cubes and n**3 end cubes.)
    a=b*1      
    m=[]                                                        #Make an empty array for coordinates.                                             
    9.times{|j|m<<(j<6?i/n**j%n:m[j-6]-m[j-3])}                 #Split i into six base n digits for the start and end coordinates. also derive 3 relative move distances.
    x,y,z=v=m[6,3].map{|j|j*j}                                  #v=array of relative distances squared. x,y,z are the 3 individual relative distances squared.
    d=v.max                                                     #Max of x,y,z                                     
    e=x+y+z                                                     #Square of euclidean distance
    q=95&o=(t=a[p=g[m[3,3]]]).ord                               #t=contents of cube to move from. o=ascii value, q=uppercase of o.
    k=a[s=g[m]].ord                                             #k=ascii value of contents of cube to move to.
    o/32==w&&(o^k>31||k==75)&&                                  #If o is in the right 32 byte range (uppercase or lowercase) AND the destination contains the white king or a character not in the same 32 byte range AND...
      ((q%8==2&&q%9*d==e||q==81&&x%d+y%d+z%d<1)&&               #the piece is a rook, bishop or queen with a valid move (as described in the text) AND..
      ((1...c=d**0.5).map{|j|a[p+g[m[6,3]]/c*j]}+[?#]).max<?A|| #the intervening squares are all empty, OR..
      q==78&&e==5||                                             #the piece is a knight and the move has euclidean distance sqrt(5) OR..
      q==75&&e<4)&&                                             #the piece is a king and the move has euclidean distance <4 THEN
      (a[p]=?0;a[s]=t;r&&=w>2?a=~/K/:!f[a,3])                   #put a 0 in the start cube and put the piece in the end cube. If moved piece is black, is the white king still there? AND with return value.
  }                                                             #If moved piece is white, recursively call the f to carry out the black moves. Does the white king NOT survive some black moves? AND with return value.
r}