Dreidimensionales Schach

26

Um die verblüffende Entscheidung einer Person zu verteidigen, wird oft gesagt, dass diese Person über alle Köpfe geht und „dreidimensionales Schach“ spielt. Jetzt ist es Ihre Chance, dreidimensionales Schach zu spielen!

Regeln

Es gibt viele Varianten von 3D-Schach , aber für diese Herausforderung habe ich meine eigene erfunden. Meine Version ist wie normales Schach, nur dass die Figuren in Würfeln anstatt in Quadraten liegen und jetzt eine zusätzliche Dimension der Bewegung haben. Um diese Herausforderung zu vereinfachen, gibt es keine Bauern und keine Rochade .

Stückbewegung

(Kompassrichtungen beziehen sich auf Bewegungen, die auf einem Standardschachbrett auftreten würden, Auf und Ab beziehen sich auf vertikale Bewegungen auf dem 3D-Schachbrett.)

  • König - hat 26 Felder, die er in einem Zug erreichen kann: N, NE, E, SE, S, SW, W, NW; sowie nach oben, unten und oben / unten + eine der Kompassrichtungen.
  • Königin - kann sich in die gleichen Richtungen wie der König bewegen, aber so weit sie will in diese Richtungen.
  • Turm - kann sich in 6 Richtungen bewegen: N, E, S, W, Oben und Unten,
  • Bischof - hat 8 dreieckige Fahrtrichtungen: NE + Auf / Ab, SE + Auf / Ab, SW + Auf / Ab, NW + Auf / Ab
  • Ritter - bewegt 2 Felder auf einer Achse und dann 1 Feld auf einer anderen. Genau wie beim normalen Schach ist der Ritter das einzige Stück, das über andere Teile springen kann.

Stückprüfgerät

Verwenden Sie dieses Snippet, um zu sehen, wie sich die verschiedenen Teile auf dem 3D-Brett bewegen ( Tipp : Sehen Sie sich die *TestFunktionen im JS an, um schnell zu bestimmen, ob ein Quadrat ein gültiger Zug ist, einfach basierend auf seiner absoluten Entfernung vom Teil.):

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>

Herausforderung

Bei einem gegebenen n x n x n Brett, festzustellen , ob der weiße König in niederlage ist.

