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