Chess960 position lookup

Question

This is a follow-up to Chess960 position generator.

In Chess960, there are 960 possible starting positions that can be enumerated from 0 to 959 (or, at your choice, from 1 to 960). The enumeration scheme is defined in http://en.wikipedia.org/wiki/Chess960_numbering_scheme:

White's Chess960 starting array can be derived from its number N (0 ... 959) as follows:

a) Divide N by 4, yielding quotient N2 and remainder B1. Place a B​ishop upon the bright square corresponding to B1 (0=b, 1=d, 2=f, 3=h).

b) Divide N2 by 4 again, yielding quotient N3 and remainder B2. Place a second B​ishop upon the dark square corresponding to B2 (0=a, 1=c, 2=e, 3=g).

c) Divide N3 by 6, yielding quotient N4 and remainder Q. Place the Q​ueen according to Q, where 0 is the first free square starting from a, 1 is the second, etc.

d) N4 will be a single digit, 0 ... 9. Place the K​n​ights according to its value by consulting the following table:

Digit     Knight positioning
0         N   N   -   -   -
1         N   -   N   -   -
2         N   -   -   N   -
3         N   -   -   -   N
4         -   N   N   -   -
5         -   N   -   N   -
6         -   N   -   -   N
7         -   -   N   N   -
8         -   -   N   -   N
9         -   -   -   N   N

e) There are three blank squares remaining; place a R​ook in each of the outer two and the K​ing in the middle one.

You can find the complete table at http://www.mark-weeks.com/cfaa/chess960/c960strt.htm.

Your task: Write a program that takes an integer as its input and returns the white baseline pieces for that index, e.g.

f(1) = "BQNBNRKR"
f(518) = "RNBQKBNR"

Or, you might as well use unicode "♖♘♗♕♔♗♘♖" if your language supports that.

_{For your inspiration, here's a pretty straight-forward (not optimized) JS implementation: http://jsfiddle.net/Enary/1/}

Answer 1

GolfScript (100 97 95 91 90 84 80 79 chars)

~:?4%2*)?4/4%2*].8,^?16/6%?96/4,{5,>({}+/}%2/=+{1$=.@^}/]'BBQNNRKR'+8/zip${1>}%

This approach follows the instructions forwards rather than backwards. Basically it takes an array of indices and repeatedly removes the selected offsets, leaving them further down the stack; at the end, it gathers them together with the letters and uses them to sort.

Answer 2

Python, 179 chars

i=input()
a=i%4*2+1
b=i/4%4*2
c=i/16%6
d=i/96*5
s='NNRKRNRNKRNRKNRNRKRNRNNKRRNKNRRNKRNRKNNRRKNRNRKRNN'[d:d+5]
s=s[:c]+'Q'+s[c:]
if a>b:a,b=b,a
print s[:a]+'B'+s[a:b-1]+'B'+s[b-1:]

Builds it backwards from the description order so we don't have to count the spaces that are already taken.

Answer 3

C, 221 chars

Explanations:

1. The result is accumulated in r.
2. g calculates division and remainder into n and x.
3. p and P write a character in the n'th available slot.

Interesting points:

1. x~-x is 2*x+1.
2. In !s*!*m, one * serves as &&, the other is dereference.
3. P uses s+0, so with an empty parameter you get +0.

The knights calculation is the hardest, and accounts for the longest line. Can probably be improved.

char*m,r[9],c;
n,x;
g(r){x=n%r;n/=r;}
p(s){!s*!*m?*m=c:p(s-!*m++);}
#define P(s,t);m=r;c=*#t;p(s+0);
main(){
    scanf("%d",&n);
    g(4)P(x-~x,B)
    g(4);r[x*2]=c;
    g(6)P(x,Q)
    P(n>3?(n-=3)>3?(n-=2)>3?n=3:2:1:0,N)
    P(n,N)
    P(,R)P(,K)P(,R)
    puts(r);
}

Answer 4

Javascript, 230 204 200 chars, with Unicode ♖♘♗♕♔♗♘♖

