Xadrez Tridimensional

26

Para defender a decisão desconcertante de alguém, as pessoas costumam dizer que essa pessoa está passando por cima da cabeça de todos e jogando "xadrez tridimensional". Agora é sua chance de jogar xadrez tridimensional!

Regras

Existem muitas variantes do 3D Chess , mas para esse desafio eu criei o meu. Minha versão é como o xadrez normal, exceto que as peças estão dentro de cubos, em vez de quadrados, e agora têm uma dimensão adicional de movimento. Para fazer esta simples desafio existem há peões e sem roque .

Movimento das peças

(As direções da bússola referem-se ao movimento que ocorreria em um tabuleiro de xadrez padrão; Cima e Baixo referem-se a mover-se verticalmente no tabuleiro de xadrez 3D).

  • King - possui 26 quadrados em um determinado turno: N, NE, E, SE, S, SW, W, NW; bem como para cima, para baixo e para cima / para baixo + uma das direções da bússola.
  • Rainha - pode se mover nas mesmas direções que o rei, mas até onde ela quiser nessas direções.
  • Torre - pode se mover em 6 direções: N, E, S, W, Para cima e Para baixo,
  • Bishop - tem 8 direções triagonais da viagem: NE + Cima / Baixo, SE + Cima / Baixo, SW + Cima / Baixo, NW + Cima / Baixo
  • Cavaleiro - move 2 espaços em um eixo e depois 1 espaço em outro. Assim como o xadrez normal, o cavaleiro é a única peça que pode pular sobre outras peças.

Testador de peças

Use este trecho para ver como as diferentes peças se movem na placa 3D ( dica : confira as *Testfunções no JS para obter maneiras rápidas de determinar se um quadrado é uma jogada válida, simplesmente com base em sua distância absoluta da peça.):

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>

Desafio

Dado um quadro n x n x n , determine se o rei branco está em xeque-mate.

