25
\$\begingroup\$

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: enter image description here "bottom" board: enter image description here

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]

    enter image description here(III) enter image description here(II) enter image description here(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!

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

    enter image description here(III) enter image description here(II) enter image description here(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.

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

    enter image description here(III) enter image description here(II) enter image description here(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.

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

    enter image description here(IV) enter image description here(III) enter image description here(II) enter image description here(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.

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

    enter image description here(III) enter image description here(II) enter image description here(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.

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

    enter image description here(III) enter image description here(II) enter image description here(I)

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

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

    enter image description here(III) enter image description here(II) enter image description here(I)

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

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

    enter image description here(II) enter image description here(I)

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

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

    enter image description here(II) enter image description here(I)

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

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

    enter image description here(III) enter image description here(II) enter image description here(I)

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

\$\endgroup\$
  • \$\begingroup\$ Just a detail, but wouldn't cell.className = (i + j)%2 == 0 ? "black" : "white" be better in the snippet? \$\endgroup\$ – Arnauld Mar 20 '18 at 23:33
  • \$\begingroup\$ @Arnauld lol, forgot to fix the most obvious thing. \$\endgroup\$ – geokavel Mar 21 '18 at 1:29
  • \$\begingroup\$ What is the largest board size we need to support? \$\endgroup\$ – Weijun Zhou Mar 21 '18 at 18:25
  • 1
    \$\begingroup\$ @WeijunZhou Basically you should be able to do the test cases in a reasonable amount of time to see if your code works. For larger numbers it just needs to theoretically work given infinite time and memory. \$\endgroup\$ – geokavel Mar 21 '18 at 18:30
4
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ Couldn't you golf this by using 1-digit ascii values? Also, did you mean "stalemate not checkmate" in the third paragraph? \$\endgroup\$ – geokavel Mar 26 '18 at 2:13
  • \$\begingroup\$ @geokavel The shortest representation of a single ascii value in Ruby is ?A (there is an example in the code) so it's still 2 bytes. Still better than some languages which require "A". There were certain manipulations that went better with the ASCII values rather than the characters (in particular o^k>31 which ensures that a piece can move to an unoccupied square or one occupied by a friendly piece but not a hostile one.) \$\endgroup\$ – Level River St Mar 26 '18 at 2:19
  • \$\begingroup\$ I mean checkmate not stalemate. Stalemate is the situation where the king is threatened if the player moves. Checkmate is the situation where the king is threatened if the player moves, and also if he doesn't. \$\endgroup\$ – Level River St Mar 26 '18 at 2:20
  • \$\begingroup\$ What if you used int values instead of ascii values (i.e array of ints instead of string)? \$\endgroup\$ – geokavel Mar 26 '18 at 2:22
  • \$\begingroup\$ @geokavel ints probably would be shorter, and I may revise it later as it is specifically allowed by the spec. But I went with the chosen format partly because it was more human readable (hence easier to develop) and partly because I was inspired by this answer of mine that heavily influenced my thinking: codegolf.stackexchange.com/a/45544/15599 \$\endgroup\$ – Level River St Mar 26 '18 at 18:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.