Eingang

  • (Optional) n ≥ 2 - die Größe der Platine
  • Das Spielbrett
    • Kann in Form eines 1d-, 2d- oder 3d-Arrays oder eines ähnlichen Formats vorliegen. Notation kann in jedem einfachen Format sein. Zum Beispiel KQRBN (Weiß) und kqrbn (Schwarz) mit # für leere Würfel. Oder verwenden Sie Zahlen für die verschiedenen Werte.
    • Stellen Sie sich das 3D-Schachbrett als mehrere übereinander gestapelte und von oben nach unten aufgeführte Bretter vor. Dann wird jede einzelne Platine von links nach rechts, von hinten nach vorne (von der schwarzen Seite zur weißen Seite) notiert.
    • Stellen Sie sich diesen 2x2x2-Fall als 3D-Array vor:
 [
[[bq] [##]]
[[Mrd.] [KQ]]
]

"top" board: Bildbeschreibung hier eingeben"bottom" board:Bildbeschreibung hier eingeben

Ausgabe

  • Boolescher Wert (wahrheitsgemäßer / falscher Wert) - wahr, wenn sich der weiße König im Schachmatt befindet, sonst falsch.

Schachmatt

Der weiße König ist in Schach, wenn eine schwarze Figur sie in der nächsten Runde von Schwarz zu erobern droht. Um außer Kontrolle zu geraten, muss Weiß seinen König in Sicherheit bringen, ihn mit einer anderen Figur verteidigen oder die bedrohliche Figur erobern. Wenn Weiß nicht außer Kontrolle geraten kann, befindet sich der weiße König im Schachmatt . Denken Sie daran, wenn Weiß nicht in Schach ist, sich aber nicht bewegen kann, ohne in Schach zu geraten, ist es ein Patt , das kein Schachmatt ist.

Spezifikation

  • Sie erhalten keine Tafel, auf der der schwarze König versucht, den weißen König zu "kontrollieren", oder eine Tafel, auf der beide Könige in Kontrolle sind (unmögliche Szenarien).

Testfälle

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

    Bildbeschreibung hier eingeben(III) Bildbeschreibung hier eingeben(II) Bildbeschreibung hier eingeben(I)

    Ausgabe: wahr

    Erklärung: Der König erhält einen Scheck vom Turm in der obersten Etage. Der weiße Turm kann den Angriff nicht abwehren oder den drohenden Turm erobern, daher muss der König versuchen, sich aus dem Weg zu räumen. Betrachten wir die Zugoptionen des Königs:

    1. c2 (I) - bewacht vom Bischof bei b3 (II)
    2. b2 (I) - bewacht von einem Ritter bei a2 (III)
    3. c1 (II) - bewacht von Turm bei c1 (III)
    4. b1 (II) - bewacht von Turm bei b1 (III)
    5. c2 (II) - bewacht von einem Ritter bei a2 (III)
    6. b2 (II) - bewacht vom Bischof bei a1 (I)

Da der König dem Scheck nicht entkommen kann, ist es ein Schachmatt!

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

    Bildbeschreibung hier eingeben(III) Bildbeschreibung hier eingeben(II) Bildbeschreibung hier eingeben(I)

    Ausgabe: false Erläuterung: Der König erhält einen Scheck von der Königin und hat keine Bewegungen, mit denen er entkommen oder blocken kann. Der Ritter kann jedoch die Königin fangen.

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

    Bildbeschreibung hier eingeben(III) Bildbeschreibung hier eingeben(II) Bildbeschreibung hier eingeben(I)

Ausgabe: false Erläuterung: Weiß hat keine Möglichkeit, die bedrohliche Königin zu erobern oder seinen König in Sicherheit zu bringen. Indem Weiß seinen Läufer nach b2 (II) versetzt, kann er die Bedrohung der Königin abwehren.

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

    Bildbeschreibung hier eingeben(IV) Bildbeschreibung hier eingeben(III) Bildbeschreibung hier eingeben(II)Bildbeschreibung hier eingeben (I)

    Ausgabe: wahr Erläuterung: In diesem Fall erhält der König einen Scheck von einem der Ritter und einer Königin. Obwohl Weiß eines der Kontrollstücke erfassen / blockieren kann, kann er nicht beide erfassen / blockieren. Deshalb muss Weiß versuchen, seinen König außer Kontrolle zu bringen, aber er hat keine Wahl.

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

    Bildbeschreibung hier eingeben(III) Bildbeschreibung hier eingeben(II)Bildbeschreibung hier eingeben(I)

Ausgabe: falsch Erläuterung: Weiß ist nicht in Schach, kann sich jedoch nicht bewegen, ohne in Schach zu geraten. Daher ist es ein Patt, aber kein Schachmatt.

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

    Bildbeschreibung hier eingeben(III) Bildbeschreibung hier eingeben(II)Bildbeschreibung hier eingeben(I)

Ausgabe: wahr Erklärung: Weiß würde gerne mit seiner Königin vorbeischauen, um seinen König zu verteidigen, aber sein Ritter blockiert den Weg.

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

    Bildbeschreibung hier eingeben(III) Bildbeschreibung hier eingeben(II) Bildbeschreibung hier eingeben(I)

Ausgabe: wahr Erklärung: Weiß kann die Königin nicht mit seinem Ritter nehmen, weil dann der Turm den König von Weiß prüft.

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

    Bildbeschreibung hier eingeben(II) Bildbeschreibung hier eingeben(I)

Ausgabe: falsch Erklärung: Weiß kann die Königin mit seinem König fangen.

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

    Bildbeschreibung hier eingeben(II) Bildbeschreibung hier eingeben(I)

Ausgabe: true Erläuterung: Diesmal bewacht der Turm, sodass der König die Königin nicht fangen kann.

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

    Bildbeschreibung hier eingeben(III) Bildbeschreibung hier eingeben(II) Bildbeschreibung hier eingeben(I)

Ausgabe: false Erläuterung: Der weiße König kann entkommen, indem er den Ritter gefangen nimmt.

Geokavel
quelle
Nur ein Detail, aber wäre es nicht cell.className = (i + j)%2 == 0 ? "black" : "white"besser im Snippet?
Arnauld
@Arnauld lol, vergaß das offensichtlichste zu reparieren.
Geokavel
Was ist die größte Boardgröße, die wir unterstützen müssen?
Weijun Zhou
1
@WeijunZhou Grundsätzlich sollten Sie in der Lage sein, die Testfälle in angemessener Zeit durchzuführen, um zu überprüfen, ob Ihr Code funktioniert. Für größere Zahlen muss es theoretisch nur bei unendlicher Zeit und unendlichem Gedächtnis funktionieren.
Geokavel

Antworten:

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}

Probieren Sie es online! Jetzt auf alle Testfälle geprüft. Der Code wurde um 1 Byte erhöht, um einen Fehler in Fall 5 (Pattfall) zu beheben.

Llambda-Funktion, für die eine Eingabe als Zeichenfolge im unten gezeigten Format erforderlich ist. Optional kann ein zweiter Parameter angegeben werden, der angibt, welche Gruppe von 32 ASCII-Codes bei der nächsten Verschiebung berücksichtigt werden soll (standardmäßig entspricht dies 2 Groß- / Weißbuchstaben, die Funktion ruft sich jedoch rekursiv mit 3 Kleinbuchstaben / Schwarzbuchstaben auf). )