Entrada

  • (Opcional) n ≥ 2 - o tamanho do quadro
  • O tabuleiro de jogo
    • Pode ser na forma de matriz 1d-2d ou 3d ou outro formato semelhante. A notação pode estar em qualquer formato simples. Por exemplo, KQRBN (Branco) e kqrbn (Preto) com # para cubos vazios. Ou use números para os diferentes valores.
    • Pense no tabuleiro de xadrez 3D como vários tabuleiros empilhados um sobre o outro e listados de cima para baixo. Em seguida, cada quadro individual é anotado da esquerda para a direita, de trás para a frente (lado preto para lado branco).
    • Imagine este gabinete 2x2x2 fornecido como uma matriz 3D:
 [
[[bq] [##]]
[[bn] [KQ]]
]

placa "superior": placa insira a descrição da imagem aqui"inferior":insira a descrição da imagem aqui

Saída

  • booleano (valor verdade / falsidade) - verdadeiro se o rei branco estiver em xeque-mate, caso contrário, falso.

Xeque-mate

O rei branco está em xeque se uma peça preta ameaça capturá-la no próximo turno de Black. Para sair do controle, White precisa mover seu rei para a segurança, defendê-lo com outra peça ou capturar a peça ameaçadora. Se as brancas não têm como sair do controle, o rei branco está no xeque-mate . Lembre-se, se as Brancas não estiverem em xeque, mas não puderem se mover sem entrar em xeque, então é um impasse , que não é um xeque-mate.

Especificação

  • Você não receberá um quadro onde o rei preto está tentando "dar check" ao rei branco, ou um quadro em que os dois reis estejam em xeque (cenários impossíveis).

Casos de teste

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

    insira a descrição da imagem aqui(III) insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

    Saída: true

    Explicação: O rei está recebendo um cheque da torre no último andar. A torre branca é incapaz de bloquear o ataque ou capturar a torre ameaçadora, então o rei deve tentar se afastar. Vamos considerar as opções de movimento do rei:

    1. c2 (I) - guardado pelo bispo em b3 (II)
    2. b2 (I) - guardado por cavaleiro em a2 (III)
    3. c1 (II) - guardado pela torre em c1 (III)
    4. b1 (II) - guardado pela torre em b1 (III)
    5. c2 (II) - guardado por cavaleiro em a2 (III)
    6. b2 (II) - guardado pelo bispo em a1 (I)

Como o rei não pode escapar do cheque, é um xeque-mate!

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

    insira a descrição da imagem aqui(III) insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

    Saída: false Explicação: O rei está recebendo um cheque da rainha e não tem movimentos para escapar ou bloquear. No entanto, o cavaleiro pode capturar a rainha.

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

    insira a descrição da imagem aqui(III) insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

Saída: false Explicação: White não tem como capturar a rainha ameaçadora ou mover seu rei para a segurança. No entanto, movendo seu bispo para b2 (II), as brancas podem bloquear a ameaça da rainha.

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

    insira a descrição da imagem aqui(IV) insira a descrição da imagem aqui(III) insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

    Resultado: true Explicação: Nesse caso, o rei está recebendo um cheque de um dos cavaleiros e uma rainha. Mesmo que White possa capturar / bloquear uma das peças de verificação, ele não pode capturar / bloquear ambas. Portanto, as brancas devem tentar tirar seu rei do controle, mas ele não tem opções.

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

    insira a descrição da imagem aqui(III) insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

Saída: false Explicação: O branco não está em cheque, mas não tem como se mover sem entrar em cheque. Portanto, é um impasse, mas não um xeque-mate.

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

    insira a descrição da imagem aqui(III) insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

Resultado: true Explicação: As brancas gostariam de entrar com sua rainha para defender seu rei, mas seu cavaleiro está bloqueando o caminho.

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

    insira a descrição da imagem aqui(III) insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

Saída: true Explicação: As brancas não podem levar a rainha com seu cavaleiro, porque a torre estará verificando o rei das brancas.

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

    insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

Saída: false Explicação: As brancas podem capturar a rainha com seu rei.

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

    insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

Saída: true Explicação: Desta vez a torre está protegendo, para que o rei não possa capturar a rainha.

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

    insira a descrição da imagem aqui(III) insira a descrição da imagem aqui(II) insira a descrição da imagem aqui(I)

Saída: false Explicação: O rei branco pode escapar capturando o cavaleiro.

geokavel
fonte
Apenas um detalhe, mas não cell.className = (i + j)%2 == 0 ? "black" : "white"seria melhor no snippet?
Arnauld
@ Arnauld lol, esqueci de consertar a coisa mais óbvia.
geokavel
Qual é o maior tamanho de placa que precisamos suportar?
Weijun Zhou
1
@WeijunZhou Basicamente, você poderá executar os casos de teste em um período de tempo razoável para verificar se o seu código funciona. Para números maiores, basta trabalhar teoricamente com tempo e memória infinitos.
precisa saber é

Respostas:

5

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}

Experimente online! Agora verificado em todos os casos de teste. Código aumentado em 1 byte para corrigir um erro no caso 5 (caso de impasse).

Função Llambda que requer entrada como uma string no formato mostrado abaixo. Um segundo parâmetro opcional pode ser fornecido, indicando qual grupo de 32 códigos ASCII deve ser considerado na próxima jogada (por padrão, este 2 corresponde a caracteres maiúsculos / brancos, mas a função se chama recursivamente usando 3 correspondentes a caracteres minúsculos / pretos. )

Nível de recursão 1: tenta todos os movimentos possíveis para branco (qualquer cubo para qualquer cubo) e percorre todos os legais. Nível de recursão 2: em cada caso, ele se autodefine para percorrer todos os movimentos possíveis em preto. Isso retorna verdadeiro se o rei branco tiver sobrevivido a todos os movimentos negros possíveis. Nível de recursão 1: se todos os movimentos brancos possíveis levarem a uma situação em que o rei branco NÃO sobreviva a todos os movimentos negros possíveis, retorne verdadeiro (caso contrário, falso).

Em geral, uma peça não pode se mover para um quadrado ocupado por uma peça amiga. Para considerar o caso em que as brancas não se movem (portanto, xeque-mate e não-impasse), também é permitido o caso em que o rei "se move" para o quadrado em que ele já está. Por razões de código curto, as outras peças brancas também podem mover-se para o quadrado ocupado pelo rei branco. Esta é uma jogada sem sentido, mas permitir que ela não afete o resultado, portanto não é um problema.

Os testes a seguir são usados ​​para verificar se um movimento é válido para cada peça. x,y,zsão os quadrados das distâncias percorridas em cada eixo. eé a soma destes (daí o quadrado da distância euclidiana) e dé o máximo. O tipo de peça é AND com 95 para converter valores ASCII minúsculos em maiúsculos.

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

Código comentado

->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}
Level River St
fonte
Você não poderia jogar isso usando valores ASCII de um dígito? Além disso, você quis dizer "impasse não xeque-mate" no terceiro parágrafo?
geokavel
@geokavel A representação mais curta de um único valor ASCII no Ruby é ?A(existe um exemplo no código), portanto, ele ainda tem 2 bytes. Ainda melhor do que alguns idiomas que exigem "A". Houve certas manipulações que foram melhores com os valores ASCII do que com os caracteres (em particular, o o^k>31que garante que uma peça possa se mover para um quadrado desocupado ou ocupado por uma peça amiga, mas não hostil.)
Level River St
Quero dizer xeque-mate, não impasse. O empate é a situação em que o rei é ameaçado se o jogador se mover. Xeque-mate é a situação em que o rei é ameaçado se o jogador se mover e também se ele não o fizer.
Level River St
E se você usasse valores int em vez de valores ascii (ou seja, matriz de ints em vez de string)?
geokavel
O @geokavel ints provavelmente seria menor, e eu posso revisá-lo mais tarde, pois é especificamente permitido pelas especificações. Mas eu fui com o formato escolhido, em parte porque era mais legível para o ser humano (portanto, mais fácil de desenvolver) e em parte porque fui inspirado por essa minha resposta que influenciou fortemente meu pensamento: codegolf.stackexchange.com/a/45544/15599
Nível Rio St