Biorąc pod uwagę liczbę całkowitą 2n, znajdź liczbę możliwych sposobów ułożenia 2n ^ 2 czarnych pionków i 2n ^ 2 białych pionków na szachownicy 2n przez 2n, tak aby żaden pionek nie atakował innego.

• Czarny pionek może atakować tylko białego pionka i odwrotnie.
• Stosowane są zwykłe zasady szachowe ataku, tj. Białe pionki atakują kwadraty bezpośrednio po przekątnej z przodu, a czarne pionki atakują kwadraty natychmiast po przekątnej do tyłu (jak widzi biały obserwator).
• Cały obrót, odbicia liczą się jako odrębne.

Wygrywa program, który może wypisać wszystkie możliwe konfiguracje dla najwyższej wartości 2n w 120 sekund. (Wszystkie programy są mile widziane)

Na przykład program Alicji może poradzić sobie z upto n = 16 w ciągu 120 sekund, podczas gdy program Boba może poradzić sobie z upto n = 20 w tym samym czasie. Bob wygrywa.

Platforma: Linux 2.7GHz @ 4 procesory

Java, n = 87 na moim komputerze

Wynik dla n = 87 wynosi

62688341832480765224168252369740581641682638216282495398959252035334029997073369148728772291668336432168

import java.math.BigInteger;

public class NonattackingPawns {

    static BigInteger count(int n) {
        BigInteger[][] a0 = new BigInteger[n+1][n*n+1], a1 = new BigInteger[n+1][n*n+1], tm;

        for(int h = 0; h <= n; h++) a0[h][0] = h%2==0? BigInteger.ONE: BigInteger.ZERO;

        for(int c = 1; c <= 2*n; c++) {     
            int minp = 0;
            for(int h = 0; h <= n; h++) {
                java.util.Arrays.fill(a1[h], BigInteger.ZERO);
                if(h>0) minp += c >= 2*h-c%2 ? 2*h - c%2 : c;

                int maxp = Math.min(n*(c-1)+h, n*n);
                for(int p = minp; p <= maxp; p++) {
                    BigInteger sum = a0[h][p-h];

                    if(c%2==1 && h>0) 
                        sum = sum.add(a0[h-1][p-h]);
                    else if(c%2==0 && h<n) 
                        sum = sum.add(a0[h+1][p-h]);

                    a1[h][p] = sum;
                }
            }
            tm=a0; a0=a1; a1=tm;
        }
        BigInteger[] s = new BigInteger[n*n+1];
        for(int p = 0; p <= n*n; p++) {
            BigInteger sum = BigInteger.ZERO;
            for(int h = 0; h <= n; h++) sum = sum.add(a0[h][p]);
            s[p] = sum;

        }

        BigInteger ans = BigInteger.ZERO;
        for(int p = 0; p < n*n; p++) ans = ans.add(s[p].multiply(s[p]));
        return ans.shiftLeft(1).add(s[n*n].multiply(s[n*n]));
    }

    public static void main(String[] args) {
        for(int n = 0;; n++) {
            System.out.println(n + " " + count(n));
        }
    }

}

Obecnie korzysta z dynamicznego schematu programowania, który przyjmuje operacje O (n ^ 4), aby obliczyć sposoby umieszczania ppionków na kwadratach jednego koloru 0 <= p <= n^2. Myślę, że powinno być to możliwe znacznie wydajniej.

Sprawdź wyniki tutaj.

Wyjaśnienie

W prawidłowym rozwiązaniu najniższe białe pionki w każdej kolumnie muszą tworzyć zygzakowatą linię:

Oznacza to, że wysokość linii w kolumnie c musi wynosić +/- 1 od jej pozycji w kolumnie c - 1 . Linia może również przechodzić do dwóch wyimaginowanych rzędów powyżej górnej części planszy.

