# Chess960 position lookup

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/

## 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.

## 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.

• Good job at combining steps d) and e) using a string literal. I have to admit I had not thought about that, but it looks very efficicent. – user123444555621 Aug 17 '13 at 11:39

## 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);
}


# Javascript, 230204 200 chars, with Unicode ♖♘♗♕♔♗♘♖

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);


(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);


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

### 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.

• You can save at least 24 chars on the magic string using base conversion. It reduces to 12 chars for the literal equivalent of [128 146 140 142 200 194 196 176 178 184]''+ and 17 chars to decode as {3base{'KNR'=}/}%. – Peter Taylor Aug 17 '13 at 9:21
• @PeterTaylor Thought about that also but somehow did it wrong. You can save even more, because you don't need to decode the whole string. – Howard Aug 17 '13 at 12:11

## 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

• Sweet! I like the idea of starting with the king and gathering the royal staff around him – user123444555621 Aug 19 '13 at 10:58
• @Pumbaa80 It actually follows the rules given in the question, in the same order - bishops first, then queen, etc. I'm not creative enough to do anything apart from slavishly following the given algorithm ;) – Paul Prestidge Aug 21 '13 at 5:50
• O right. Somehow I thought it was iterating backwards. I need to improve my ruby skills. – user123444555621 Aug 21 '13 at 8:41

## 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


# 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


# 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!

# 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
ret;            // return


# 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
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

• I think you should add a hex dump of your machine code, as your assembler source requires significantly more than 84 bytes. – Jonathan Frech Dec 18 '19 at 15:16