9
\$\begingroup\$

I have previously posted a challenge, smallest number of steps for a knight in chess.

Now I would like to go a step further by adding the possibility to choose your piece.

If you place a piece on any square of a chessboard, what is the smallest number of steps to reach every possible position?

Rules

  • It is an 8 by 8 board.
  • The given input is a coordinate (x, y) and the chosen piece. Explain in the answer how to input the piece of choice.
  • The piece starts at an arbitrary position, taken as input.
  • The pawn can not start at the bottom row, and can not move 2 steps (like when in the start-position) and travels only to the top of the board not downwards.
  • If a piece cannot reach a certain position, use a character of choice to indicate this.

Example

With input (1, 0) for a knight, we start by putting a 0 in that position:

. 0

From here on we continue to fill the entire 8x8 board.

For a knight the output will look as follows:

3 0 3 2 3 2 3 4
2 3 2 1 2 3 4 3
1 2 1 4 3 2 3 4
2 3 2 3 2 3 4 3
3 2 3 2 3 4 3 4
4 3 4 3 4 3 4 5
3 4 3 4 3 4 5 4
4 5 4 5 4 5 4 5

For a pawn with input (1, 7) the output will look like this:

. 6 . . . . . . 
. 5 . . . . . . 
. 4 . . . . . . 
. 3 . . . . . . 
. 2 . . . . . . 
. 1 . . . . . . 
. 0 . . . . . . 
. . . . . . . . 

In the examples, I start counting from zero but it does not matter if you start from zero or one.

Challenge

The pattern printed for a piece, as short as possible, in any reasonable format.

\$\endgroup\$
9
  • 4
    \$\begingroup\$ I think "." is a bad choice for indicating inability to reach a position, as that makes the result mixed-type, which is much harder for certain languages to deal with. I'd go for either something like -1, or incrementing all other values and using 0, or letting the answerer choose a value which cannot otherwise occur. \$\endgroup\$
    – Adám
    Aug 31, 2022 at 7:37
  • 5
    \$\begingroup\$ This feels like it's just 5 separate challenges since every piece is totally different \$\endgroup\$
    – mousetail
    Aug 31, 2022 at 7:39
  • 1
    \$\begingroup\$ @mousetail Maybe there are opportunities for sharing code between, say, rooks, bishops, queens, and kings… \$\endgroup\$
    – Adám
    Aug 31, 2022 at 7:41
  • 1
    \$\begingroup\$ @mousetail, it looks like it, but I have seen amazing stuff and clever solutions on other questions. This makes me curious how this will be solved. And every bit to spare is progress. \$\endgroup\$
    – Bjop
    Aug 31, 2022 at 7:52
  • 2
    \$\begingroup\$ Based on rule "The pawn can not start at the bottom row, and can not move 2 steps (like when in the start-position).", I assume a pawn will always only travel upwards? Might be good to explicitly mention that, so with a pawn input 1,1 the output will be a board with 0 and 1,1 and 1 at 0,1, instead of traveling down. \$\endgroup\$ Aug 31, 2022 at 9:01

3 Answers 3

11
\$\begingroup\$

JavaScript (ES7), 175 bytes

Expects (P, X, Y) where \$X\$ and \$Y\$ are 0-indexed and \$P \in\{3,4,5,6,7,10\}\$, as described in the Piece encoding paragraph below.

f=(P,X,Y,n=0,m=[...s='........'].map(_=>[...s]))=>m.map((r,y)=>r.map((V,x)=>V<=n||(h=(x-X)**2)==(v=(y-Y)**2)&P|h*v==(P&12)-4&&h+v<3|P&2&&y<Y|P-4&&f(P,x,y,n+1,m)),m[Y][X]=n)&&m

Try it online!

Or 171 bytes if we can fill the 'background' with the pattern "Infinity", which I think is pretty nice since it would indeed take an infinity of moves to reach these squares. ;-)

Try it online!

Piece encoding

Each bit in the piece code nibble encodes a specific property used by the move generator.

                    piece  |  P | as binary
                   --------+----+-----------
                    bishop |  3 |  0 0 1 1
                    pawn   |  4 |  0 1 0 0
                    king   |  5 |  0 1 0 1
                    rook   |  6 |  0 1 1 0
                    queen  |  7 |  0 1 1 1
                    knight | 10 |  1 0 1 0
                                   ^ ^ ^ ^
                                   | | | |
             moves like a knight --+ | | |
     moves along ranks and files ----+ | |
can move farther than one square ------+ |
           moves along diagonals --------+

