Finden Sie bei einer ganzen Zahl 2n die Anzahl der Möglichkeiten, wie 2n ^ 2 schwarze Bauern und 2n ^ 2 weiße Bauern auf einem 2n x 2n-Schachbrett so angeordnet werden können, dass kein Bauer einen anderen angreift.

• Ein schwarzer Bauer kann nur einen weißen Bauern angreifen und umgekehrt.
• Es folgen die üblichen Schachregeln für Angriffe, dh weiße Bauern greifen Felder unmittelbar diagonal vorne an und die schwarzen Bauern greifen Felder unmittelbar diagonal rückwärts an (vom weißen Beobachter aus gesehen).
• Alle Rotationen und Reflexionen gelten als unterschiedlich.

Das Programm, das alle möglichen Konfigurationen für den höchsten Wert von 2n in 120 Sekunden ausgeben kann, gewinnt. (Alle Programme sind jedoch willkommen)

Zum Beispiel kann Alices Programm innerhalb von 120 Sekunden bis zu n = 16 verarbeiten, während Bobs innerhalb derselben Zeit bis zu n = 20 verarbeiten kann. Bob gewinnt.

Plattform: Linux 2.7GHz @ 4 CPUs

Java, n = 87 auf meinem Computer

Das Ergebnis für n = 87 ist

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

}

Dies verwendet derzeit ein dynamisches Programmierschema, das O (n ^ 4) -Operationen verwendet, um die Möglichkeiten zum Platzieren von pBauern auf den Quadraten einer Farbe für zu berechnen 0 <= p <= n^2. Ich denke, es sollte möglich sein, dies viel effizienter zu tun.

Überprüfen Sie die Ergebnisse hier.

Erläuterung

In einer gültigen Lösung müssen die untersten weißen Bauern in jeder Spalte eine Zick-Zack-Linie wie folgt bilden:

Das heißt, die Höhe der Linie in Spalte c muss +/- 1 von ihrer Position in Spalte c - 1 betragen . Die Linie kann auch auf zwei imaginäre Reihen über der Oberseite der Tafel verlaufen.

Wir können die dynamische Programmierung verwenden, um die Anzahl der Möglichkeiten zum Zeichnen einer Linie in den ersten c- Spalten zu ermitteln, die p Bauern in diesen Spalten enthält. Sie befindet sich in der Höhe h in der c- ten Spalte und verwendet die Ergebnisse für Spalte c - 1 , Höhe h + / - 1 und Anzahl der Bauern p - h .

Java

Derzeit ist mein Code sehr lang und langweilig. Ich arbeite daran, ihn schneller zu machen. Ich benutze eine rekursive Methode, um die Werte zu finden. Es berechnet die ersten 5 innerhalb von 2 oder 3 Sekunden, wird danach aber viel langsamer. Ich bin mir auch noch nicht sicher, ob die Zahlen stimmen, aber die ersten scheinen mit den Kommentaren übereinzustimmen. Anregungen sind willkommen.

Ausgabe

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

Erläuterung

Die Grundidee ist Rekursion. Im Wesentlichen beginnen Sie mit einer leeren Tafel, einer Tafel mit allen Nullen. Die rekursive Methode prüft nur, ob sie einen schwarzen oder weißen Bauern an die nächste Position bringen kann. Wenn sie nur eine Farbe setzen kann, setzt sie sie dort ab und ruft sich selbst auf. Wenn es beide Farben setzen kann, nennt es sich zweimal, eine mit jeder Farbe. Jedes Mal, wenn es sich selbst nennt, werden die verbleibenden Quadrate und die entsprechende verbleibende Farbe verringert. Wenn es das gesamte Brett gefüllt hat, gibt es die aktuelle Anzahl + 1 zurück. Wenn es herausfindet, dass es keine Möglichkeit gibt, einen schwarzen oder weißen Bauern an die nächste Position zu bringen, gibt es 0 zurück, was bedeutet, dass es ein toter Pfad ist.

Code

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

Probieren Sie es hier aus (Läuft für Ideone nicht schnell genug, sodass der letzte Wert nicht gedruckt wird. Meine Lösung scheint nicht sehr gut zu sein!)

C ++ mit pthreads, n = 147 156

Das neueste Ergebnis ist das Ausführen des gleichen Codes wie zuvor auf einem kräftigeren Computer. Dies wurde nun auf einem Desktop mit einem Quad-Core i7 (Core i7-4770) ausgeführt, der in 120 Sekunden auf n = 156 kam. Das Ergebnis ist:

