_{To wyzwanie jest inspirowane tą aplikacją . Przypadki testowe są zapożyczone z tej aplikacji.}

Jest to wyzwanie z najszybszym kodem , którego celem jest rozwiązanie największych przypadków testowych w jak najkrótszym czasie. Udostępniono kilka mniejszych przypadków testowych, aby ludzie mogli szybciej testować swoje algorytmy.

Otrzymasz kwadratową siatkę wejściową o wymiarach n-po-n, gdzie 9 <= n <= 12 . Ta siatka zostanie podzielona na n obszarów, w których komórki każdego obszaru mają unikalne identyfikatory (użyję małych liter z al w tekście tutaj, ale możesz wybrać, co chcesz, na przykład liczby całkowite 1-12 ) .

Dane wejściowe mogą wyglądać następująco (opcjonalny format wejściowy):

aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg

Lub łatwiejsze do wizualizacji:

Wyzwanie:

Musisz umieścić 2 * n drzew w tym parku, zgodnie z następującymi zasadami:

• Powinny być dokładnie 2 drzewa na kolumnę i 2 drzewa na rząd
• Wszystkie obszary powinny mieć dokładnie 2 drzewa.
• Żadne drzewa nie mogą przylegać do innego drzewa, pionowo, poziomo lub po przekątnej

Rozwiązaniem powyższego układu jest:

Uwaga: dla każdej układanki jest tylko jedno rozwiązanie

Dodatkowe zasady:

• Formaty wejściowe i wyjściowe są opcjonalne
  • Wyjściem może być na przykład lista indeksów, siatka z 1/0 wskazującą, czy w tej pozycji znajduje się drzewo, lub zmodyfikowana wersja danych wejściowych, w których drzewa są wskazane
• Czas wykonania musi być deterministyczny
• Program musi zakończyć się w ciągu 1 minuty na komputerze @ isaacg
  • Specyfikacja: 4 procesory, procesor i5-4300U przy 1,9 GHz, 7,5G pamięci RAM.
• W przypadku, gdy Twój program nie może rozwiązać dwóch największych przypadków testowych w ciągu jednej minuty, czas na drugą co do wielkości ( n = 11 ) będzie twój wynik. Przegrasz z rozwiązaniem, które rozwiązuje największy przypadek.

Przypadki testowe:

Mógłbym edytować tę listę, jeśli wydaje się, że przesłania są dostosowane do tych przypadków testowych.

12 na 12 :

--- Input ---
aaaaabccccdd
aaaaabccccdd
aaaaabbbbddd
eeeafffgbghh
eeaafffgbghh
eefffffggghh
eeefijffghhh
iieiijjjjkhh
iiiiijjjjkhk
lljjjjjjjkkk
llllllkkkkkk
llllllkkkkkk
--- Solution ---
aaaaabcccCdD
aaaaaBcCccdd
aAaaabbbbdDd
eeeaffFgBghh
eeAaFffgbghh
eefffffGgGhh
EeefijffghhH
iiEiIjjjjkhh
IiiiijjjjkHk
lljJjJjjjkkk
lLllllkkKkkk
lllLllKkkkkk

11 na 11 :

--- Input ---
aaaaaaabbcc
adddabbbbcc
edddbbbbbbc
eddddbbbbbb
effffggghhh
effffgghhii
eefffjjhhii
eeeejjjhhii
eeejjjjkiii
jjjjjjkkiii
jjjjjkkkiii
--- Solution ---
aaAaaaabbCc
adddAbBbbcc
eDddbbbbbbC
eddDdBbbbbb
effffggGhHh
eFfffGghhii
eefFfjjhHii
EeeejjjhhiI
eeEjjjjKiii
JjjjJjkkiii
jjjjjkKkIii

10 na 10

--- Input ---
aaaaabccdd
aeaabbbccd
aeaabfbgcd
eeeaafggcd
eeeaafghcd
eeeiifghcd
ieiiigghcd
iiijighhcd
jjjjighhcd
jjjggghhdd
--- Solution ---
aaAaabccdD
aeaaBbBccd
aEaabfbgcD
eeeaaFgGcd
eEeAafghcd
eeeiiFghCd
IeiIigghcd
iiijigHhCd
JjJjighhcd
jjjgGghHdd

9 na 9