With ideas from chron's Ruby answer and Keith Randall's Python answer

N=prompt();
(r='♘♘♖♔♖♘♖♘♔♖♘♖♔♘♖♘♖♔♖♘♖♘♘♔♖♖♘♔♘♖♖♘♔♖♘♖♔♘♘♖♖♔♘♖♘♖♔♖♘♘'.substr(~~(N/96)*5,5).split(''))[s='splice'](N/16%6,0,'♕');
a=~~(N/4)%4*2;
b=N%4*2;
r[s](a>b?b+1:b,0,B='♗');
r[s](a,0,B);
alert(r.join(''))

(and 194 chars without Unicode)

N=prompt();
(r=btoa('4ÔJDÔM)Q(ÔMD¤MDÓJEJ5M)Q(ÓQD£Q54Ó').substr(~~(N/96)*5,5).split(''))[s='splice'](N/16%6,0,'Q');
a=~~(N/4)%4*2;
b=N%4*2;
r[s](a>b?b+1:b,0,B='B');
r[s](a,0,B);
alert(r.join(''))

I added both newlines and semicolons for readability. You can remove either of them when determining the character count.

Answer 5

GolfScript, 109 80 chars

Using Peter's suggestion for an encoding of the string we can reduce the char count considerably.

~:§96/'€’ŒŽÈÂÄ°²¸'=3base{'KNR'=}%81§16/6%{.3$<@+@@>+}:^~[§4/4%2*§4%2*)]${'B'\^}/

A more or less direct translation of Keith Randall's solution to GolfScript.

Answer 6

Ruby, 150 + 1 chars

Trying a new approach using gsub and $_.

n,$_=$_.to_i,?R*8
{B:[n%4*2+1,n/4%4*2],Q:n/16%6,N:[k=(n/=96)/4+n/7-n/8+n/9,k+1+(n+n/7+n/9*2)%4],K:1}.map{|p,l|x=-1;gsub(?R){[*l].include?(x+=1)?p:$&}}

This needs to be run with the -p flag, and takes the sequence number on stdin. For example:

echo 518 | ruby -p chess960-lookup.rb
RNBQKBNR

Answer 7

vba, 472

Function f(n)
s="--------"
s=r(s,"B",m(n,4)*2)
n=n\4
s=r(s,"B",m(n, 4)*2-1)
n=n\4
s=r(s,"Q",m(n,6))
n=n\6
Select Case n
Case 0:x=1:y=2
Case 1:x=1:y=3
Case 2:x=1:y=4
Case 3:x=1:y=5
Case 4:x=2:y=3
Case 5:x=2:y=4
Case 6:x=2:y=5
Case 7:x=3:y=4
Case 8:x=3:y=5
Case 9:x=4:y=5
End Select
s=r(s,"N",y)
s=r(s,"N",x)
s=r(s,"R",1)
s=r(s,"K",1)
f=r(s,"R",1)
End Function
Function m(n,q)
m=n Mod q+1
End Function
Function r(s,c,p)
r=Replace(Replace(s,"-",c,,p),c,"-",,p-1)
End Function

Answer 8

Excel, 345 bytes

=SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(REPLACE(REPLACE(11111111,2*MOD(A1,4)+2,1,"B"),2*MOD(QUOTIENT(A1,4),4)+1,1,"B"),1,"Q",MOD(QUOTIENT(QUOTIENT(A1,4),4),6)+1),1,"N",CHOOSE(QUOTIENT(QUOTIENT(QUOTIENT(A1,4),4),6)+1,1,1,1,1,2,2,2,3,3,4)),1,"N",CHOOSE(QUOTIENT(QUOTIENT(QUOTIENT(A1,4),4),6)+1,1,2,3,4,2,3,4,3,4,4)),1,"K",2),1,"R")

Breakdown for those interested.

For simplicity, first the codes used to determine the Numbers used:

{N2} =QUOTIENT(A1,4)
{B1} =MOD(A1,4)                               # For Bishop
{N3} =QUOTIENT(QUOTIENT(A1,4),4)
{B2} =MOD(QUOTIENT(A1,4),4)                   # For Bishop
{N4} =QUOTIENT(QUOTIENT(QUOTIENT(A1,4),4),6)  # For Knights
{Q}  =MOD(QUOTIENT(QUOTIENT(A2,4),4),6)       # For Queen

And from the middle outwards:

REPLACE(11111111,2*{B1}+2,1,"B")           # Start with String of '1's
                                           # Place the first Bishop

REPLACE(...,
            2*{B2}+1,1,"B")                # Place Second Bishop

SUBSTITUTE(...,                            # Place Queen in Empty Square
           1,"Q",{Q}+1)

SUBSTITUTE(...,                            # Place first Knight
           1,"N",CHOOSE({N4}+1,            # Using a Lookup
           1,1,1,1,2,2,2,3,3,4))

SUBSTITUTE(...,                            # Place Second Knight
           1,"N",CHOOSE({N4}+1,            # Using a Lookup, with
           1,2,3,4,2,3,4,3,4,4))           # index-1 because other Knight already placed

SUBSTITUTE(...,                            # Place King
            1,"K",2)                       # In second Empty Square

SUBSTITUTE(...,1,"R")                      # Rooks in Remaining Squares

Answer 9

Perl 5, 196 bytes

sub e{$l=int pop;$i=-1;1until!$r[++$i]&&!$l--;$i}$r[$_/4%4*2]=$r[$_%4*2+1]=B;$r[e$_/16%6]=Q;$r[e$a]=$r[e(($n+1,$n-2,$n-3,4)[$a=substr'0000111223',$n=$_/96,1])]=N;$r[e 0]=$r[e 2]=R;$r[e 0]=K;say@r

Try it online!

Answer 10

IA-32 machine code, 99 bytes

Hexdump:

60 68 4e 52 4b 52 68 42 42 51 4e 60 8b fc 8a c1
24 03 d0 e0 40 aa 8a c1 24 0c d0 e8 aa 6a 04 58
91 d3 e8 d4 06 aa 3a e1 72 07 2a e1 49 fe c5 eb
f5 8a c5 aa 02 c4 aa 33 c0 ab 8d 77 17 8b fa ab
ab aa 8b fa 6a 08 59 8a 46 e0 33 db 4b 43 80 3c
1f 00 75 f9 fe c8 7d f5 ac 88 04 1f e2 e9 83 c4
28 61 c3

A pretty straightforward implementation of the rules. First, it calculates the index of each piece, in the order specified by the rules. After placing the knights, the indices of Rook, King and Rook (in that order) are 0.

Then, it converts the indices to "absolute indices", taking into account occupied places. Empty places are marked by a zero byte, and occupied places are marked by the name (letter) of the piece.

Division by 4 is implemented by bit-fiddling. After dividing the starting position by 16 (twice by 4), the quotient is smaller than 256, so it's possible to use aam to divide by 6.

The positions of the knights are determined by a calculation, not by a LUT - the code seems to be smaller that way.

Assembly source code:

    pushad;         // save all registers
    push 'RKRN';    // prepare a LUT of names of pieces
    push 'NQBB';
    pushad;         // allocate temporary variables (values = junk)
    mov edi, esp;   // prepare a pointer to indices of pieces

    // Calculate the index of a Bishop from bits 1 and 0
    mov al, cl;
    and al, 3;
    shl al, 1;
    inc eax;
    stosb;          // store the index of Bishop

    // Calculate the index of a Bishop from bits 3 and 2
    mov al, cl;
    and al, 12;
    shr al, 1;
    stosb;          // store the index of Bishop

    // Divide by 16; also load 4 into ecx
    push 4;
    pop eax;
    xchg eax, ecx;
    shr eax, cl;

    // Divide by 6
    _emit 0xd4;
    _emit 6;
    stosb;          // store the index of Queen

    // Calculate the indices of Knights:
    // Subtract 4, 3, 2, 1 until no longer possible.
    // Knight 1 index: number of times subtraction succeeded
    // Knight 2 index: that, plus remainder