Możemy użyć programowania dynamicznego, aby znaleźć liczbę sposobów narysowania linii na pierwszych c kolumnach, które zawierają p pionki na tych kolumnach, jest na wysokości h na c- tej kolumnie, wykorzystując wyniki dla kolumny c - 1 , wysokości h + / - 1 , a liczba pionków p - h .

Jawa

Obecnie mój kod jest bardzo długi i żmudny, pracuję nad tym, aby był szybszy. Używam metody rekurencyjnej, aby znaleźć wartości. Oblicza pierwsze 5 w ciągu 2 lub 3 sekund, ale potem robi się znacznie wolniej. Ponadto nie jestem jeszcze pewien, czy liczby są prawidłowe, ale wydaje się, że pierwszych kilka zgadza się z komentarzami. Wszelkie sugestie są mile widziane.

Wynik

2x2:    3
4x4:    30
6x6:    410
8x8:    6148
10x10:  96120

Wyjaśnienie

Podstawową ideą jest rekurencja. Zasadniczo zaczynasz od pustej planszy, planszy ze wszystkimi zerami. Metoda rekurencyjna sprawdza tylko, czy może umieścić czarnego lub białego pionka w następnej pozycji, jeśli może umieścić tylko jeden kolor, umieszcza go tam i wywołuje. Jeśli umieści oba kolory, nazywa się dwa razy, po jednym z każdym kolorem. Za każdym razem, gdy się wywołuje, zmniejsza kwadraty w lewo i pozostawia odpowiedni kolor. Po wypełnieniu całej planszy zwraca bieżącą liczbę + 1. Jeśli stwierdzi, że nie ma sposobu, aby umieścić czarnego lub białego pionka w następnej pozycji, zwraca 0, co oznacza, że ​​jest to martwa ścieżka.

Kod