For a pawn, the move generator applies an additional constraint which is not explicitly encoded in the bit mask: it may only move upwards.

Move generator

A move between \$(X,Y)\$ and \$(x,y)\$ is valid if the following test succeeds:

(h = (x - X) ** 2)  // h = squared difference between x and X
==                  // is it equal to ...
(v = (y - Y) ** 2)  // v = squared difference between y and Y?
                    // if yes, this is a move along a diagonal
& P                 // which is valid if bit #0 is set in P
|                   //
h * v ==            // test whether h * v is equal to:
(P & 12) - 4        //   0 if bit #2 is set (move along ranks/files)
                    //   4 if bit #3 is set (knight move)
                    //  -4 otherwise (which always fails)
                    //
&&                  // additional conditions:
  h + v < 3 | P & 2 //   either h + v is less than 3 or bit #1 is set
&&                  //
  y < Y | P - 4     //   either y is less than Y or this is not a pawn
\$\endgroup\$
6
  • \$\begingroup\$ Out of curiosity, why are the numbers of the pieces what they are? (why 3-5-6-7-12 and 19) \$\endgroup\$
    – Bjop
    Aug 31, 2022 at 15:27
  • 2
    \$\begingroup\$ @Bjop I've added a description of the (updated) piece encoding. \$\endgroup\$
    – Arnauld
    Aug 31, 2022 at 16:12
  • \$\begingroup\$ It is a very interesting approach. \$\endgroup\$
    – Bjop
    Sep 1, 2022 at 12:42
  • 1
    \$\begingroup\$ @Bjop About your edit suggestion: it looks great on my PC, but breaks the formatting on my mobile. \$\endgroup\$
    – Arnauld
    Sep 19, 2022 at 13:03
  • 1
    \$\begingroup\$ @Bjop Yes \$\endgroup\$
    – Arnauld
    Sep 19, 2022 at 13:11
7
\$\begingroup\$

APL (Dyalog APL), 133 127 108 100 91 80 70 bytes

{s⍴(⍉(⍺⌷9*(××(×,,,1⍺≠+)⍥|-×+),1 0≢,)/¨∘.-⍨,⍳s)(⊢⌊⌊.+)⍣≡9×⍵≢¨,⍳s←8 8}∘⊂

Attempt This Online!

Update: -19 bytes (127 → 108) by compressing the move matrices
Update: -8 bytes (108 → 100) by simplifying single move function
Update: -9 bytes (100 → 91) by changing the move matrix format
Update: -11 bytes (91 → 80)
Update: -10 bytes (80 → 70) by changing the move matrix format again

I/O

This is a function that takes as arguments

  • the starting square coordinates (Note that APL uses 1-based indexing by default and matrix indices are row number first. So the knight example in the OP has starting coordinates 1 2); and
  • an integer 1~6 for the piece choice, where they correspond to queen, rook, bishop, king, knight, and pawn respectively

The output is an 8×8 matrix, where the starting square is marked as 0 and unreachable squares are marked as 9. This is unambiguous since no piece takes more than 7 moves to reach any reachable square on an 8×8 board.

Explanation

Algorithm Overview

This challenge boils down to a shortest paths problem on an unweighted directed graph, where squares are nodes and edges connect between squares that the chosen piece can move between. It's a directed graph solely because the pawn's move is not reversible.

But, to simplify the implementation, we treat the graph as a complete weighted directed graph, where the weight of an edge is 1 if it represents a move of the chosen piece and ∞ otherwise. As noted above, since 9 is not a possible shortest path length, we can just use 9 as "effectively infinite" and treat everything ≥9 as such.

This way, we can use an iterative algorithm that is similar to Dijkstra's Algorithm, but without tracking visited/unvisited nodes and without node prioritization. Each iteration just processes all edges simultaneously.

Code Overview

The function first, based on the piece choice, generates a 64×64 "move matrix" which is just the adjacency matrix of the 64-node graph.

For example, this is the move matrix of the Queen:

┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
↓1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1│
└~──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

Then it creates the initial board state as an 64-element array of 9s everywhere except 0 at the starting square.

Next, define a function that takes as arguments a "move matrix" and a current board state and "executes one move" by running one iteration of the shortest paths algorithm above.

With these, we can calculate the final output by looping the "single move" function until the output no longer changes (fixpoint).

Finally, we have to reshape that 64-element array as an 8×8 matix

{s⍴(⍉ ... ⍳s)( ... )⍣≡,9×⍵≢¨⍳s←8 8}∘⊂

