Слишком много пешек на шахматной доске

10

Учитывая целое число 2n, найдите количество возможных способов, которыми 2n ^ 2 черных пешек и 2n ^ 2 белых пешек могут быть размещены на шахматной доске 2n на 2n таким образом, чтобы никакая пешка не атаковала другую.

  • Черная пешка может атаковать только белую пешку, и наоборот.
  • Следуют обычным шахматным правилам атаки: белые пешки атакуют квадраты сразу по диагонали спереди, а черные пешки атакуют квадраты сразу по диагонали назад (как заметил белый наблюдатель).
  • Все вращения, отражения считаются отличимыми.

Программа, которая может выводить все возможные конфигурации для наибольшего значения 2n за 120 секунд, побеждает. (Все программы приветствуются)

Например, программа Алисы может обрабатывать до n = 16 в течение 120 секунд, в то время как Боб может обрабатывать до n = 20 в течение того же времени. Боб выигрывает.

Платформа: Linux 2,7 ГГц @ 4 процессора

fastest-code combinatorics chess Агнишом Чаттопадхяй
источник
2
Какой выходной формат?
Дверная ручка
2
Для теста: кто-нибудь имеет представление о числах участвующих? Я нашел 3 решения для 2x2 и 28 решений для 4x4
edc65
1
@ edc65, я делаю 3, 30, 410. Я проверил 3 и 30 альтернативным методом.
Питер Тейлор
1
Мой код генерировал первые несколько: 3, 30, 410, 6148, 96120, 1526700. Хотя я не могу проверить. Кто-нибудь получит то же самое?
CMXU
1
Чтобы уточнить приоритет оператора, когда вы говорите 2n^2пешки, это (2n)^2или 2(n^2)?
Рето Коради

Ответы:

9

Java, n = 87 на моей машине

Результат для n = 87

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

}

В настоящее время используется схема динамического программирования, в которой для вычисления способов размещения pпешек на квадратах одного цвета используются O (n ^ 4) операций 0 <= p <= n^2. Я думаю, что должно быть возможно сделать это намного более эффективно.

Проверьте результаты здесь.

объяснение

В правильном решении самые нижние белые пешки в каждом столбце должны образовывать зигзагообразную линию, например:

пешка

То есть высота строки в столбце c должна быть +/- 1 от ее положения в столбце c - 1 . Линия также может идти на два воображаемых ряда над верхней частью доски.

Мы можем использовать динамическое программирование , чтобы найти число способов , чтобы нарисовать линию на первых гр столбцах , которые включают р пешку на этих колоннах, находится на высоту ч на с - м столбца, используя результаты для столбца с - 1 , высотой Н + / - 1 , а количество пешек p - h .

feersum
источник
Можете ли вы поделиться число для n = 87? Или хотя бы на порядок? Это должно быть очень большое число ...
Рето Коради
Я немного запутался в том, что ты здесь делаешь, но это очень впечатляет!
СМХУ
Я думаю, что получаю большую часть вашего объяснения, за исключением случаев, когда вы говорите: «Линия также может идти на два воображаемых ряда над верхней частью доски»
cmxu
@Changming, это только означает, что в этом столбце нет пешек.
feersum
@feersum Я вижу, что это имеет больше смысла, я посмотрю, смогу ли я работать с логикой, и посмотрим, смогу ли я найти способ реализовать ее еще быстрее.
CMXU
5

Ява

В настоящее время мой код очень длинный и утомительный, я работаю над тем, чтобы сделать его быстрее. Я использую рекурсивный метод, чтобы найти значения. Он вычисляет первые 5 в течение 2 или 3 секунд, но потом становится намного медленнее. Кроме того, я еще не уверен, верны ли цифры, но первые несколько, похоже, совпадают с комментариями. Любые предложения приветствуются.

Вывод

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

объяснение

Основная идея - рекурсия. По сути, вы начинаете с пустой доски, доски со всеми нулями. Рекурсивный метод просто проверяет, может ли он положить черную или белую пешку в следующую позицию, если он может поместить только один цвет, он помещает его туда и вызывает сам. Если он может поместить оба цвета, он вызывает себя дважды, по одному с каждым цветом. Каждый раз, когда он вызывает себя, он уменьшает количество оставленных квадратов и соответствующий цвет. Когда он заполнил всю доску, он возвращает текущий счет + 1. Если он обнаруживает, что невозможно поставить черную или белую пешку в следующую позицию, он возвращает 0, что означает, что это мертвый путь.