785810368888248234969622509064814231709342669126944160689354425709131590643177370267626619864305814898736515156056592289185248184704932154134758272879317511454384

Dies verwendet einen dynamischen Programmieralgorithmus. Ich dachte anfangs über Ansätze nach, bei denen das Ergebnis Zeile für Zeile erstellt werden würde, aber ich konnte nie einen Weg finden, die Lösung zu erweitern, ohne eine Menge Status zu verfolgen.

Die wichtigsten Erkenntnisse, die eine einigermaßen effiziente Lösung ermöglichten, waren:

• Da Bauern auf schwarzen Feldern nur Bauern auf anderen schwarzen Feldern angreifen können und dies auch für weiße Felder gilt, sind die schwarzen und weißen Felder unabhängig und können separat verarbeitet werden. Und da sie gleichwertig sind, müssen wir nur einen der beiden verarbeiten.
• Das Problem wird viel einfacher, wenn die Platine diagonal für diagonal verarbeitet wird.

Wenn Sie sich eine Diagonale einer gültigen Konfiguration ansehen, besteht diese immer aus einer Folge von schwarzen Bauern, gefolgt von einer Folge von weißen Bauern (wobei jede Folge auch leer sein kann). Mit anderen Worten, jede Diagonale kann vollständig durch ihre Anzahl schwarzer Bauern charakterisiert werden.

Daher ist der für jede Diagonale verfolgte Zustand die Anzahl der gültigen Bauernkonfigurationen für jede Kombination von:

• Anzahl der schwarzen Bauern in der Reihe (oder mit anderen Worten die Position innerhalb der Diagonale, die die schwarzen Bauern von den weißen Bauern trennt).
• Gesamtzahl der verwendeten schwarzen Bauern. Wir müssen das Ganze pro Bauernzahl verfolgen, weil wir nur die gleiche Anzahl schwarzer und weißer Bauern am Ende brauchen. Während der Verarbeitung der Diagonalen können die Zählungen unterschiedlich sein und am Ende immer noch zu gültigen Lösungen führen.

Beim Übergang von einer Diagonale zur nächsten gibt es eine weitere Einschränkung, um gültige Lösungen zu erstellen: Die Position, die schwarze Bauern von weißen Bauern trennt, kann nicht erhöht werden. Die Anzahl der gültigen Konfigurationen wird also als die Summe der gültigen Konfigurationen der vorherigen Diagonale für Positionen berechnet, die gleich oder größer sind.

Der grundlegende DP-Schritt ist dann sehr einfach. Jeder Wert in einer Diagonale ist nur eine Summe von Werten aus der vorherigen Diagonale. Der einzige etwas schmerzhafte Teil ist die korrekte Berechnung der Indizes und Schleifenbereiche. Da wir an Diagonalen arbeiten, nimmt die Länge in der ersten Hälfte der Berechnung zu und in der zweiten Hälfte ab, was die Berechnung der Schleifenbereiche umständlicher macht. Es gibt auch einige Überlegungen zu den Werten an der Grenze der Platine, da sie nur diagonale Nachbarn auf einer Seite haben, wenn sie von diagonal zu diagonal wechseln.

Die verwendete Speichermenge beträgt O (n ^ 3). Ich behalte zwei Kopien der Statusdaten und Ping-Pong zwischen ihnen. Ich glaube, es wäre möglich, mit einer einzigen Instanz der Zustandsdaten zu arbeiten. Sie müssen jedoch sehr vorsichtig sein, dass keine Werte aktualisiert werden, bevor die alten Werte vollständig verbraucht sind. Außerdem würde es für die von mir eingeführte Parallelverarbeitung nicht gut funktionieren.

Die Komplexität der Laufzeit ist ... polynomisch. Der Algorithmus enthält 4 verschachtelte Schleifen, sodass er auf den ersten Blick wie O (n ^ 4) aussehen würde. Aber Sie brauchen offensichtlich Bigint bei diesen Größen, und die Zahlen selbst werden auch bei größeren Größen länger. Die Anzahl der Stellen im Ergebnis scheint ungefähr proportional zu n zuzunehmen, was das Ganze zu O (n ^ 5) machen würde. Auf der anderen Seite habe ich einige Leistungsverbesserungen festgestellt, die es vermeiden, den gesamten Bereich aller Schleifen zu durchlaufen.