--- Input ---
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
--- Solution ---
aAbBbbbcc
adddbbBcC
adEeEcccc
AdddefgCc
hhhDiFggg
hDddifffG
hhhiIfFfg
HiHiifffg
iiiiiIgGg
--- Input ---
aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg
--- Solution ---
aaAbBbccc
AaaabbcCc
aaaDdBcce
fFddddcCe
fffFdDeee
fGffdheeE
fggfHhHee
IggggheeE
iiIgggGgg

JavaScript (ES6), 271 bajtów

Pobiera dane wejściowe jako tablicę tablic znaków. Zwraca tablicę masek bitowych (liczb całkowitych) opisujących pozycję drzew w każdym rzędzie, gdzie najmniej znaczący bit jest pozycją najbardziej na lewo.

f=(a,p=0,r=[S=y=0],w=a.length)=>a.some((R,y)=>a.some((_,x)=>r[y]>>x&1&&(o[k=R[x]]=-~o[k])>2),o=[])?0:y<w?[...Array(1<<w)].some((_,n)=>(k=n^(x=n&-n))<=x*2|k&-k^k|n&(p|p/2|p*2)||r.some((A,i)=>r.some((B,j)=>A&B&n&&i<y&j<i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&&S:S=[...r]

Sformatowane i skomentowane

f = (                                           // given:
  a,                                            //   - a = input matrix
  p = 0,                                        //   - p = previous bitmask
  r = [                                         //   - r = array of tree bitmasks
        S = y = 0 ],                            //   - S = solution / y = current row
  w = a.length                                  //   - w = width of matrix
) =>                                            //
  a.some((R, y) => a.some((_, x) =>             // if there's at least one area with more
    r[y] >> x & 1 && (o[k = R[x]] = -~o[k]) > 2 // than two trees:
  ), o = []) ?                                  //
    0                                           //   abort right away
  :                                             // else:
    y < w ?                                     //   if we haven't reached the last row:
      [...Array(1 << w)].some((_, n) =>         //     for each possible bitmask n:
        (k = n ^ (x = n & -n)) <= x * 2 |       //       if the bitmask does not consist of
        k & - k ^ k |                           //       exactly two non-consecutive bits,
        n & (p | p / 2 | p * 2) ||              //       or is colliding with the previous
        r.some((A, i) => r.some((B, j) =>       //       bitmask, or generates more than two
          A & B & n && i < y & j < i            //       trees per column:
        )) ?                                    //
          0                                     //         yield 0
        :                                       //       else:
          (                                     //
            w = r[y],                           //         save the previous bitmask
            f(a, r[y++] = n, r),                //         recursive call with the new one
            r[--y] = w,                         //         restore the previous bitmask
            S                                   //         yield S
          )                                     //
      ) && S                                    //     end of some(): return false or S
    :                                           //   else:
      S = [...r]                                //     this is a solution: save a copy in S

Przypadki testowe

Ten fragment kodu zawiera dodatkową funkcję wyświetlania wyników w bardziej czytelnym formacie. Zbyt wolne jest rozwiązywanie ostatniego przypadku testowego.

Oczekiwany czas działania: ~ 5 sekund.

f=(a,p=0,r=[S=y=0],w=a.length)=>a.some((R,y)=>a.some((_,x)=>r[y]>>x&1&&(o[k=R[x]]=-~o[k])>2),o=[])?0:y<w?[...Array(1<<w)].some((_,n)=>(k=n^(x=n&-n))<=x*2|k&-k^k|n&(p|p/2|p*2)||r.some((A,i)=>r.some((B,j)=>A&B&n&&i<y&j<i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&&S:S=[...r]

format = (a, w) => a.map(n => [...('0'.repeat(w) + n.toString(2)).slice(-w)].reverse().join('')).join('\n')

console.log(format(f([
  [..."aabbbbbcc"],
  [..."adddbbbcc"],
  [..."adeeecccc"],
  [..."adddefgcc"],
  [..."hhhdifggg"],
  [..."hdddifffg"],
  [..."hhhiifffg"],
  [..."hihiifffg"],
  [..."iiiiiiggg"]
]), 9));

console.log(format(f([
  [..."aaabbbccc"],
  [..."aaaabbccc"],
  [..."aaaddbcce"],
  [..."ffddddcce"],
  [..."ffffddeee"],
  [..."fgffdheee"],
  [..."fggfhhhee"],
  [..."iggggheee"],
  [..."iiigggggg"]
]), 9));

console.log(format(f([
  [..."aaaaabccdd"],
  [..."aeaabbbccd"],
  [..."aeaabfbgcd"],
  [..."eeeaafggcd"],
  [..."eeeaafghcd"],
  [..."eeeiifghcd"],
  [..."ieiiigghcd"],
  [..."iiijighhcd"],
  [..."jjjjighhcd"],
  [..."jjjggghhdd"]
]), 10));

C, oficjalny czas: 5 ms dla 12 x 12

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>

#define valT char
#define posT int

#ifndef _OPENMP
#  warning Building without OpenMP support
#  define omp_get_max_threads() 1
#  define omp_get_num_threads() 1
#  define omp_get_thread_num() 0
#endif

#define MIN_THREADED_SIZE 11

static void complete(posT n, valT *workspace) {
    const posT s = n * 3 + 2;

    const valT *regions = workspace;
    valT *output = &workspace[n*2+1];

    for(posT y = 0; y < n; ++ y) {
        for(posT x = 0; x < n; ++ x) {
//          putchar(output[y*s+x] ? '*' : '-');
            putchar(regions[y*s+x] + (output[y*s+x] ? 'A' : 'a'));
        }
        putchar('\n');
    }

    _Exit(0);
}

static void solveB(const posT n, valT *workspace, valT *pops, const posT y) {
    const posT s = n * 3 + 2;

    const valT *regions = workspace;
    const valT *remaining = &workspace[n];
    valT *output = &workspace[n*2+1];

    for(posT r = 0; r < n; ++ r) {
        if(pops[r] + remaining[r] < 2) {
            return;
        }
    }

    for(posT t1 = 0; t1 < n - 2; ++ t1) {
        posT r1 = regions[t1];
        if(output[t1+1-s]) {
            t1 += 2;
            continue;
        }
        if(output[t1-s]) {
            ++ t1;
            continue;
        }
        if((pops[t1+n] | pops[r1]) & 2 || output[t1-1-s]) {
            continue;
        }
        output[t1] = 1;
        ++ pops[t1+n];
        ++ pops[r1];
        for(posT t2 = t1 + 2; t2 < n; ++ t2) {
            posT r2 = regions[t2];
            if(output[t2+1-s]) {
                t2 += 2;
                continue;
            }
            if(output[t2-s]) {
                ++ t2;
                continue;
            }
            if((pops[t2+n] | pops[r2]) & 2 || output[t2-1-s]) {
                continue;
            }
            output[t2] = 1;
            ++ pops[t2+n];
            ++ pops[r2];
            if(y == 0) {
                complete(n, &workspace[-s*(n-1)]);
            }
            solveB(n, &workspace[s], pops, y - 1);
            output[t2] = 0;
            -- pops[t2+n];
            -- pops[r2];
        }
        output[t1] = 0;
        -- pops[t1+n];
        -- pops[r1];
    }
}

static void solve(const posT n, valT *workspace) {
    const posT s = n * 3 + 2;

    valT *regions = workspace;
    valT *remaining = &workspace[n];
    valT *pops = &workspace[n*s];
//  memset(&remaining[n*s], 0, n * sizeof(valT));

    for(posT y = n; (y --) > 0;) {
        memcpy(&remaining[y*s], &remaining[(y+1)*s], n * sizeof(valT));
        for(posT x = 0; x < n; ++ x) {
            valT r = regions[y*s+x];
            valT *c = &remaining[y*s+r];
            valT *b = &pops[r*3];
            if(*c == 0) {
                *c = 1;
                b[0] = y - 1;
                b[1] = x - 1;
                b[2] = x + 1;
            } else if(x < b[1] || x > b[2] || y < b[0]) {
                *c = 2;
            } else {
                b[1] = b[1] > (x - 1) ? b[1] : (x - 1);
                b[2] = b[2] < (x + 1) ? b[2] : (x + 1);
            }
        }
//      memset(&output[y*s], 0, (n+1) * sizeof(valT));
    }
    memset(pops, 0, n * 2 * sizeof(valT));

    posT sz = (n + 1) * s + n * 3;
    if(n >= MIN_THREADED_SIZE) {
        for(posT i = 1; i < omp_get_max_threads(); ++ i) {
            memcpy(&workspace[i*sz], workspace, sz * sizeof(valT));
        }
    }

#pragma omp parallel for if (n >= MIN_THREADED_SIZE)
    for(posT t1 = 0; t1 < n - 2; ++ t1) {
        valT *workspace2 = &workspace[omp_get_thread_num()*sz];
        valT *regions = workspace2;
        valT *output = &workspace2[n*2+1];
        valT *pops = &workspace2[n*s];

        posT r1 = regions[t1];
        output[t1] = pops[t1+n] = pops[r1] = 1;
        for(posT t2 = t1 + 2; t2 < n; ++ t2) {
            posT r2 = regions[t2];
            output[t2] = pops[t2+n] = 1;
            ++ pops[r2];
            solveB(n, &regions[s], pops, n - 2);
            output[t2] = pops[t2+n] = 0;
            -- pops[r2];
        }
        output[t1] = pops[t1+n] = pops[r1] = 0;
    }
}

int main(int argc, const char *const *argv) {
    if(argc < 2) {
        fprintf(stderr, "Usage: %s 'grid-here'\n", argv[0]);
        return 1;
    }

    const char *input = argv[1];
    const posT n = strchr(input, '\n') - input;
    const posT s = n * 3 + 2;

    posT sz = (n + 1) * s + n * 3;
    posT threads = (n >= MIN_THREADED_SIZE) ? omp_get_max_threads() : 1;
    valT *workspace = (valT*) calloc(sz * threads, sizeof(valT));
    valT *regions = workspace;

    for(posT y = 0; y < n; ++ y) {
        for(posT x = 0; x < n; ++ x) {
            regions[y*s+x] = input[y*(n+1)+x] - 'a';
        }
    }

    solve(n, workspace);

    fprintf(stderr, "Failed to solve grid\n");
    return 1;
}

Kompilowany z GCC 7 przy użyciu flag -O3i -fopenmp. Powinny mieć podobne wyniki w dowolnej wersji GCC z zainstalowanym OpenMP.

gcc-7 Trees.c -O3 -fopenmp -o Trees

Format wejściowy i wyjściowy są podane w pytaniu.

Na mojej maszynie potrzeba 0,009s 0,008s 0,005s dla przykładu 12x12 i 0,022s 0,020s 0,019s, aby uruchomić wszystkie przykłady. Na komputerze testowym isaacg zgłasza 5ms dla przykładu 12x12 przy użyciu oryginalnej (nie-wątkowej) wersji kodu.

Stosowanie:

./Trees 'aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg'

Po prostu prosty solver z brutalną siłą, działający na jednym rzędzie na raz. Działa z dobrą prędkością, wcześnie rozpoznając niemożliwe sytuacje (np. Nie pozostały komórki regionu, ale mniej niż 2 drzewa w regionie).

Pierwsza aktualizacja poprawia trafienia do pamięci podręcznej poprzez umieszczenie powiązanych danych blisko siebie w pamięci i sprawia, że ​​obliczenia możliwych drzew pozostających w segmencie są nieco bardziej inteligentne (teraz uwzględnia to, że drzewa nie mogą sąsiadować). Wyodrębnia również najbardziej zewnętrzną pętlę, tak że w najgorętszej części algorytmu potrzeba mniej specjalnych przypadków.

Druga aktualizacja sprawia, że ​​najbardziej zewnętrzna pętla działa równolegle na dostępnych procesorach (przy użyciu OpenMP), zapewniając liniowe zwiększenie prędkości. Jest to włączone tylko dla n> = 11, ponieważ narzut odradzających się wątków przewyższa zalety mniejszych sieci.

Java (OpenJDK 8) , oficjalny czas: 1,2 s na 12 x 12

edycja: już nie koduj golfa

import java.util.*;

// Callable method, takes an int[][] and modifies it
static void f(int[][] areas){
    List<List<BitSet>> areaBitSets = new ArrayList<>();
    List<List<BitSet>> areaTreeBitSets = new ArrayList<>();
    for(int i = 0; i < areas.length; i++){
        areaBitSets.add(new ArrayList<BitSet>());
        areaTreeBitSets.add(new ArrayList<BitSet>());
    }

    // Add a bitset to our list representing each possible square, grouped by area
    for(int i=0; i < areas.length; i++){
        for(int j=0; j < areas.length; j++){
            BitSet b = new BitSet();
            b.set(i*areas.length + j);
            areaBitSets.get(areas[i][j]).add(b);
        }
    }

    // Fold each set onto itself so each area bitset has two trees
    for(int i=0; i < areas.length; i++){
        for(int j=0; j<areaBitSets.get(i).size()-1; j++){
            for(int k=j+1; k <areaBitSets.get(i).size(); k++){
                if(canFoldTogether(areaBitSets.get(i).get(j),areaBitSets.get(i).get(k), areas.length)){
                    BitSet b = (BitSet)areaBitSets.get(i).get(j).clone();
                    b.or(areaBitSets.get(i).get(k));
                    areaTreeBitSets.get(i).add(b);
                }
            }
        }
    }

    // Starting with area 0 add each area one at a time doing Cartesian products
    Queue<BitSet> currentPossibilities = new LinkedList<>();
    Queue<BitSet> futurePossibilities = new LinkedList<>();
    currentPossibilities.addAll(areaTreeBitSets.get(0));

    for(int i=1; i < areaTreeBitSets.size(); i++){
        while(!currentPossibilities.isEmpty()){
            BitSet b= (BitSet)currentPossibilities.poll().clone();

            for(BitSet c: areaTreeBitSets.get(i)){
                if(canFoldTogether(b,c,areas.length)){
                    BitSet d=(BitSet)b.clone();
                    d.or(c);
                    futurePossibilities.add(d);
                }
            }
        }
        currentPossibilities.addAll(futurePossibilities);
        futurePossibilities.clear();
    }

    // Get final output and modify the array
    BitSet b = currentPossibilities.poll();
    for(int i=0; i<areas.length*areas.length; i++){
        areas[i/areas.length][i%areas.length] = b.get(i)?1:0;
    }
}

// Helper method which determines whether combining two bitsets
// will still produce a valid output
static boolean canFoldTogether(BitSet a, BitSet b, int size){

    // See if there are trees too close to each other
    int c=-1;
    while((c=a.nextSetBit(c+1))>=0){
        int d=-1;
        while((d=b.nextSetBit(d+1))>=0){
            int r1=c/size;
            int r2=d/size;
            int c1=c%size;
            int c2=d%size;

            int rDifference = r1>r2 ? r1-r2 : r2-r1;
            int cDifference = c1>c2 ? c1-c2 : c2-c1;
            if(rDifference<2 && cDifference<2)
                return false;
        }
    }

    // Check for row and column cardinality
    BitSet f,g;
    for(int i=0; i<size; i++){
        f = new BitSet();
        f.set(i*size,(i+1)*size);
        g=(BitSet)f.clone();
        f.and(a);
        g.and(b);
        f.or(g);
        if(f.cardinality()>2){
            return false;
        }


        f=new BitSet();
        for(int j = 0; j<size; j++){
            f.set(j*size+i);
        }
        g=(BitSet)f.clone();
        f.and(a);
        g.and(b);
        f.or(g);
        if(f.cardinality()>2){
            return false;
        }
    }

    return true;
}

Wypróbuj online!

Łącze TIO jest przeznaczone do skrzynki testowej 12x12. TIO zgłasza 2,429 dla czasu działania.

Pobiera na wejściu tablicę liczb całkowitych i modyfikuje tablicę, aby zawierała 1 dla drzew i 0 dla drzew innych niż drzewa.

Działa to dla wszystkich przypadków testowych. Największa walizka testowa działa na moim komputerze w niecałą sekundę, chociaż mam dość mocną maszynę

Kod testowy dla 12x12, można modyfikować dla innych

public static void main(String[] args){
    int[][] test = {{0,  0,  0,  0,  0,  1,  2,  2,  2,  2,  3,  3}, 
            {0,  0,  0,  0,  0,  1,  2,  2,  2,  2,  3,  3}, 
            {0,  0,  0,  0,  0,  1,  1,  1,  1,  3,  3,  3}, 
            {4,  4,  4,  0,  5,  5,  5,  6,  1,  6,  7,  7}, 
            {4,  4,  0,  0,  5,  5,  5,  6,  1,  6,  7,  7}, 
            {4,  4,  5,  5,  5,  5,  5,  6,  6,  6,  7,  7}, 
            {4,  4,  4,  5,  8,  9,  5,  5,  6,  7,  7,  7}, 
            {8,  8,  4,  8,  8,  9,  9,  9,  9,  10,  7,  7}, 
            {8,  8,  8,  8,  8,  9,  9,  9,  9,  10,  7,  10}, 
            {11,  11,  9,  9,  9,  9,  9,  9,  9,  10,  10,  10}, 
            {11,  11,  11,  11,  11,  11,  10,  10,  10,  10,  10,  10}, 
            {11,  11,  11,  11,  11,  11,  10,  10,  10,  10,  10,  10}};

    long l = System.currentTimeMillis();
    f(test);
    System.out.println("12x12: " + (System.currentTimeMillis() - l) + "ms");

    for(int[] t : test){
        System.out.println(Arrays.toString(t));
    }

}

Produkuje to na moim komputerze:

12x12: 822ms
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]

Clingo , ≈ 7 ms dla 12 × 12, 116 bajtów

{t(X,Y):c(X,Y,Z)}=2:-Z=1..n.
:-X=1..n,{t(X,1..n)}!=2.
:-Y=1..n,{t(1..n,Y)}!=2.
:-t(X,Y),t(X+1,Y;X+1,Y+1;X,Y+1;X-1,Y+1).

(Nowe linie są opcjonalne i nie są liczone).

Uruchom z clingo plant.lp - -c n=<n>gdzie <n>jest rozmiar siatki. Format wejściowy jest lista c(X,Y,Z).instrukcji dla każdej komórki ( X, Y) kolorowe Z, z ≤ 1 X, Y, Z≤ n, oddzielone spacją opcjonalnym. Dane wyjściowe obejmują t(X,Y)dla każdego drzewa w ( X,Y ).

Czas nie ma większego znaczenia, ponieważ jest to po prostu czas uruchamiania, więc rozważ to jako głos na większe przypadki testowe.

Próbny

$ clingo plant.lp -c n=12 - <<EOF
> c(1,1,1). c(2,1,1). c(3,1,1). c(4,1,1). c(5,1,1). c(6,1,2). c(7,1,3). c(8,1,3). c(9,1,3). c(10,1,3). c(11,1,4). c(12,1,4).
> c(1,2,1). c(2,2,1). c(3,2,1). c(4,2,1). c(5,2,1). c(6,2,2). c(7,2,3). c(8,2,3). c(9,2,3). c(10,2,3). c(11,2,4). c(12,2,4).
> c(1,3,1). c(2,3,1). c(3,3,1). c(4,3,1). c(5,3,1). c(6,3,2). c(7,3,2). c(8,3,2). c(9,3,2). c(10,3,4). c(11,3,4). c(12,3,4).
> c(1,4,5). c(2,4,5). c(3,4,5). c(4,4,1). c(5,4,6). c(6,4,6). c(7,4,6). c(8,4,7). c(9,4,2). c(10,4,7). c(11,4,8). c(12,4,8).
> c(1,5,5). c(2,5,5). c(3,5,1). c(4,5,1). c(5,5,6). c(6,5,6). c(7,5,6). c(8,5,7). c(9,5,2). c(10,5,7). c(11,5,8). c(12,5,8).
> c(1,6,5). c(2,6,5). c(3,6,6). c(4,6,6). c(5,6,6). c(6,6,6). c(7,6,6). c(8,6,7). c(9,6,7). c(10,6,7). c(11,6,8). c(12,6,8).
> c(1,7,5). c(2,7,5). c(3,7,5). c(4,7,6). c(5,7,9). c(6,7,10). c(7,7,6). c(8,7,6). c(9,7,7). c(10,7,8). c(11,7,8). c(12,7,8).
> c(1,8,9). c(2,8,9). c(3,8,5). c(4,8,9). c(5,8,9). c(6,8,10). c(7,8,10). c(8,8,10). c(9,8,10). c(10,8,11). c(11,8,8). c(12,8,8).
> c(1,9,9). c(2,9,9). c(3,9,9). c(4,9,9). c(5,9,9). c(6,9,10). c(7,9,10). c(8,9,10). c(9,9,10). c(10,9,11). c(11,9,8). c(12,9,11).
> c(1,10,12). c(2,10,12). c(3,10,10). c(4,10,10). c(5,10,10). c(6,10,10). c(7,10,10). c(8,10,10). c(9,10,10). c(10,10,11). c(11,10,11). c(12,10,11).
> c(1,11,12). c(2,11,12). c(3,11,12). c(4,11,12). c(5,11,12). c(6,11,12). c(7,11,11). c(8,11,11). c(9,11,11). c(10,11,11). c(11,11,11). c(12,11,11).
> c(1,12,12). c(2,12,12). c(3,12,12). c(4,12,12). c(5,12,12). c(6,12,12). c(7,12,11). c(8,12,11). c(9,12,11). c(10,12,11). c(11,12,11). c(12,12,11).
> EOF
clingo version 5.1.0
Reading from plant.lp ...
Solving...
Answer: 1
c(1,1,1) c(2,1,1) c(3,1,1) c(4,1,1) c(5,1,1) c(6,1,2) c(7,1,3) c(8,1,3) c(9,1,3) c(10,1,3) c(11,1,4) c(12,1,4) c(1,2,1) c(2,2,1) c(3,2,1) c(4,2,1) c(5,2,1) c(6,2,2) c(7,2,3) c(8,2,3) c(9,2,3) c(10,2,3) c(11,2,4) c(12,2,4) c(1,3,1) c(2,3,1) c(3,3,1) c(4,3,1) c(5,3,1) c(6,3,2) c(7,3,2) c(8,3,2) c(9,3,2) c(10,3,4) c(11,3,4) c(12,3,4) c(1,4,5) c(2,4,5) c(3,4,5) c(4,4,1) c(5,4,6) c(6,4,6) c(7,4,6) c(8,4,7) c(9,4,2) c(10,4,7) c(11,4,8) c(12,4,8) c(1,5,5) c(2,5,5) c(3,5,1) c(4,5,1) c(5,5,6) c(6,5,6) c(7,5,6) c(8,5,7) c(9,5,2) c(10,5,7) c(11,5,8) c(12,5,8) c(1,6,5) c(2,6,5) c(3,6,6) c(4,6,6) c(5,6,6) c(6,6,6) c(7,6,6) c(8,6,7) c(9,6,7) c(10,6,7) c(11,6,8) c(12,6,8) c(1,7,5) c(2,7,5) c(3,7,5) c(4,7,6) c(5,7,9) c(6,7,10) c(7,7,6) c(8,7,6) c(9,7,7) c(10,7,8) c(11,7,8) c(12,7,8) c(1,8,9) c(2,8,9) c(3,8,5) c(4,8,9) c(5,8,9) c(6,8,10) c(7,8,10) c(8,8,10) c(9,8,10) c(10,8,11) c(11,8,8) c(12,8,8) c(1,9,9) c(2,9,9) c(3,9,9) c(4,9,9) c(5,9,9) c(6,9,10) c(7,9,10) c(8,9,10) c(9,9,10) c(10,9,11) c(11,9,8) c(12,9,11) c(1,10,12) c(2,10,12) c(3,10,10) c(4,10,10) c(5,10,10) c(6,10,10) c(7,10,10) c(8,10,10) c(9,10,10) c(10,10,11) c(11,10,11) c(12,10,11) c(1,11,12) c(2,11,12) c(3,11,12) c(4,11,12) c(5,11,12) c(6,11,12) c(7,11,11) c(8,11,11) c(9,11,11) c(10,11,11) c(11,11,11) c(12,11,11) c(1,12,12) c(2,12,12) c(3,12,12) c(4,12,12) c(5,12,12) c(6,12,12) c(7,12,11) c(8,12,11) c(9,12,11) c(10,12,11) c(11,12,11) c(12,12,11) t(1,7) t(1,9) t(2,3) t(2,11) t(3,5) t(3,8) t(4,10) t(4,12) t(5,5) t(5,8) t(6,2) t(6,10) t(7,4) t(7,12) t(8,2) t(8,6) t(9,4) t(9,11) t(10,1) t(10,6) t(11,3) t(11,9) t(12,1) t(12,7)
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.009s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Aby ułatwić obsługę formatu wejścia / wyjścia, oto programy w języku Python do konwersji zi do formatu podanego w wyzwaniu.

Wejście

import sys
print(' '.join("c({},{},{}).".format(x + 1, y + 1, ord(cell) - ord('a') + 1) for y, row in enumerate(sys.stdin.read().splitlines()) for x, cell in enumerate(row)))

Wynik

import re
import sys
for line in sys.stdin:
    c = {(int(x), int(y)): int(z) for x, y, z in re.findall(r'\bc\((\d+),(\d+),(\d+)\)', line)}
    if c:
        t = {(int(x), int(y)) for x, y in re.findall(r'\bt\((\d+),(\d+)\)', line)}
        n, n = max(c)
        for y in range(1, n + 1):
            print(''.join(chr(ord('aA'[(x, y) in t]) + c[x, y] - 1) for x in range(1, n + 1)))
        print()