{                                 }    ⍝ Defines a function that
                       9×⍵≢¨⍳s←8 8     ⍝   Generates the initial board state,
   (⍉ ... ⍳s)                          ⍝   Generates the the move matrix of the 
                                       ⍝     chosen piece,
                    ⍣≡                 ⍝   Calculate the fixpoint of ...
             ( ... )                   ⍝     the "single move" function, and
 s⍴                                    ⍝   Reshape the final board state
                                       ⍝    to an 8×8 matrix
                                   ∘⊂  ⍝ Compose that function with a 
                                       ⍝   preprocessing step of boxing its right 
                                       ⍝   argument

Move matrix generation

(⍉(⍺⌷9*(××(×,,,1⍺≠+)⍥|-×+),1 0≢,)/¨∘.-⍨,⍳s)

Note: The variable s is defined (as 8 8) beforehand, during the initial board state generation explained later.

To generate the move matrix, we first generate a 64-element array of all the 64 coordinates (,⍳s). Then generate the 64×64 matrix of their relative positions by element-wise subtraction between each pair of them (∘.-⍨). For each of those, run a function with the (x,y) delta as right and left argument respectively ((...)/¨). Finally, transpose () that matrix to make the argument order easier to work with.

The inner function treats its two arguments as an (x,y) coordinate pair and returns 1 if the chosen piece can move to that square from (0,0) in a single move and 9 otherwise. It does this by generating the answer for all 6 pieces as a 6-element array, then indexing into that array using the piece choice (⍺⌷). The value for (0,0) does not matter as the "single move" function effectively ignores it.

For example, given (2,2) and piece choice 3 (bishop), the inner function generates 1 9 1 9 9 9 (because only the queen (1) and the bishop (3) can move to (2,2) from (0,0)), then chooses the 3rd element 1.

To generate the 6 answers, we define a tacit function ((××(×,,,1 5≠+)⍥|-×+),1 0≢,) that returns a boolean (i.e. 0 or 1) of whether the corresponding piece is unable to reach that square in one move, then exponentiate with 9 (9*) to get the desired result.

That tacit function, in turn, concatenates the results of 2 different tacit functions, one for the non-pawn pieces ((××(×,,,1 5≠+)⍥|-×+)), and one for the pawn (1 0≢,).

Pawn

1 0≢,

Simply returns whether (x,y) is not exactly () (1,0)

Other pieces

××(×,,,1⍺≠+)⍥|-×+

 ×                   ⍝ Calculate a = x × y
               -×+   ⍝ Calculate b = (x-y) × (x+y)
  (        )⍥|      ⍝ Apply a function with |a| and |b| as arguments
    , ,              ⍝ That function returns a 5-element array by concatenating:
   ×                 ⍝   1)   |a| × |b|              (queen)
     ,               ⍝   2,3) |a| and |b| themselves (rook and bishop)
       1 ≠+          ⍝   4)   whether |a| + |b| ≠ 1  (king)
        ⍺≠+          ⍝   5)   whether |a| + |b| ≠ 5  (knight)
×                     ⍝ Find the signum of those 5 results, because those
                      ⍝   results are 0 if the corresponding piece can move to
                      ⍝   (x,y) and positive otherwise

Notably, this takes advantage of the fact that the 5th entry only matters when the piece choice is 5.

Initial board

9×⍵≢¨,⍳s←8 8

Generates a 64-element array where each entry is a 2-element array corresponding to the coordinates of a square on the board (,⍳8 8), then check each entry against the starting square coordinate (⍵≢¨). This results in an 8×8 boolean matrix which is 0 at the starting square and 1 everywhere else. Multiplying those by 9 () gives the initial board state.

This, as noted, also stores the array 8 8 in variable s along the way, which saves 2 bytes overall.

Single move function

(⊢⌊⌊.+)

The single move function is defined as a tacit function that takes an existing board state and a move matrix and runs one iteration of the shortest paths algorithm. That is, for each edge with weight w, source node value u it generates a "candidate value" u+w for the destination node. The value of each node is then set to the smallest among its original value and all its "candidates".

Note that although the algorithm loops through all edges, it effectively ignores all not-yet-reached source nodes and all edges that does not correspond to the chosen piece's movement, since u is 9 ("effectively infinite") in the former case and w is 9 in the latter case.


To explain the code, let's follow as a reduced example the first iteration of the single move function when choosing rook and starting square (1,2) on a 3×3 board. The algorithm generalizes to any board size.