Код

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

Попробуйте это здесь (не работает достаточно быстро для Ideone, поэтому последнее значение не печатается, похоже, мое решение не очень хорошее!)

cmxu
источник
Я согласен до 6148, и я еще не произвел никаких ценностей кроме этого.
Питер Тейлор
@PeterTaylor Ну, Агнишом говорит, что это должно быть 3, 28, 408, поэтому я сомневаюсь, что 6148 прав. Интересно, что мы оба делаем не так?
CMXU
Довольно быстрее, чем мой. +1, даже если я не согласен с результатами
edc65
Здравствуйте! Я никогда не говорил, что это 28, 408. Правильная последовательность - 3,30,410, ...
Агнишом Чаттопадхьяй
Вы сказали, что @ edc65 имел правильные значения, а его значения 28, 408?
CMXU
4

C ++ с потоками, n = 147 156

Последний результат - запуск того же кода, что и раньше, на более мощной машине. Теперь он запускался на настольном компьютере с четырехъядерным процессором i7 (Core i7-4770), который достиг 120 = n за 120 секунд. Результат:

7858103688882482349696225090648142317093426691269441606893544257091315906431773702676266198643058148987365151560565922891852481847049321541347582728793175114543840164406674137410614843200

Это использует алгоритм динамического программирования. Сначала я размышлял о подходах, где результат будет строиться строка за строкой, но я никогда не мог придумать способ расширить решение, не отслеживая тонну состояний.

Ключевые идеи, которые позволили получить достаточно эффективное решение, были следующими:

  • Поскольку пешки на черных квадратах могут атаковать пешки только на других черных квадратах, и то же самое верно для белых квадратов, черные и белые квадраты независимы и могут обрабатываться отдельно. И поскольку они эквивалентны, нам нужно обработать только один из двух.
  • Проблема становится намного проще при обработке доски по диагонали.

Если вы посмотрите на одну диагональ действительной конфигурации, она всегда состоит из последовательности черных пешек, за которой следует последовательность белых пешек (где любая последовательность также может быть пустой). Другими словами, каждая диагональ может быть полностью охарактеризована количеством черных пешек.

Следовательно, состояние, отслеживаемое для каждой диагонали, представляет собой количество допустимых конфигураций пешек для каждой комбинации:

  • Количество черных пешек в ряду (или, другими словами, позиция внутри диагонали, отделяющая черных пешек от белых пешек).
  • Общее количество использованных черных пешек. Нам нужно отследить все на счет пешки, потому что нам нужно одинаковое количество черных и белых пешек в самом конце. При обработке диагоналей счет может быть разным, и в итоге все равно получится правильное решение.

При переходе от одной диагонали к следующей возникает другое ограничение для построения правильных решений: позиция, которая отделяет черных пешек от белых пешек, не может увеличиваться. Таким образом, число допустимых конфигураций рассчитывается как сумма действительных конфигураций предыдущей диагонали для позиций, которые равны или больше.

Основной шаг DP тогда очень прост. Каждое значение в диагонали - это просто сумма значений из предыдущей диагонали. Единственной болезненной частью является правильное вычисление индексов и циклов. Поскольку мы работаем с диагоналями, длина увеличивается во время первой половины вычисления и уменьшается во второй половине, что делает вычисление диапазонов цикла более громоздким. Есть также некоторые соображения относительно значений на границе платы, так как они имеют только диагональных соседей с одной стороны при переходе от диагонали к диагонали.

Количество используемой памяти O (n ^ 3). Я храню две копии данных о состоянии и пинг-понг между ними. Я полагаю, что можно было бы оперировать одним экземпляром данных о состоянии. Но вы должны быть очень осторожны, чтобы никакие значения не обновлялись до полного использования старых значений. Кроме того, это не будет работать хорошо для параллельной обработки, которую я представил.