public class Chess {
    public static void main(String[] args){
        System.out.println(solve(1));
        System.out.println(solve(2));
        System.out.println(solve(3));
        System.out.println(solve(4));
        System.out.println(solve(5));
    }
    static int solve(int n){
        int m =2*n;
        int[][] b = new int[m][m];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                b[i][j]=0;
            }
        }
        return count(m,m*m,m*m/2,m*m/2,0,b);
    }
    static int count(int n,int sqLeft, int bLeft, int wLeft, int count, int[][] b){
        if(sqLeft == 0){
            /*for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    System.out.print(b[i][j]);
                }
                System.out.println();
            }
            System.out.println();*/
            return count+1;
        }
        int x=(sqLeft-1)%n;
        int y=(sqLeft-1)/n;
        if(wLeft==0){
            if(y!=0){
                if ((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!= 1)) {
                    b[x][y] = 2;
                    return count(n, sqLeft-1, bLeft-1, wLeft, count, b);
                } else {
                    return 0;
                }
            } else {
                b[x][y]=2;
                return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
            }
        } else if(bLeft==0){
            if(y!=n-1){
                if((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
                    b[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
                } else {
                    return 0;
                }
            } else {
                b[x][y]=1;
                return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
            }
        } else{
            if(y==0){
                if((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
                    int[][] c=new int[n][n];
                    for(int i = 0; i < n; i++){
                        System.arraycopy(b[i], 0, c[i], 0, n);
                    }
                    b[x][y]=2;
                    c[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                } else {
                    b[x][y]=2;
                    return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                }
            }else if(y==n-1){
                if((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1)){
                    int[][] c=new int[n][n];
                    for(int i = 0; i < n; i++){
                        System.arraycopy(b[i], 0, c[i], 0, n);
                    }
                    b[x][y]=2;
                    c[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                } else {
                    b[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
                }
            }else{
                if(((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1))&&((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2))){
                    int[][] c=new int[n][n];
                    for(int i = 0; i < n; i++){
                        System.arraycopy(b[i], 0, c[i], 0, n);
                    }
                    b[x][y]=2;
                    c[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                } else if ((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1)){
                    b[x][y]=2;
                    return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                } else if ((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
                    b[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
                } else {
                    return 0;
                }
            }
        }
    }
}

Wypróbuj tutaj (nie działa wystarczająco szybko dla Ideone, więc ostatnia wartość nie jest drukowana, wygląda na to, że moje rozwiązanie nie jest zbyt dobre!)

C ++ z pthreads, n = 147 156

Najnowszy wynik to uruchomienie tego samego kodu, co poprzednio, na maszynie o większej mocy. To było teraz uruchomione na pulpicie z czterordzeniowym i7 (Core i7-4770), który osiągnął n = 156 w 120 sekund. Wynik to:

78581036888824823496962250906481423170934266912694416068935442570913159064317737026762661986430581489873651515605659228918524818470493215413475827287931751145438401644066743.

Wykorzystuje to algorytm programowania dynamicznego. Początkowo zastanawiałem się nad podejściami, w których wynik byłby budowany rząd po rzędzie, ale nigdy nie mogłem znaleźć sposobu na rozszerzenie rozwiązania bez śledzenia tony stanu.

Kluczowymi spostrzeżeniami, które umożliwiły racjonalnie skuteczne rozwiązanie, były:

• Ponieważ pionki na czarnych kwadratach mogą atakować pionki tylko na innych czarnych kwadratach, i to samo dotyczy białych kwadratów, czarne i białe kwadraty są niezależne i mogą być przetwarzane osobno. A ponieważ są one równoważne, musimy przetworzyć tylko jeden z dwóch.
• Problem staje się znacznie łatwiejszy przy przetwarzaniu płyty po przekątnej.

Jeśli spojrzysz na jedną przekątną prawidłowej konfiguracji, zawsze składa się ona z sekwencji czarnych pionków, a następnie sekwencji białych pionków (gdzie każda z sekwencji może być również pusta). Innymi słowy, każdą przekątną można w pełni scharakteryzować liczbą czarnych pionków.

Dlatego stan śledzony dla każdej przekątnej to liczba prawidłowych konfiguracji pionków dla każdej kombinacji:

• Liczba czarnych pionków w rzędzie (lub innymi słowy pozycja w przekątnej, która oddziela czarne pionki od białych pionków).
• Łączna liczba użytych czarnych pionków. Musimy śledzić całą liczbę na pion, ponieważ potrzebujemy tylko takiej samej liczby czarnych i białych pionków na samym końcu. Podczas przetwarzania przekątnych liczby mogą być różne i nadal kończą się poprawnymi rozwiązaniami.

Przechodząc od jednej przekątnej do następnej, istnieje inne ograniczenie do budowania prawidłowych rozwiązań: Pozycja oddzielająca czarne pionki od białych pionków nie może wzrosnąć. Tak więc liczba prawidłowych konfiguracji jest obliczana jako suma prawidłowych konfiguracji poprzedniej przekątnej dla pozycji, które są równe lub większe.

Podstawowy krok DP jest wtedy bardzo prosty. Każda wartość na przekątnej jest tylko sumą wartości z poprzedniej przekątnej. Jedyną nieco bolesną częścią jest prawidłowe obliczanie wskaźników i zakresów pętli. Ponieważ pracujemy nad przekątnymi, długość zwiększa się w pierwszej połowie obliczeń, a zmniejsza w drugiej połowie, co sprawia, że ​​obliczanie zakresów pętli jest bardziej skomplikowane. Należy również wziąć pod uwagę wartości na granicy tablicy, ponieważ mają one tylko sąsiadujących po przekątnej sąsiadów po jednej stronie podczas przechodzenia od przekątnej do przekątnej.

Ilość używanej pamięci to O (n ^ 3). Trzymam dwie kopie danych stanu i między nimi ping ponga. Wierzę, że byłoby możliwe działanie z jedną instancją danych stanu. Ale trzeba bardzo uważać, aby żadne wartości nie były aktualizowane, zanim stare wartości zostaną w pełni wykorzystane. Ponadto nie działałoby to dobrze w przypadku równoległego przetwarzania, które wprowadziłem.

Złożoność środowiska wykonawczego jest ... wielomianowa. Algorytm zawiera 4 zagnieżdżone pętle, więc na pierwszy rzut oka wyglądałoby to jak O (n ^ 4). Ale oczywiście potrzebujesz bigintów w tych rozmiarach, a same liczby stają się dłuższe w większych rozmiarach. Liczba cyfr w wyniku wydaje się rosnąć mniej więcej proporcjonalnie do n, co dałoby całość O (n ^ 5). Z drugiej strony znalazłem pewne ulepszenia wydajności, które pozwalają uniknąć przejścia przez pełny zakres wszystkich pętli.

Chociaż jest to wciąż dość drogi algorytm, staje się on znacznie szerszy niż algorytmy wyliczające rozwiązania, które są wykładnicze.

Kilka uwag na temat wdrożenia:

• Podczas gdy na czarnych kwadratach może znajdować się do 2 * n ^ 2 czarnych pionków, obliczam tylko numery konfiguracji do n ^ 2 czarnych pionków. Ponieważ istnieje symetria między czarnymi i białymi pionkami, liczba konfiguracji dla k i 2 * n ^ 2-k jest taka sama.
• Liczba rozwiązań jest obliczana na końcu z konfiguracji liczonych na czarnych kwadratach w oparciu o podobną symetrię. Całkowita liczba rozwiązań (które muszą mieć 2 * n ^ 2 pionków każdego koloru) to liczba konfiguracji dla k czarnych pionków w jednym kolorze kwadratów pomnożona przez liczbę konfiguracji dla 2 * n ^ 2-k czarnych pionków na inny kolor kwadratów, zsumowany na całym k.
• Oprócz tylko przechowywania liczb konfiguracji dla pozycji po przekątnej i liczby pionków, przechowuję również zakres liczby pionów, które mają prawidłowe konfiguracje dla pozycji. Pozwala to znacznie zmniejszyć zasięg wewnętrznej pętli. Bez tego zauważyłem, że dodawanych jest wiele zer. Dzięki temu uzyskałem bardzo znaczną poprawę wydajności.
• Algorytm działa dość dobrze równolegle, szczególnie przy dużych rozmiarach. Przekątne muszą być przetwarzane sekwencyjnie, więc na końcu każdej przekątnej znajduje się bariera. Ale pozycje w przekątnej można przetwarzać równolegle.
• Profilowanie pokazuje, że wąskim gardłem jest wyraźne dodawanie wartości bigint. Bawiłem się kilkoma odmianami kodu, ale nie jest on mocno zoptymalizowany. Podejrzewam, że może istnieć znacząca poprawa w porównaniu z montażem wbudowanym do korzystania z 64-bitowych dodatków z funkcją carry.

Główny kod algorytmu. THREADSkontroluje liczbę używanych wątków, przy czym liczba rdzeni procesora powinna być rozsądnym punktem wyjścia:

#ifndef THREADS
#define THREADS 2
#endif

#if THREADS > 1
#include <pthread.h>
#endif

#include <vector>
#include <iostream>
#include <sstream>

#include "BigUint.h"

typedef std::vector<BigUint> BigUintVec;
typedef std::vector<int> IntVec;

static int N;
static int NPawn;
static int NPos;

static BigUintVec PawnC[2];
static IntVec PawnMinC[2];
static IntVec PawnMaxC[2];

#if THREADS > 1
static pthread_mutex_t ThreadMutex;
static pthread_cond_t ThreadCond;
static int BarrierCount;
#endif

#if THREADS > 1
static void ThreadBarrier()
{
    pthread_mutex_lock(&ThreadMutex);

    --BarrierCount;
    if (BarrierCount)
    {
        pthread_cond_wait(&ThreadCond, &ThreadMutex);
    }
    else
    {
        pthread_cond_broadcast(&ThreadCond);
        BarrierCount = THREADS;
    }

    pthread_mutex_unlock(&ThreadMutex);
}
#endif

static void* countThread(void* pData)
{
    int* pThreadIdx = static_cast<int*>(pData);
    int threadIdx = *pThreadIdx;

    int prevDiagMin = N - 1;
    int prevDiagMax = N;

    for (int iDiag = 1; iDiag < 2 * N; ++iDiag)
    {
        BigUintVec& rSrcC = PawnC[1 - iDiag % 2];
        BigUintVec& rDstC = PawnC[iDiag % 2];

        IntVec& rSrcMinC = PawnMinC[1 - iDiag % 2];
        IntVec& rDstMinC = PawnMinC[iDiag % 2];

        IntVec& rSrcMaxC = PawnMaxC[1 - iDiag % 2];
        IntVec& rDstMaxC = PawnMaxC[iDiag % 2];

        int diagMin = prevDiagMin;
        int diagMax = prevDiagMax;;
        if (iDiag < N)
        {
            --diagMin;
            ++diagMax;
        }
        else if (iDiag > N)
        {
            ++diagMin;
            --diagMax;
        }

        int iLastPos = diagMax;
        if (prevDiagMax < diagMax)
        {
            iLastPos = prevDiagMax;
        }

        for (int iPos = diagMin + threadIdx; iPos <= iLastPos; iPos += THREADS)
        {
            int nAdd = iPos - diagMin;

            for (int iPawn = nAdd; iPawn < NPawn; ++iPawn)
            {
                rDstC[iPos * NPawn + iPawn] = 0;
            }

            rDstMinC[iPos] = NPawn;
            rDstMaxC[iPos] = -1;

            int iFirstPrevPos = iPos;
            if (!nAdd)
            {
                iFirstPrevPos = prevDiagMin;
            }

            for (int iPrevPos = iFirstPrevPos;
                 iPrevPos <= prevDiagMax; ++iPrevPos)
            {
                int iLastPawn = rSrcMaxC[iPrevPos];
                if (iLastPawn + nAdd >= NPawn)
                {
                    iLastPawn = NPawn - 1 - nAdd;
                }

                if (rSrcMinC[iPrevPos] > iLastPawn)
                {
                    continue;
                }

                if (rSrcMinC[iPrevPos] < rDstMinC[iPos])
                {
                    rDstMinC[iPos] = rSrcMinC[iPrevPos];
                }

                if (iLastPawn > rDstMaxC[iPos])
                {
                    rDstMaxC[iPos] = iLastPawn;
                }

                for (int iPawn = rSrcMinC[iPrevPos];
                     iPawn <= iLastPawn; ++iPawn)
                {
                    rDstC[iPos * NPawn + iPawn + nAdd] += rSrcC[iPrevPos * NPawn + iPawn];
                }
            }

            if (rDstMinC[iPos] <= rDstMaxC[iPos])
            {
                rDstMinC[iPos] += nAdd;
                rDstMaxC[iPos] += nAdd;
            }
        }

        if (threadIdx == THREADS - 1 && diagMax > prevDiagMax)
        {
            int pawnFull = (iDiag + 1) * (iDiag + 1);
            rDstC[diagMax * NPawn + pawnFull] = 1;
            rDstMinC[diagMax] = pawnFull;
            rDstMaxC[diagMax] = pawnFull;
        }

        prevDiagMin = diagMin;
        prevDiagMax = diagMax;

#if THREADS > 1
        ThreadBarrier();
#endif
    }

    return 0;
}

static void countPawns(BigUint& rRes)
{
    NPawn = N * N + 1;
    NPos = 2 * N;

    PawnC[0].resize(NPos * NPawn);
    PawnC[1].resize(NPos * NPawn);

    PawnMinC[0].assign(NPos, NPawn);
    PawnMinC[1].assign(NPos, NPawn);

    PawnMaxC[0].assign(NPos, -1);
    PawnMaxC[1].assign(NPos, -1);

    PawnC[0][(N - 1) * NPawn + 0] = 1;
    PawnMinC[0][N - 1] = 0;
    PawnMaxC[0][N - 1] = 0;

    PawnC[0][N * NPawn + 1] = 1;
    PawnMinC[0][N] = 1;
    PawnMaxC[0][N] = 1;

#if THREADS > 1
    pthread_mutex_init(&ThreadMutex, 0);
    pthread_cond_init(&ThreadCond, 0);

    BarrierCount = THREADS;

    int threadIdxA[THREADS] = {0};
    pthread_t threadA[THREADS] = {0};
    for (int iThread = 0; iThread < THREADS; ++iThread)
    {
        threadIdxA[iThread] = iThread;
        pthread_create(threadA + iThread, 0, countThread, threadIdxA + iThread);
    }

    for (int iThread = 0; iThread < THREADS; ++iThread)
    {
        pthread_join(threadA[iThread], 0);
    }

    pthread_cond_destroy(&ThreadCond);
    pthread_mutex_destroy(&ThreadMutex);
#else
    int threadIdx = 0;
    countThread(&threadIdx);
#endif

    BigUint solCount;
    BigUintVec& rResC = PawnC[1];
    for (int iPawn = 0; iPawn < NPawn; ++iPawn)
    {
        BigUint nComb = rResC[(N - 1) * NPawn + iPawn];

        nComb *= nComb;
        if (iPawn < NPawn - 1)
        {
            nComb *= 2;
        }

        solCount += nComb;
    }

    std::string solStr;
    solCount.toDecString(solStr);
    std::cout << solStr << std::endl;
}

int main(int argc, char* argv[])
{
    std::istringstream strm(argv[1]);
    strm >> N;

    BigUint res;
    countPawns(res);

    return 0;
}

To także potrzebuje klasy bigint, którą napisałem w tym celu. Zauważ, że nie jest to klasa bigint ogólnego przeznaczenia. To wystarczy, aby obsłużyć operacje używane przez ten konkretny algorytm:

#ifndef BIG_UINT_H
#define BIG_UINT_H

#include <cstdint>
#include <string>
#include <vector>

class BigUint
{
public:
    BigUint()
      : m_size(1),
        m_cap(MIN_CAP),
        m_valA(m_fixedValA)
    {
        m_valA[0] = 0;
    }

    BigUint(uint32_t val)
      : m_size(1),
        m_cap(MIN_CAP),
        m_valA(m_fixedValA)
    {
        m_valA[0] = val;
    }

    BigUint(const BigUint& rhs)
      : m_size(rhs.m_size),
        m_cap(MIN_CAP),
        m_valA(m_fixedValA)
    {
        if (m_size > MIN_CAP)
        {
            m_cap = m_size;
            m_valA = new uint32_t[m_cap];
        }

        for (int iVal = 0; iVal < m_size; ++iVal)
        {
            m_valA[iVal] = rhs.m_valA[iVal];
        }
    }

    ~BigUint()
    {
        if (m_cap > MIN_CAP)
        {
            delete[] m_valA;
        }
    }

    BigUint& operator=(uint32_t val)
    {
        m_size = 1;
        m_valA[0] = val;

        return *this;
    }

    BigUint& operator=(const BigUint& rhs)
    {
        if (rhs.m_size > m_cap)
        {
            if (m_cap > MIN_CAP)
            {
                delete[] m_valA;
            }

            m_cap = rhs.m_size;
            m_valA = new uint32_t[m_cap];
        }

        m_size = rhs.m_size;

        for (int iVal = 0; iVal < m_size; ++iVal)
        {
            m_valA[iVal] = rhs.m_valA[iVal];
        }

        return *this;
    }

    BigUint& operator+=(const BigUint& rhs)
    {
        if (rhs.m_size > m_size)
        {
            resize(rhs.m_size);
        }

        uint64_t sum = 0;
        for (int iVal = 0; iVal < m_size; ++iVal)
        {
            sum += m_valA[iVal];
            if (iVal < rhs.m_size)
            {
                sum += rhs.m_valA[iVal];
            }
            m_valA[iVal] = sum;
            sum >>= 32u;
        }

        if (sum)
        {
            resize(m_size + 1);
            m_valA[m_size - 1] = sum;
        }

        return *this;
    }

    BigUint& operator*=(const BigUint& rhs)
    {
        int resSize = m_size + rhs.m_size - 1;
        uint32_t* resValA = new uint32_t[resSize];

        uint64_t sum = 0;

        for (int iResVal = 0; iResVal < resSize; ++iResVal)
        {
            uint64_t carry = 0;

            for (int iLhsVal = 0;
                 iLhsVal <= iResVal && iLhsVal < m_size; ++iLhsVal)
            {
                int iRhsVal = iResVal - iLhsVal;
                if (iRhsVal < rhs.m_size)
                {
                    uint64_t prod = m_valA[iLhsVal];
                    prod *= rhs.m_valA[iRhsVal];
                    uint64_t newSum = sum + prod;
                    if (newSum < sum)
                    {
                        ++carry;
                    }
                    sum = newSum;
                }
            }

            resValA[iResVal] = sum & UINT64_C(0xFFFFFFFF);
            sum >>= 32u;
            sum += carry << 32u;
        }

        if (resSize > m_cap)
        {
            if (m_cap > MIN_CAP)
            {
                delete[] m_valA;
            }

            m_cap = resSize;
            m_valA = resValA;
        }
        else
        {
            for (int iVal = 0; iVal < resSize; ++iVal)
            {
                m_valA[iVal] = resValA[iVal];
            }

            delete[] resValA;
        }

        m_size = resSize;

        if (sum)
        {
            resize(m_size + 1);
            m_valA[m_size - 1] = sum;
        }

        return *this;
    }

    void divMod(uint32_t rhs, uint32_t& rMod)
    {
        uint64_t div = 0;
        for (int iVal = m_size - 1; iVal >= 0; --iVal)
        {
            div <<= 32u;
            div += m_valA[iVal];

            uint64_t val = div / rhs;
            div -= val * rhs;

            if (val || iVal == 0 || iVal < m_size - 1)
            {
                m_valA[iVal] = val;
            }
            else
            {
                --m_size;
            }
        }

        rMod = div;
    }

    void toDecString(std::string& rStr) const
    {
        std::vector<char> digits;

        BigUint rem(*this);
        while (rem.m_size > 1 || rem.m_valA[0])
        {
            uint32_t digit = 0;
            rem.divMod(10, digit);
            digits.push_back(digit);
        }

        if (digits.empty())
        {
            rStr = "0";
        }
        else
        {
            rStr.clear();
            rStr.reserve(digits.size());

            for (int iDigit = digits.size() - 1; iDigit >= 0; --iDigit)
            {
                rStr.append(1, '0' + digits[iDigit]);
            }
        }
    }

private:
    static const int MIN_CAP = 8;

    void resize(int newSize)
    {
        if (newSize > m_cap)
        {
            uint32_t* newValA = new uint32_t[newSize];

            for (int iVal = 0; iVal < m_size; ++iVal)
            {
                newValA[iVal] = m_valA[iVal];
            }

            if (m_cap > MIN_CAP)
            {
                delete[] m_valA;
            }

            m_cap = newSize;
            m_valA = newValA;
        }

        for (int iVal = m_size; iVal < newSize; ++iVal)
        {
            m_valA[iVal] = 0;
        }

        m_size = newSize;
    }

    int m_size;
    int m_cap;

    uint32_t* m_valA;
    uint32_t m_fixedValA[MIN_CAP];
};

#endif // BIG_UINT_H

Fantom

Oto pierwszy post, który konfiguruje framework. Myślę, że procedura jest stosunkowo dobra, ale wdrożenie jest w tej chwili trochę do bani. Prawdopodobnie muszę spróbować zminimalizować liczbę wykonywanych obliczeń, a zamiast tego przekazać więcej stałych.

Strategia

Zasadniczo każdy biały pionek musi atakować inne białe pionki. Zacznę więc od umieszczenia białego pionka, umieszczenia pionków w każdym zaatakowanym miejscu i zasadniczo wypełnienia planszy wszystkimi miejscami, którymi MUSI iść biały pionek. Przestaję, jeśli dodałem już zbyt wiele białych pionków. Jeśli na końcu mam dokładnie 2n ^ 2 pionki, jest to rozwiązanie. Jeśli mniej, dodaj kolejny biały pionek, wypełnij wszystkie wymagane miejsca i policz ponownie. Rekurencyjnie dzielę się za każdym razem, gdy zostanie znalezione wypełnienie mniejsze niż 2n ^ 2, i obliczam liczbę rozwiązań z dodanym pionkiem i bez niego.

Kod

class main
{
  public  Void main(){

    echo(calculate(1))
    echo(calculate(2))
    echo(calculate(3))
    echo(calculate(4))
    echo(calculate(5))

  }

  public static  Int calculate(Int n){

    n *= 2
    //Initialize the array -  Definitely a weakpoint, but only runs once
    Bool[][] white := [,]
    n.times{ 
      row := [,]
      n.times{ row.add(false) }
      white.add(row)
    }

    return recurse(white, -1, 0, n, n*n/2)
  }

  private static  Int recurse(Bool[][] white, Int lastPlacement, Int numWhites, Int n, Int totalWhite){
    if(totalWhite - numWhites > n*n - 1 - lastPlacement) return 0
    lastPlacement++
    Int row := lastPlacement / n
    Int col := lastPlacement % n
    if(white[row][col]){ return recurse(white, lastPlacement, numWhites, n, totalWhite)}
    Bool[][] whiteCopy := copy(white)
    whiteCopy[row][col] = true
    Int result := fillIn(whiteCopy, numWhites + 1, totalWhite)
    if(result == -1){
      return recurse(white, lastPlacement, numWhites,n, totalWhite);
    }
    else if(result == totalWhite){
      //echo("Found solution")
      //echo("WhiteCopy = $whiteCopy")
      return recurse(white, lastPlacement, numWhites,n, totalWhite) + 1;
    }
    else return recurse(whiteCopy, lastPlacement, result,n, totalWhite) + recurse(white, lastPlacement, numWhites,n, totalWhite)


  }

  //Every white must be attacking other whites, so fill in the grid with all necessary points
  //Stop if number of whites used goes too high
  private static Int fillIn(Bool[][] white, Int count, Int n){
    white[0..-2].eachWhile |Bool[] row, Int rowIndex -> Bool?| {
      return row.eachWhile |Bool isWhite, Int colIndex -> Bool?|{
        if(isWhite){
          //Catching index out of bounds is faster than checking index every time
          try{
            if(colIndex > 0 && !white[rowIndex + 1][colIndex - 1]){
              white[rowIndex + 1][colIndex - 1] = true
              count++
            }
            if(!white[rowIndex + 1][colIndex + 1]){
              white[rowIndex + 1][colIndex + 1] = true
              count++
            }
          } catch {}
        }
        if(count > n){ count = -1; return true}
        return null
      }//End row.each
    }//End white.each
    return count
  }

  private static Bool[][] copy(Bool[][] orig){
    Bool[][] copy := [,]
    orig.each{
      copy.add(it.dup)
    }
    return copy
  }

}

Wynik

W tej chwili jest tylko 5, ale myślę, że większość problemu dotyczy implementacji.

3
30
410
6148
96120

Test