Obwohl dies immer noch ein ziemlich teurer Algorithmus ist, geht er viel weiter als die Algorithmen, die Lösungen aufzählen, die alle exponentiell sind.

Einige Hinweise zur Implementierung:

• Während es auf den schwarzen Quadraten bis zu 2 * n ^ 2 schwarze Bauern geben kann, berechne ich nur die Konfigurationsnummern bis zu n ^ 2 schwarzen Bauern. Da es eine Symmetrie zwischen schwarzen und weißen Bauern gibt, sind die Konfigurationszahlen für k und 2 * n ^ 2-k gleich.
• Die Anzahl der Lösungen wird am Ende aus den Konfigurationszählungen auf den schwarzen Quadraten basierend auf einer ähnlichen Symmetrie berechnet. Die Gesamtzahl der Lösungen (die 2 * n ^ 2 Bauern jeder Farbe haben müssen) ist die Anzahl der Konfigurationen für k schwarze Bauern auf einer Farbe von Quadraten multipliziert mit der Anzahl der Konfigurationen für 2 * n ^ 2-k schwarze Bauern auf der anderen Farbe der Quadrate, summiert über alle k.
• Zusätzlich zum Speichern der Konfigurationszählungen pro diagonaler Position und der Bauernanzahl speichere ich auch den Bereich der Bauernzählungen mit gültigen Konfigurationen pro Position. Dies ermöglicht es, den Bereich der inneren Schleife wesentlich zu verringern. Ohne dies stellte ich fest, dass viele Nullen hinzugefügt wurden. Ich habe dadurch eine sehr wesentliche Leistungsverbesserung erzielt.
• Der Algorithmus parallelisiert ziemlich gut, insbesondere bei großen Größen. Die Diagonalen müssen nacheinander verarbeitet werden, sodass am Ende jeder Diagonale eine Barriere vorhanden ist. Die Positionen innerhalb der Diagonale können jedoch parallel verarbeitet werden.
• Die Profilerstellung zeigt, dass der Engpass eindeutig darin besteht, Bigint-Werte hinzuzufügen. Ich habe mit einigen Variationen des Codes herumgespielt, aber er ist nicht stark optimiert. Ich vermute, dass es eine signifikante Verbesserung gegenüber der Inline-Assembly geben könnte, wenn 64-Bit-Ergänzungen mit Übertrag verwendet werden.

Hauptalgorithmuscode. THREADSsteuert die Anzahl der verwendeten Threads, wobei die Anzahl der CPU-Kerne ein vernünftiger Ausgangspunkt sein sollte:

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

Dies erfordert auch eine Bigint-Klasse, die ich zu diesem Zweck geschrieben habe. Beachten Sie, dass dies keine Allzweck-Bigint-Klasse ist. Es reicht gerade aus, um die von diesem speziellen Algorithmus verwendeten Operationen zu unterstützen:

#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

Hier ist ein erster Beitrag, der das Framework einrichtet. Ich denke, das Verfahren ist relativ gut, aber die Implementierung im Moment ist irgendwie beschissen. Ich muss wahrscheinlich versuchen, die Anzahl der Berechnungen, die ich mache, zu minimieren und stattdessen einfach mehr Konstanten zu übergeben.

Strategie

Grundsätzlich muss jeder weiße Bauer andere weiße Bauern angreifen. Also beginne ich damit, einen weißen Bauern zu platzieren, Bauern an jeder Stelle zu platzieren, die er angreift, und im Wesentlichen das Brett mit allen Stellen zu füllen, an denen ein weißer Bauer gehen muss. Ich höre auf, wenn ich schon zu viele weiße Bauern hinzugefügt habe. Wenn ich am Ende genau 2n ^ 2 Bauern habe, ist das eine Lösung. Wenn weniger, füge irgendwo einen weiteren weißen Bauern hinzu, fülle alle erforderlichen Stellen aus und zähle erneut. Ich teile jedes Mal rekursiv auf, wenn eine Füllung mit weniger als 2n ^ 2 gefunden wird, und berechne die Anzahl der Lösungen mit und ohne den letzten Bauern, den ich hinzugefügt habe.

Code

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
  }

}

Ausgabe

Schafft es momentan nur auf 5, aber ich denke, der größte Teil des Problems liegt in der Implementierung.

3
30
410
6148
96120

Prüfung