Пронумеруем строки и столбцы доски размером nxn номерами от 0 до n-1. Номер клетки будет иметь вид (i,j), где i – номер строки, j – номер столбца. Координаты ферзей будут иметь вид (i,p(i)).
Пускай у нас уже расставлены k ферзей в строках от 0 до k-1.
Тогда ферзь с координатами (i,p(i)), где i<k, может бить клетки в строке k с координатами (k,p(i)), (k,p(i)-(k-i)) и (k,p(i)+(k-i)), при этом нас интересуют только клетки с номерами столбцов от 0 до n-1.
Теперь определим битовую маску, для того чтобы определить, в какие клетки строки k нельзя ставить ферзя.
SV(k)=Sum(i=0..k-1,2^p(i))
SD1(k)=Sum(i=0..k-1,2^p(i) shr (k-i))
Если p(i)-(k-i)<0, то 2^p(i) shr (k-i)=0.
SD2(k)=Sum(i=0..k-1,2^p(i) shl (k-i)) and (2^n-1)
Если p(i)+(k-i)>=n, то 2^p(i) shl (k-i) будет отброшено при помощи and (2^n-1).
S(k)=SV(k) or SD1(k) or SD2(k)
где ^ – возведение в степень, or – побитовое или, and – побитовое и, shl – сдвиг влево, shr – сдвиг вправо.
В данном случае используется Sum вместо or, т.к. на любой вертикали или диагонали не может быть более одного ферзя.
Если записать рекуррентно, то получится
SV(0)=0
SD1(0)=0
SD2(0)=0
SV(k+1)=SV(k) or 2^p(k)
SD1(k+1)=(SD1(k) or 2^p(k)) shr 1
SD2(k+1)=((SD2(k) or 2^p(k)) shl 1) and (2^n-1)
Читать полностью »