Сложность во время выполнения ... полиномиальная. В алгоритме есть 4 вложенных цикла, поэтому на первый взгляд это будет выглядеть как O (n ^ 4). Но вам, очевидно, нужны bigints при этих размерах, а сами числа также увеличиваются при больших размерах. Число цифр в результате, кажется, увеличивается примерно пропорционально n, что составляет целое число O (n ^ 5). С другой стороны, я обнаружил некоторые улучшения производительности, которые позволяют избежать прохождения всего диапазона всех циклов.

Таким образом, хотя это все еще довольно дорогой алгоритм, он идет намного дальше, чем алгоритмы, перечисляющие решения, которые все являются экспоненциальными.

Некоторые замечания по реализации:

  • В то время как на черных квадратах может быть до 2 * n ^ 2 черных пешек, я вычисляю только номера конфигурации до n ^ 2 черных пешек. Поскольку между черными и белыми пешками существует симметрия, количество конфигураций для k и 2 * n ^ 2-k одинаково.
  • Количество решений рассчитывается в конце из подсчетов конфигурации на черных квадратах на основе аналогичной симметрии. Общее количество решений (которые должны иметь 2 * n ^ 2 пешек каждого цвета) - это число конфигураций для k черных пешек на одном цвете квадратов, умноженное на количество конфигураций для 2 * n ^ 2-k черных пешек на другом цвете квадратов суммируется по всем k.
  • В дополнение к простому сохранению количества конфигураций для каждой диагональной позиции и количества пешек, я также храню диапазон количества пешек, которые имеют допустимые конфигурации для каждой позиции. Это позволяет существенно сократить диапазон внутренней петли. Без этого я обнаружил, что было добавлено много нулей. Я получил очень существенное улучшение производительности от этого.
  • Алгоритм распараллеливает довольно хорошо, особенно при больших размерах. Диагонали должны обрабатываться последовательно, поэтому в конце каждой диагонали имеется барьер. Но позиции внутри диагонали могут обрабатываться параллельно.
  • Профилирование показывает, что узкое место заключается в добавлении значений bigint. Я играл с некоторыми вариантами кода, но он не сильно оптимизирован. Я подозреваю, что может быть значительное улучшение от встроенной сборки для использования 64-битных дополнений с переносом.

Основной алгоритм кода. THREADSуправляет количеством используемых потоков, где разумным началом является количество ядер ЦП:

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

Для этого также нужен класс bigint, который я написал для этой цели. Обратите внимание, что это не класс bigint общего назначения. Этого достаточно для поддержки операций, используемых этим конкретным алгоритмом:

#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
Рето Коради
источник
0

фантом

Вот начальный пост, который устанавливает рамки. Я думаю, что процедура является относительно хорошей, но реализация прямо сейчас отстой. Мне нужно, вероятно, попытаться минимизировать количество вычислений, которые я делаю, и вместо этого просто передать больше констант.

стратегия

По сути, каждая белая пешка должна атаковать других белых пешек. Поэтому я начинаю с размещения белой пешки, размещения пешек в каждом месте, где она атакует, и, по существу, заполнения доски всеми местами, которые должна пройти белая пешка. Я останавливаюсь, если уже добавил слишком много белых пешек. Если в конце этого у меня ровно 2n ^ 2 пешек, это решение. Если меньше, добавьте еще одну белую пешку куда-нибудь, заполните все необходимые места и посчитайте снова. Я рекурсивно делю каждый раз, когда обнаруживается заполнение с менее чем 2n ^ 2, и вычисляю количество решений с последней добавленной пешкой и без нее.

Код

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
  }

}

Вывод

Только делает это до 5 прямо сейчас, но я думаю, что большая часть проблемы находится в реализации.

3
30
410
6148
96120

Тестовое задание

Каин
источник
Это тоже моя стратегия, но она кажется слишком медленной по сравнению с другими решениями, опубликованными здесь.
edc65
@ edc65 Подходы, перечисляющие решения, не будут иметь шансов. Если были какие-либо сомнения, доказательство тому - явное число, полученное алгоритмом feersum. Некоторый вид алгоритма динамического программирования, который вычисляет количество решений, не перечисляя их, является способом пойти сюда.
Рето KORADI