⍝ move matrix ⍺
┌→────────────────┐
↓1 1 1 1 9 9 1 9 9│
│1 1 1 9 1 9 9 1 9│
│1 1 1 9 9 1 9 9 1│
│1 9 9 1 1 1 1 9 9│
│9 1 9 1 1 1 9 1 9│
│9 9 1 1 1 1 9 9 1│
│1 9 9 1 9 9 1 1 1│
│9 1 9 9 1 9 1 1 1│
│9 9 1 9 9 1 1 1 1│
└~────────────────┘
⍝ Board state ⍵
┌→────────────────┐
│9 0 9 9 9 9 9 9 9│
└~────────────────┘

To calculate candidates, we need to add each entry in the board state to each entry in the corresponding column in the move matrix. Then, to find the best candidate, we need to find the min of each row.

min(1+9, 1+0, 1+9, 1+9, 9+9, 9+9, 1+9, 9+9, 9+9)
min(1+9, 1+0, 1+9, 9+9, 1+9, 9+9, 9+9, 1+9, 9+9)
min(1+9, 1+0, 1+9, 9+9, 9+9, 1+9, 9+9, 9+9, 1+9)
min(1+9, 9+0, 9+9, 1+9, 1+9, 1+9, 1+9, 9+9, 9+9)
min(9+9, 1+0, 9+9, 1+9, 1+9, 1+9, 9+9, 1+9, 9+9)
min(9+9, 9+0, 1+9, 1+9, 1+9, 1+9, 9+9, 9+9, 1+9)
min(1+9, 9+0, 9+9, 1+9, 9+9, 9+9, 1+9, 1+9, 1+9)
min(9+9, 1+0, 9+9, 9+9, 1+9, 9+9, 1+9, 1+9, 1+9)
min(9+9, 9+0, 1+9, 9+9, 9+9, 1+9, 1+9, 1+9, 1+9)

This operation may sound familiar -- it is actually matrix multiplication but with min and + instead of + and ×.

Luckily, APL does have this "generalized matrix multiplication" operation built-in. So that whole "find best candidate for each square" is just ⌊.+.

⍝ {⍺(⌊.+)⍵}
┌→────────────────┐
│1 1 1 9 1 9 9 1 9│
└~────────────────┘

Finally, we finish the iteration by dong element-wise min with the original board state.

⍝ {⍺(⊢⌊⌊.+)⍵}
┌→────────────────┐  
│1 0 1 9 1 9 9 1 9│  
└~────────────────┘  
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 110 bytes

UO⁸ψUB.Nθ⊞υ⟦⁰NN⟧Fυ«≔⊟ιζ≔⊟ιηJζη¿¬℅KKF⁸F⁸«PIΣι≔⁺X⁻λζ²X⁻κη²ε≔⟦⁼↔⁻κη↔⁻λζ∨⁼κη⁼λζ⟧δ¿§⟦›³ε⌈δ⊟δ⊟δ⁼⁵ε∧⁼κ⊖η⁼λζ⟧θ⊞υ⟦⊕Σικλ

Try it online! Link is to verbose version of code. First input is an integer 0 King 1 Queen 2 Rook 3 Bishop 4 Knight 5 Pawn, second input is the column, third input is the row (0-indexed). Explanation:

UO⁸ψUB.

Generate nice output by marking all unreachable squares with .. UO⁸ψ only would mark all unreachable squares with spaces. ψ only would trim trailing whitespace for pawn movements (removing it completely would trim leading whitespace too, which would be unhelpful).

Nθ

Input the piece number.

⊞υ⟦⁰NN⟧

Start a breadth-first search by placing a 0 at the input coordinates.

Fυ«

Loop over the squares as they are discovered.

≔⊟ιζ≔⊟ιηJζη

Jump to the current square.

¿¬℅KK

Check that it hasn't already been visited from a different route.

F⁸F⁸«

Loop over the whole board.

PIΣι

Set the source square to the current number of steps. (This is done inside the board loop to save a byte.)

≔⁺X⁻λζ²X⁻κη²ε

Get the Euclidean distance from the source square to the current square.

≔⟦⁼↔⁻κη↔⁻λζ∨⁼κη⁼λζ⟧δ

Determine whether the source and current squares are a bishop's or a rook's move away.

¿§⟦›³ε⌈δ⊟δ⊟δ⁼⁵ε∧⁼κ⊖η⁼λζ⟧θ

Create a list of six booleans depending on whether the source and current squares are a king's, queen's, rook's, bishop's, knight's or pawn's move away, and index using the input piece number to determine whether the piece can move to the current square.

⊞υ⟦⊕Σικλ

If it can then save this as being potentially one step further away.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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