Rekursionsstufe 1: Versucht alle möglichen Züge für Weiß (von Würfel zu Würfel) und durchläuft alle zulässigen. Rekursionsstufe 2: In jedem Fall ruft es sich dann auf, alle möglichen Züge für Schwarz durchzugehen. Dies ist wahr, wenn der weiße König alle möglichen schwarzen Züge überlebt hat. Rekursionsstufe 1: Wenn alle möglichen weißen Züge zu einer Situation führen, in der der weiße König NICHT alle möglichen schwarzen Züge überlebt, dann gebe wahr zurück (ansonsten falsch).

Im Allgemeinen kann sich eine Figur nicht auf ein Feld bewegen, auf dem sich eine befreundete Figur befindet. Um den Fall zu betrachten, in dem sich Weiß überhaupt nicht bewegt (daher Schachmatt nicht Patt), ist der Fall, in dem sich der König zu dem Feld "bewegt", auf dem er sich bereits befindet, ebenfalls zulässig. Aus Gründen der Kurzwahl dürfen sich auch die anderen weißen Figuren auf das vom weißen König besetzte Feld bewegen. Dies ist ein unsinniger Schachzug, aber das Zulassen hat keinen Einfluss auf das Ergebnis, so dass es kein Problem darstellt.

Die folgenden Tests werden verwendet, um zu überprüfen, ob ein Zug für jedes Stück gültig ist. x,y,zsind die Quadrate der zurückgelegten Strecken in jeder Achse. eist die Summe von diesen (daher das Quadrat der euklidischen Distanz) und dist das Maximum. Der Teiletyp wird mit 95 UND-verknüpft, um ASCII-Kleinbuchstaben in Großbuchstaben umzuwandeln.

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

Kommentierter 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}
Level River St
quelle
Könnten Sie das nicht mit 1-stelligen ASCII-Werten spielen? Meinten Sie im dritten Absatz auch "Patt statt Schachmatt"?
Geokavel
@geokavel Die kürzeste Darstellung eines einzelnen ASCII-Werts in Ruby ist ?A(es gibt ein Beispiel im Code), es sind also immer noch 2 Bytes. Immer noch besser als einige Sprachen, die es erfordern "A". Es gab bestimmte Manipulationen, die mit den ASCII-Werten besser liefen als mit den Zeichen (insbesondere o^k>31, um sicherzustellen, dass ein Teil auf ein freies Feld oder ein Feld verschoben werden kann, das von einem befreundeten, aber nicht feindlichen Teil besetzt ist.)
Level River St
Ich meine Schachmatt nicht Patt. Patt ist die Situation, in der der König bedroht ist, wenn der Spieler zieht. Schachmatt ist die Situation, in der der König bedroht ist, wenn sich der Spieler bewegt und auch, wenn er sich nicht bewegt.
Level River St
Was ist, wenn Sie int-Werte anstelle von ASCII-Werten verwenden (dh ein Array von ints anstelle von string)?
Geokavel
@geokavel ints wäre wahrscheinlich kürzer, und ich kann es später überarbeiten, da es ausdrücklich von der Spezifikation erlaubt ist. Aber ich habe mich für das gewählte Format entschieden, zum Teil, weil es für Menschen besser lesbar ist (und daher einfacher zu entwickeln ist), und zum Teil, weil mich diese Antwort inspiriert hat, die mein Denken stark beeinflusst hat: codegolf.stackexchange.com/a/45544/15599
Level River St