kloop:
    cmp ah, cl;
    jb kdone;
    sub ah, cl;
    dec ecx;
    inc ch;
    jmp kloop;

kdone:
    mov al, ch;
    stosb;          // store the index of Knight
    add al, ah;     // calculate the index of the other knight
    stosb;          // store the index of Knight

    xor eax, eax;
    stosd;          // store indices of Rook, King and Rook

    lea esi, [edi+23]; // point to the names of pieces

    // Fill the output buffer with zeros
    mov edi, edx;
    stosd;
    stosd;
    stosb;
    mov edi, edx;

    // Initialize loop counter for the loop over pieces
    push 8;
    pop ecx;

pc_loop:
    mov al, [esi-32];   // read the index of the piece
    xor ebx, ebx;   // initialize the absolute index
    dec ebx;

pos_loop:
    // Find a zero byte
    inc ebx;
    cmp byte ptr [edi+ebx], 0;
    jne pos_loop;

    // Decrease the index until it hits -1
    dec al;
    jge pos_loop;

    lodsb;          // read the name of the piece
    mov [edi+ebx], al; // store it into the output string

    loop pc_loop;   // repeat for all pieces

    add esp, 40;    // restore stack pointer
    popad;          // restore all registers
    ret;            // return

Answer 11

x86 machine code, 84 bytes

60 4F B9 02 00 BA 03 00 8B D8 23 DA D1 E3 03 D9
C6 01 42 C1 E8 02 E2 F0 33 DB B1 06 F6 F1 FE C4
43 38 29 75 FB FE CC 75 F7 C6 01 51 BB 4A 01 D7
2B DA 47 38 2D 75 FB 32 E4 F6 F2 86 C4 D7 88 05
86 C4 E2 EE AA 61 C3 4B 4E 52 B8 B2 C4 8E B0 C2
8C C8 92 80

This is an even more straightforward implementation adapted from LeanChess960.

Rather than calculate indices, it writes directly to the buffer (which is assumed to contain 0s).

I found the LUT approach to be more economical - it only requires 1 byte per arrangement thanks to ternary encoding of the starting positions (0 - K, 1 - N, 2 - R). LeanChess Barebone editions use a trick that may further reduce the code size by transforming a piece type (0..7) to ASCII (K, N, O, P, Q and R), but I was too lazy to find a transform for KNR (0..2).

Assembly source code:

gen960:
    pusha
    dec di

bishop:
    mov cx, 2
    mov dx, 3

bish_loop:
    mov bx, ax
    and bx, dx
    shl bx, 1
    add bx, cx
    mov byte ptr [di + bx], 'B'
    shr ax, 2
    loop bish_loop

queen:
    xor bx, bx
    mov cl, 6
    div cl
    inc ah

queen_loop:
    inc bx
    cmp [di + bx], ch
    jne queen_loop
    dec ah
    jne queen_loop
    mov byte ptr [di + bx], 'Q'

knr:
    mov bx, offset knr_db
    xlat
    sub bx, dx

knr_loop:
    inc di
    cmp [di], ch
    jne knr_loop
    xor ah, ah
    div dl
    xchg al, ah
    xlat
    mov [di], al
    xchg al, ah
    loop knr_loop

done:
    stosb
    popa
    ret

K  equ 0
N  equ 1
R  equ 2

    db "KNR"

knr_db:
    db N + N * 3 + R * 9 + K * 27 + R * 81
    db N + R * 3 + N * 9 + K * 27 + R * 81
    db N + R * 3 + K * 9 + N * 27 + R * 81
    db N + R * 3 + K * 9 + R * 27 + N * 81
    db R + N * 3 + N * 9 + K * 27 + R * 81
    db R + N * 3 + K * 9 + N * 27 + R * 81
    db R + N * 3 + K * 9 + R * 27 + N * 81
    db R + K * 3 + N * 9 + N * 27 + R * 81
    db R + K * 3 + N * 9 + R * 27 + N * 81
    db R + K * 3 + R * 9 + N * 27 + N * 81