Twoim zadaniem jest napisanie programu (lub dwóch oddzielnych programów) w dowolnym języku, który:

1. Może wziąć skompletowaną planszę Sudoku jako dane wejściowe (w dowolnym formacie logicznym) i skompresować ją do ciągu znaków
2. Może wziąć skompresowany ciąg jako dane wejściowe i rozpakować go, aby uzyskać dokładnie tę samą ukończoną tablicę Sudoku (wyjście w dowolnym logicznym formacie 9 wierszy)

Uwaga: użyj reguł Sudoku na swoją korzyść; taka jest idea tego wyzwania.
Sudoku rządzi Wikipedią

Zasady

• W skompresowanym wyjściu dozwolone są tylko drukowalne znaki ASCII (32–126) (np. Brak znaków wielobajtowych ).
• Możesz założyć, że wejście jest prawidłową tablicą Sudoku 3x3 (normalne zasady, bez zmian).
• Nie narzucę limitu czasu, ale nie tworzę algorytmu brutalnej siły. Lub osoby zgłaszające powinny być w stanie przetestować swoje zgłoszenia przed opublikowaniem (Dzięki Jan Dvorak).

Jeśli masz jakieś pytania lub wątpliwości, możesz poprosić o wyjaśnienia lub sugestie w komentarzach.

Warunki wygranej

Wynik = suma liczby znaków ze wszystkich dziesięciu przypadków testowych

Najniższy wynik wygrywa.

Przypadki testowe

Możesz użyć ich do sprawdzenia, jak działa Twój program.

9 7 3 5 8 1 4 2 6
5 2 6 4 7 3 1 9 8
1 8 4 2 9 6 7 5 3
2 4 7 8 6 5 3 1 9
3 9 8 1 2 4 6 7 5
6 5 1 7 3 9 8 4 2
8 1 9 3 4 2 5 6 7
7 6 5 9 1 8 2 3 4
4 3 2 6 5 7 9 8 1

7 2 4 8 6 5 1 9 3
1 6 9 2 4 3 8 7 5
3 8 5 1 9 7 2 4 6
8 9 6 7 2 4 3 5 1
2 7 3 9 5 1 6 8 4
4 5 1 3 8 6 9 2 7
5 4 2 6 3 9 7 1 8
6 1 8 5 7 2 4 3 9
9 3 7 4 1 8 5 6 2

1 5 7 6 8 2 3 4 9
4 3 2 5 1 9 6 8 7
6 9 8 3 4 7 2 5 1
8 2 5 4 7 6 1 9 3
7 1 3 9 2 8 4 6 5
9 6 4 1 3 5 7 2 8
5 4 1 2 9 3 8 7 6
2 8 9 7 6 1 5 3 4
3 7 6 8 5 4 9 1 2

8 3 5 4 1 6 9 2 7
2 9 6 8 5 7 4 3 1
4 1 7 2 9 3 6 5 8
5 6 9 1 3 4 7 8 2
1 2 3 6 7 8 5 4 9
7 4 8 5 2 9 1 6 3
6 5 2 7 8 1 3 9 4
9 8 1 3 4 5 2 7 6
3 7 4 9 6 2 8 1 5

6 2 8 4 5 1 7 9 3
5 9 4 7 3 2 6 8 1
7 1 3 6 8 9 5 4 2
2 4 7 3 1 5 8 6 9
9 6 1 8 2 7 3 5 4
3 8 5 9 6 4 2 1 7
1 5 6 2 4 3 9 7 8
4 3 9 5 7 8 1 2 6
8 7 2 1 9 6 4 3 5

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 8 9 7 2
6 4 8 9 7 2 5 3 1
9 7 2 5 3 1 6 4 8

1 4 5 7 9 2 8 3 6
3 7 6 5 8 4 1 9 2
2 9 8 3 6 1 7 5 4
7 3 1 9 2 8 6 4 5
8 5 9 6 4 7 3 2 1
4 6 2 1 3 5 9 8 7
6 2 4 8 7 3 5 1 9
5 8 7 4 1 9 2 6 3
9 1 3 2 5 6 4 7 8

5 2 7 4 1 6 9 3 8
8 6 4 3 2 9 1 5 7
1 3 9 5 7 8 6 4 2
2 9 1 8 5 4 3 7 6
3 4 8 6 9 7 5 2 1
6 7 5 1 3 2 4 8 9
7 1 2 9 4 5 8 6 3
4 8 3 2 6 1 7 9 5
9 5 6 7 8 3 2 1 4

2 4 6 7 1 3 9 8 5
1 8 5 4 9 6 7 3 2
9 3 7 8 2 5 1 4 6
6 7 8 5 4 2 3 9 1
4 9 3 1 6 8 2 5 7
5 1 2 3 7 9 4 6 8
8 2 4 9 5 7 6 1 3
7 5 9 6 3 1 8 2 4
3 6 1 2 8 4 5 7 9

8 6 1 2 9 4 5 7 3
4 7 5 3 1 8 6 9 2
3 9 2 5 6 7 8 1 4
2 3 6 4 5 9 7 8 1
1 5 4 7 8 3 2 6 9
9 8 7 6 2 1 3 4 5
5 2 9 1 7 6 4 3 8
6 4 8 9 3 2 1 5 7
7 1 3 8 4 5 9 2 6

Podziękowania dla http://www.opensky.ca/~jdhildeb/software/sudokugen/ dla niektórych z nich

Jeśli znajdziesz jakieś problemy z przypadkami testowymi, powiedz mi.

Haskell, 107 punktów

import Control.Monad
import Data.List

type Elem = Char
type Board = [[Elem]]
type Constraints = ([Elem],[Elem],[Elem])

digits :: [Elem]
digits = "123456789"
noCons :: Constraints
noCons = ([],[],[])
disjointCons :: Constraints
disjointCons = ("123","456","789") -- constraints from a single block - up to isomorphism
triples :: [a] -> [[a]]
triples [a,b,c,d,e,f,g,h,i] = [[a,b,c],[d,e,f],[g,h,i]]
(+++) :: Constraints -> Constraints -> Constraints
(a,b,c) +++ (d,e,f) = (a++d,b++e,c++f)

maxB = 12096 
-- length $ assignments noCons disjointCons
maxC = 216 -- worst case: rows can be assigned independently
maxD = maxB
maxE = 448
-- foldl1' max [length $ assignments disjointCons colCons
--             | (_, colCons) <- map constraints $ assignments ([],[1],[1]) ([],[1],[1]),
--               let ([a,d,g],[b,e,h],[c,f,i]) = colCons,
--               a < d, d < g, b < e, e < h, c < f, f < i]
maxF = 2 ^ 3 -- for each row the relevant column constraints can be in the same column (no assignment), 
             -- or in two or three columns (two assignments)
maxG = maxC
maxH = maxF

-- constraints -> list of block solutions
assignments :: Constraints -> Constraints -> [[Elem]]
assignments (r1,r2,r3) (c1,c2,c3) = do
    a <- digits  \\ (r1 ++ c1); let digits1 = digits  \\ [a]
    b <- digits1 \\ (r1 ++ c2); let digits2 = digits1 \\ [b]
    c <- digits2 \\ (r1 ++ c3); let digits3 = digits2 \\ [c]
    d <- digits3 \\ (r2 ++ c1); let digits4 = digits3 \\ [d]
    e <- digits4 \\ (r2 ++ c2); let digits5 = digits4 \\ [e]
    f <- digits5 \\ (r2 ++ c3); let digits6 = digits5 \\ [f]
    g <- digits6 \\ (r3 ++ c1); let digits7 = digits6 \\ [g]
    h <- digits7 \\ (r3 ++ c2); let digits8 = digits7 \\ [h]
    i <- digits8 \\ (r3 ++ c3)
    return [a,b,c,d,e,f,g,h,i]

-- block solution -> tuple of constraints
constraints :: [Elem] -> (Constraints, Constraints)
constraints [a,b,c,d,e,f,g,h,i] = (([a,b,c],[d,e,f],[g,h,i]),([a,d,g],[b,e,h],[c,f,i]))

------------------------------------------------------------------------------------------

-- solution -> Integer
solution2ix :: Board -> Integer
solution2ix [a,b,c,d,e,f,g,h,i] =
    let (ar, ac) = constraints a
        (br, bc) = constraints b
        (_ , cc) = constraints c
        (dr, dc) = constraints d
        (er, ec) = constraints e
        (_ , fc) = constraints f
        (gr, _ ) = constraints g
        (hr, _ ) = constraints h
        (_ , _ ) = constraints i

        Just ixA = findIndex (a ==) $ assignments noCons      noCons
        Just ixB = findIndex (b ==) $ assignments ar          noCons
        Just ixC = findIndex (c ==) $ assignments (ar +++ br) noCons
        Just ixD = findIndex (d ==) $ assignments noCons      ac
        Just ixE = findIndex (e ==) $ assignments dr          bc
        Just ixF = findIndex (f ==) $ assignments (dr +++ er) cc
        Just ixG = findIndex (g ==) $ assignments noCons      (ac +++ dc)
        Just ixH = findIndex (h ==) $ assignments gr          (bc +++ ec)
        Just ixI = findIndex (i ==) $ assignments (gr +++ hr) (cc +++ fc)

    in foldr (\(i,m) acc -> fromIntegral i + m * acc) (fromIntegral ixA)
     $ zip [ixH, ixG, ixF, ixE, ixD, ixC, ixB] [maxH, maxG, maxF, maxE, maxD, maxC, maxB]

--    list of rows 
-- -> list of threes of triples
-- -> three triples of threes of triples 
-- -> three threes of triples of triples
-- -> nine triples of triples
-- -> nine blocks
toBoard :: [[Elem]] -> Board
toBoard = map concat . concat . map transpose . triples . map triples

toBase95 :: Integer -> String
toBase95 0 = ""
toBase95 ix = toEnum (32 + fromInteger (ix `mod` 95)) : toBase95 (ix `div` 95)

------------------------------------------------------------------------------------------

ix2solution :: Integer -> Board
ix2solution ix =
    let (ixH', ixH) = ix   `divMod` maxH
        (ixG', ixG) = ixH' `divMod` maxG
        (ixF', ixF) = ixG' `divMod` maxF
        (ixE', ixE) = ixF' `divMod` maxE
        (ixD', ixD) = ixE' `divMod` maxD
        (ixC', ixC) = ixD' `divMod` maxC
        (ixA , ixB) = ixC' `divMod` maxB

        a = assignments noCons      noCons      !! fromIntegral ixA
        (ra, ca) = constraints a
        b = assignments ra          noCons      !! fromIntegral ixB
        (rb, cb) = constraints b
        c = assignments (ra +++ rb) noCons      !! fromIntegral ixC
        (_ , cc) = constraints c
        d = assignments noCons      ca          !! fromIntegral ixD
        (rd, cd) = constraints d
        e = assignments rd          cb          !! fromIntegral ixE
        (re, ce) = constraints e
        f = assignments (rd +++ re) cc          !! fromIntegral ixF
        (_ , cf) = constraints f
        g = assignments noCons      (ca +++ cd) !! fromIntegral ixG
        (rg, _ ) = constraints g
        h = assignments rg          (cb +++ ce) !! fromIntegral ixH
        (rh, _ ) = constraints h
        [i] = assignments (rg +++ rh) (cc +++ cf)
    in  [a,b,c,d,e,f,g,h,i]

--    nine blocks
-- -> nine triples of triples
-- -> three threes of triples of triples
-- -> three triples of threes of triples
-- -> list of threes of triples
-- -> list of rows
fromBoard :: Board -> [[Elem]]
fromBoard = map concat . concat . map transpose . triples . map triples

fromBase95 :: String -> Integer
fromBase95 ""     = 0
fromBase95 (x:xs) = (toInteger $ fromEnum x) - 32 + 95 * fromBase95 xs

------------------------------------------------------------------------------------------

main = do line <- getLine
          if length line <= 12
             then putStrLn $ unlines $ map (intersperse ' ') $ fromBoard $ ix2solution $ fromBase95 line
             else do nextLines <- replicateM 8 getLine
                     putStrLn $ toBase95 $ solution2ix $ toBoard $ map (map head.words) $ line:nextLines

Wyniki przypadku testowego:

q`3T/v50 =3,
^0NK(F4(V6T(
d KTTB{pJc[
B]^v[omnBF-*
WZslDPbcOm7'
)
ukVl2x/[+6F
qzw>GjmPxzo%
KE:*GH@H>(m!
SeM=kA`'3(X*

Kod nie jest ładny, ale działa. Podstawą algorytmu jest to, że chociaż wyliczenie wszystkich rozwiązań zajęłoby zbyt dużo czasu, wyliczenie wszystkich rozwiązań w jednym bloku jest raczej szybkie - w rzeczywistości jest szybsze niż późniejsza konwersja do base95. Wszystko działa w ciągu kilku sekund w tłumaczu na mojej niskiej jakości maszynie. Skompilowany program zakończyłby się natychmiast.

Ciężkie podnoszenie odbywa się za pomocą solution2ixfunkcji, która dla każdego bloku 3x3 generuje wszystkie możliwe permutacje, z zastrzeżeniem ograniczeń od lewej i od góry, aż znajdzie to w zakodowanym rozwiązaniu, pamiętając tylko indeks wspomnianej permutacji. Następnie łączy indeksy przy użyciu wstępnie obliczonych wag i schematu Hornera.

W przeciwnym kierunku ix2solutionfunkcja najpierw rozkłada indeks na dziewięć wartości. Następnie dla każdego bloku indeksuje listę możliwych kombinacji z odpowiednią wartością, a następnie wyodrębnia ograniczenia dla kolejnych bloków.

assignmentsjest prostą, ale brzydką, rozwiniętą rekurencją za pomocą monady listy. Generuje listę permutacji na podstawie zestawu ograniczeń.

Rzeczywista moc pochodzi z ciasnych granic długości list permutacji:

• Lewy górny róg jest nieograniczony. Liczba permutacji jest po prostu 9!. Ta wartość nigdy nie jest używana, z wyjątkiem znalezienia górnej granicy długości wyjściowej.
• Bloki obok niego mają tylko jeden zestaw ograniczeń - od lewego górnego rogu. Naiwna górna granica 6*5*4*6!jest siedem razy gorsza niż faktyczna liczba wyliczona przez wyliczenie:12096
• Prawy górny róg jest ograniczony dwa razy od lewej. Każdy wiersz może mieć tylko sześć kombinacji, aw najgorszym przypadku (właściwie w każdym poprawnym przypadku) przypisanie jest niezależne. Podobnie w lewym dolnym rogu.
• Środek był najtrudniejszy do oszacowania. Po raz kolejny brutalna siła wygrywa - policz permutację dla każdego możliwego zestawu ograniczeń aż do izomorfizmu. Trwa to trochę, ale jest to potrzebne tylko raz.
• Prawy element środkowy ma podwójne wiązanie od lewej, co wymusza każdy rząd aż do permutacji, ale także pojedyncze wiązanie od góry, co zapewnia, że ​​w rzeczywistości możliwe są tylko dwie permutacje na rząd. Podobnie dla dolnej środkowej części.
• Prawy dolny róg jest w pełni określony przez sąsiadów. Jedyne permutacja nigdy nie jest weryfikowana podczas obliczania indeksu. Wymuszanie oceny byłoby łatwe, po prostu nie jest konieczne.

Iloczyn wszystkich tych limitów wynosi 71025136897117189570560~ = 95^11.5544, co oznacza, że ​​żaden kod nie jest dłuższy niż 12 znaków, a prawie połowa z nich powinna mieć 11 lub mniej znaków. Postanowiłem nie rozróżniać krótszego sznurka od tego samego sznurka wypełnionego spacjami. Miejsca w innych miejscach są znaczące.

Teoretyczna granica wydajności kodowania dla kodów wolnych od prefiksów - logarytm podstawowy 95 6670903752021072936960- oznacza 11.035, że nawet optymalny algorytm nie może uniknąć wygenerowania danych wyjściowych o długości 12, chociaż da to tylko 3,5% wszystkich przypadków. Dopuszczenie, aby długość była znacząca (lub równoważnie, dodanie spacji końcowych) powoduje dodanie kilku kodów (1% całkowitej kwoty), ale nie wystarcza, aby wyeliminować potrzebę kodów o długości 12.

Python, 130 punktów

j1:4}*KYm6?D
h^('gni9X`g'#
$2{]8=6^l=fF!
BS ;1;J:z"^a"
\/)gT)sixb"A+
WI?TFvj%:&3-\$
*iecz`L2|a`X0
eLbt<tf|mFN'&
;KH_TzK$erFa!
7T=1*6$]*"s"!

Algorytm polega na kodowaniu każdej pozycji na płycie, pojedynczo, w dużą liczbę całkowitą. Dla każdej pozycji oblicza możliwe wartości, biorąc pod uwagę wszystkie dotychczas zakodowane zadania. Jeśli więc [1,3,7,9] są możliwymi wartościami dla danej pozycji, potrzeba 2 bitów, aby zakodować wybór.

Zaletą tego schematu jest to, że jeśli pozycja ma tylko jeden pozostały wybór, kodowanie nie wymaga spacji.

Kiedy mamy już dużą liczbę całkowitą, wypisujemy ją w bazie 95.

Prawdopodobnie są lepsze porządki kodowania niż leksykograficzne, ale nie zastanawiałem się nad tym zbyt wiele.

Enkoder:

import sys

sets = [range(i*9, i*9+9) for i in xrange(9)]
sets += [range(i, 81, 9) for i in xrange(9)]
sets += [[i/3*27+i%3*3+j/3*9+j%3 for j in xrange(9)] for i in xrange(9)]

M = []
for line in sys.stdin.readlines():
    M += [int(x) for x in line.split()]

A = 0
m = 1
for i in xrange(81):
    allowed = set(xrange(1,10))
    for s in sets:
        if i in s:
            for j in s:
                if j < i: allowed.discard(M[j])
    allowed = sorted(allowed)
    A += m * allowed.index(M[i])
    m *= len(allowed)

s=''
while A != 0:
    s+='%c'%(32+A%95)
    A /= 95
print s

Dekoder:

sets = [range(i*9, i*9+9) for i in xrange(9)]
sets += [range(i, 81, 9) for i in xrange(9)]
sets += [[i/3*27+i%3*3+j/3*9+j%3 for j in xrange(9)] for i in xrange(9)]

s=raw_input()
A=0
m=1
while s != '':
    A += m * (ord(s[0])-32)
    s = s[1:]
    m *= 95

M=[]
for i in xrange(81):
    allowed = set(xrange(1,10))
    for s in sets:
        if i in s:
            for j in s:
                if j < i: allowed.discard(M[j])
    allowed = sorted(allowed)
    M += [allowed[A%len(allowed)]]
    A /= len(allowed)

for i in xrange(9):
    print ' '.join(str(x) for x in M[i*9:i*9+9])

Uruchom tak:

> cat sudoku1 | ./sudokuEnc.py | ./sudokuDec.py
9 7 3 5 8 1 4 2 6
5 2 6 4 7 3 1 9 8
1 8 4 2 9 6 7 5 3
2 4 7 8 6 5 3 1 9
3 9 8 1 2 4 6 7 5
6 5 1 7 3 9 8 4 2
8 1 9 3 4 2 5 6 7
7 6 5 9 1 8 2 3 4
4 3 2 6 5 7 9 8 1

perl - wynik 115 113 103 113

Wydajność:

"#1!A_mb_jB)
FEIV1JH~vn"
$\\XRU*LXea.
EBIC5fPxklB
5>jM7(+0MrM
!'Wu9FS2d~!W
":`R60C"}z!k
:B&Jg[fL%\j
"L28Y?3`Q>4w
o0xPz8)_i%-

Wydajność:

                  # note this line is empty
S}_h|bt:za        
%.j0.6w>?RM+
:H$>a>Cy{7C
'57UHjcWQmcw
owmK0NF?!Fv
# }aYExcZlpD
nGl^K]xH(.\
9ii]I$voC,x
!:MR0>I>PuTU

Żadna z tych linii nie ma spacji kończącej. Zauważ, że pierwszy wiersz jest pusty.

Ten algorytm działa w następujący sposób. Aby skompresować:

1. Zacznij od pustego „bieżącego” ciągu reprezentującego siatkę Sudoku

2. Zastanów się nad dodaniem po kolei każdej cyfry 1 .. 9 do tego ciągu i określ, która jest wykonalna.

3. Pobierz następną cyfrę z siatki odpowiedzi (i dodaj ją do bieżącej)

4. Jeśli tylko jeden jest wykonalny, nie ma nic do kodowania

5. Jeśli więcej niż jedna jest wykonalna, policz liczbę wykonalnych opcji, posortuj je i zakoduj tę cyfrę jako indeks w posortowanej tablicy. Zapisz cyfrę i liczbę wykonalną jako 2-krotność w tablicy.

6. Po zakończeniu należy zakodować każdą z 2 krotek (w odwrotnej kolejności) w zmiennej liczbie zapisanej jako bigint.

7. Wyraź biginta w bazie 95.

Aby zdekodować:

1. Zacznij od pustego „bieżącego” ciągu reprezentującego siatkę Sudoku

2. Dekoduj numer base95 na bigint

3. Zastanów się nad dodaniem po kolei każdej cyfry 1 .. 9 do tego ciągu i określ, która jest wykonalna.

4. Jeśli tylko jeden jest wykonalny, nie ma nic do kodowania; dodaj ten wybór do siatki

5. Jeśli więcej niż jedna jest wykonalna, policz liczbę wykonalnych opcji, posortuj je i zakoduj tę cyfrę jako indeks w posortowanej tablicy.

6. Dekoduj bigint o zmiennej podstawie, używając liczby wykonalnych opcji jako podstawy, i modułu jako indeksu w tablicy, i wyślij tę cyfrę jako wartość komórki.

Aby określić liczbę wykonalnych opcji, używa się Games :: Sudoku :: Solver. To głównie dla przejrzystości, ponieważ na tej stronie znajdują się 3-liniowe solwery Sudoku.

Wykonanie wszystkich 10 zajęło 8 sekund na moim laptopie.

fudgeDziałanie sortowanie tablicy inaczej osiągnąć minimalną wartość dla testów. Jak udokumentowano, jest to krówka. Krówka zmniejsza wynik ze 115 do 103. Jest ręcznie, aby zapewnić, że kod bigint dla pierwszego testu wynosi 0. Najgorszy wynik dla każdego sudoku to 12, co daje wynik 120. Dlatego nie sądzę, żeby to się liczyło jako na stałe; raczej optymalizuje dane testowe. Aby zobaczyć, jak działa bez tego, zmień sort fudgena sortw obu miejscach.

Kod następuje:

#!/usr/bin/perl

use strict;
use warnings;
use Getopt::Long;
use bigint;
use Games::Sudoku::Solver qw (:Minimal set_solution_max count_occupied_cells);

# NOTE THIS IS NOT USED BY DEFAULT - see below and discussion in comments
my @fudgefactor = qw (9 7 3 5 8 1 4 2 6 5 2 6 4 7 3 1 9 8 1 8 4 2 9 6 7 5 3 2 4 7 8 6 5 3 1 9 3 9 8 1 2 4 6 7 5 6 5 1 7 3 9 8 4 2 8 1 9 3 4 2 5 6 7 7 6 5 9 1 8 2 3 4 4 3 2 6 5 7 9 8 1);
my $fudgeindex=0;
my $fudging=0; # Change to 1 to decrease score by 10

sub isviable
{
    no bigint;
    my $current = shift @_;
    my @test = map {$_ + 0} split(//, substr(($current).("0"x81), 0, 81));
    my @sudoku;
    my @solution;
    set_solution_max (2);
    my $nsolutions;

    eval
    {
        sudoku_set(\@sudoku, \@test);
        $nsolutions = sudoku_solve(\@sudoku, \@solution);
    };
    return 0 unless $nsolutions;
    return ($nsolutions >=1);
}

sub getnextviable
{
    my $current = shift @_; # grid we have so far
    my %viable;

    for (my $i = 1; $i<=9; $i++)
    {
        my $n;
        my $solution;
        $viable{$i} = 1 if (isviable($current.$i));
    }
    return %viable;
}

sub fudge
{
    return $a<=>$b unless ($fudging);
    my $k=$fudgefactor[$fudgeindex];
    my $aa = ($a+10-$k) % 10;
    my $bb = ($b+10-$k) % 10;
    return $aa<=>$bb;
}


sub compress
{
    my @data;
    while (<>)
    {
        chomp;
        foreach my $d (split(/\s+/))
        {
            push @data, $d;
        }
    }

    my $code = 0;
    my $current = "";
    my @codepoints;
    foreach my $d (@data)
    {
        my %viable = getnextviable($current);
        die "Digit $d is unexpectedly not viable - is sudoku impossible?" unless ($viable{$d});

        my $nviable = scalar keys(%viable);
        if ($nviable>1)
        {
            my $n=0;
            foreach my $k (sort fudge keys %viable)
            {
                if ($k==$d)
                {
                    no bigint;
                    my %cp = ( "n"=> $n, "v"=> $nviable);
                    unshift @codepoints, \%cp;
                    last;
                }
                $n++;
            }
        }
        $fudgeindex++;
        $current .= $d;
    }

    foreach my $cp (@codepoints)
    {
        $code = ($code * $cp->{"v"})+$cp->{"n"};
    }

    # print in base 95
    my $out="";
    while ($code)
    {
        my $digit = $code % 95;
        $out = chr($digit+32).$out;
        $code -= $digit;
        $code /= 95;
    }

    print "$out";
}

sub decompress
{
    my $code = 0;

    # Read from base 95 into bigint
    while (<>)
    {
        chomp;
        foreach my $char (split (//, $_))
        {
            my $c =ord($char)-32;
            $code*=95;
            $code+=$c;
        }
    }

    # Reconstruct sudoku
    my $current = "";
    for (my $cell = 0; $cell <81; $cell++)
    {
        my %viable = getnextviable($current);
        my $nviable = scalar keys(%viable);
        die "Cell $cell is unexpectedly not viable - is sudoku impossible?" unless ($nviable);

        my $mod = $code % $nviable;
        $code -= $mod;
        $code /= $nviable;

        my @v = sort fudge keys (%viable);
        my $d = $v[$mod];
        $current .= $d;
        print $d.(($cell %9 != 8)?" ":"\n");
        $fudgeindex++;
    }
}

my $decompress;
GetOptions ("d|decompress" => \$decompress);


if ($decompress)
{
    decompress;
}
else
{
    compress;
}

CJam, 309 bajtów

To tylko szybkie rozwiązanie podstawowe. Przepraszam, że zrobiłem to w języku golfowym, ale tak naprawdę był to najprostszy sposób. Jutro dodam wyjaśnienie właściwego kodu, ale opisałem algorytm poniżej.

Enkoder

q~{);}%);:+:(9b95b32f+:c

Dekoder

l:i32f-95b9bW%[0]64*+64<W%:)8/{_:+45\-+}%z{_:+45\-+}%z`

Sprawdź to tutaj.

Dane wejściowe kodera (na STDIN) i dane wyjściowe dekodera (na STDOUT) mają postać zagnieżdżonej tablicy CJam. Na przykład

[[8 3 5 4 1 6 9 2 7] [2 9 6 8 5 7 4 3 1] [4 1 7 2 9 3 6 5 8] [5 6 9 1 3 4 7 8 2] [1 2 3 6 7 8 5 4 9] [7 4 8 5 2 9 1 6 3] [6 5 2 7 8 1 3 9 4] [9 8 1 3 4 5 2 7 6] [3 7 4 9 6 2 8 1 5]]

10 wyjść testowych to:

U(5wtqmC.-[TM.#aMY#k*)pErHQcg'{
EWrn"^@p+g<5XT5G[r1|bk?q6Nx4~r?
#489pLj5+ML+z@y$]8a@CI,K}B$$Mwn
LF_X^"-h**A!'VZq kHT@F:"ZMD?A0r
?gD;"tw<yG%8y!3S"BC:ojQ!#;i-:\g
qS#"L%`4yei?Ce_r`{@EOl66m^hx77
"EF?` %!H@YX6J0F93->%90O7T#C_5u
9V)R+6@Jx(jg@@U6.DrMO*5G'P<OHv8
(Ua6z{V:hX#sV@g0s<|!X[T,Jy|oQ+K
N,F8F1!@OH1%%zs%dI`Q\q,~oAEl(:O

Algorytm jest bardzo prosty:

• Usuń ostatnią kolumnę i wiersz.
• Traktuj pozostałe 64 cyfry jako liczbę podstawową 9 (po zmniejszeniu każdej cyfry o 1).
• Konwertuj to na base-95, dodaj 32 do każdej cyfry i zamień ją na odpowiedni znak ASCII.
• W celu dekodowania odwróć podstawową konwersję i wypełnij ostatnią kolumnę i wiersz brakującymi liczbami.

Python 2.7, łącznie 107 znaków

Wyliczenie siły brutalnej TL; DR kwadratów 3x3 z ograniczeniami górny + lewy

przypadki testowe:

import itertools

inputs = """
9 7 3 5 8 1 4 2 6
5 2 6 4 7 3 1 9 8
1 8 4 2 9 6 7 5 3
2 4 7 8 6 5 3 1 9
3 9 8 1 2 4 6 7 5
6 5 1 7 3 9 8 4 2
8 1 9 3 4 2 5 6 7
7 6 5 9 1 8 2 3 4
4 3 2 6 5 7 9 8 1

7 2 4 8 6 5 1 9 3
1 6 9 2 4 3 8 7 5
3 8 5 1 9 7 2 4 6
8 9 6 7 2 4 3 5 1
2 7 3 9 5 1 6 8 4
4 5 1 3 8 6 9 2 7
5 4 2 6 3 9 7 1 8
6 1 8 5 7 2 4 3 9
9 3 7 4 1 8 5 6 2

1 5 7 6 8 2 3 4 9
4 3 2 5 1 9 6 8 7
6 9 8 3 4 7 2 5 1
8 2 5 4 7 6 1 9 3
7 1 3 9 2 8 4 6 5
9 6 4 1 3 5 7 2 8
5 4 1 2 9 3 8 7 6
2 8 9 7 6 1 5 3 4
3 7 6 8 5 4 9 1 2

8 3 5 4 1 6 9 2 7
2 9 6 8 5 7 4 3 1
4 1 7 2 9 3 6 5 8
5 6 9 1 3 4 7 8 2
1 2 3 6 7 8 5 4 9
7 4 8 5 2 9 1 6 3
6 5 2 7 8 1 3 9 4
9 8 1 3 4 5 2 7 6
3 7 4 9 6 2 8 1 5

6 2 8 4 5 1 7 9 3
5 9 4 7 3 2 6 8 1
7 1 3 6 8 9 5 4 2
2 4 7 3 1 5 8 6 9
9 6 1 8 2 7 3 5 4
3 8 5 9 6 4 2 1 7
1 5 6 2 4 3 9 7 8
4 3 9 5 7 8 1 2 6
8 7 2 1 9 6 4 3 5

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 8 9 7 2
6 4 8 9 7 2 5 3 1
9 7 2 5 3 1 6 4 8

1 4 5 7 9 2 8 3 6
3 7 6 5 8 4 1 9 2
2 9 8 3 6 1 7 5 4
7 3 1 9 2 8 6 4 5
8 5 9 6 4 7 3 2 1
4 6 2 1 3 5 9 8 7
6 2 4 8 7 3 5 1 9
5 8 7 4 1 9 2 6 3
9 1 3 2 5 6 4 7 8

5 2 7 4 1 6 9 3 8
8 6 4 3 2 9 1 5 7
1 3 9 5 7 8 6 4 2
2 9 1 8 5 4 3 7 6
3 4 8 6 9 7 5 2 1
6 7 5 1 3 2 4 8 9
7 1 2 9 4 5 8 6 3
4 8 3 2 6 1 7 9 5
9 5 6 7 8 3 2 1 4

2 4 6 7 1 3 9 8 5
1 8 5 4 9 6 7 3 2
9 3 7 8 2 5 1 4 6
6 7 8 5 4 2 3 9 1
4 9 3 1 6 8 2 5 7
5 1 2 3 7 9 4 6 8
8 2 4 9 5 7 6 1 3
7 5 9 6 3 1 8 2 4
3 6 1 2 8 4 5 7 9

8 6 1 2 9 4 5 7 3
4 7 5 3 1 8 6 9 2
3 9 2 5 6 7 8 1 4
2 3 6 4 5 9 7 8 1
1 5 4 7 8 3 2 6 9
9 8 7 6 2 1 3 4 5
5 2 9 1 7 6 4 3 8
6 4 8 9 3 2 1 5 7
7 1 3 8 4 5 9 2 6
""".strip().split('\n\n')

funkcja pomocnicza do drukowania sudoku

def print_sudoku(m):
    for k in m:
        print' '.join(str(i) for i in k)

generuje wszystkie możliwe kwadraty, biorąc pod uwagę ograniczenia powyżej i po lewej stronie

więcej szczegółów w komentarzu do kodu

def potential_squares(u1, u2, u3, l1, l2, l3):
    """
    returns generator of possible squares given lists of digits above and below

           u1 u2 u3
           |  |  |
    l1 --  a  b  c
    l2 --  d  e  f
    l3 --  g  h  i

    if no items exist the empty list must be given
    """
    for a, b, c, d, e, f, g, h, i in itertools.permutations(xrange(1, 10)):
        if a not in u1 and a not in l1 and b not in u2 and b not in l1 and c not in u3 and c not in l1 and d not in u1 and d not in l2 and e not in u2 and e not in l2 and f not in u3 and f not in l2 and g not in u1 and g not in l3 and h not in u2 and h not in l3 and i not in u3 and i not in l3:
            yield (a, b, c, d, e, f, g, h, i)

wyodrębnia wszystkie kwadraty z planszy sudoku jako krotki

więcej szczegółów w komentarzu do kodu

def board_to_squares(board):
    """
    finds 9 squares in a 9x9 board in this order:
    1 1 1 2 2 2 3 3 3
    1 1 1 2 2 2 3 3 3
    1 1 1 2 2 2 3 3 3
    4 4 4 5 5 5 6 6 6
    4 4 4 5 5 5 6 6 6
    4 4 4 5 5 5 6 6 6
    7 7 7 8 8 8 9 9 9
    7 7 7 8 8 8 9 9 9
    7 7 7 8 8 8 9 9 9

    returns tuple for each square as follows:
    a b c
    d e f   -->  (a,b,c,d,e,f,g,h,i)
    g h i
    """
    labels = [[3 * i + 1] * 3 + [3 * i + 2] * 3 + [3 * i + 3] * 3 for i in [0, 0, 0, 1, 1, 1, 2, 2, 2]]
    labelled_board = zip(sum(board, []), sum(labels, []))
    return [tuple(a for a, b in labelled_board if b == sq) for sq in xrange(1, 10)]

konwertuje kwadraty z powrotem na planszę sudoku

w zasadzie odwrotność powyższej funkcji

def squares_to_board(squares):
    """
    inverse of above
    """
    board = [[i / 3 * 27 + i % 3 * 3 + j / 3 * 9 + j % 3 for j in range(9)] for i in range(9)]
    flattened = sum([list(square) for square in squares], [])
    for i in range(9):
        for j in range(9):
            board[i][j] = flattened[board[i][j]]
    return board

podane kwadraty w lewo, zwróć ograniczenia

więcej szczegółów w komentarzu do kodu

def sum_rows(*squares):
    """
    takes tuples for squares and returns lists corresponding to the rows:
    l1 -- a b c   j k l
    l2 -- d e f   m n o  ...
    l3 -- g h i   p q r
    """
    l1 = []
    l2 = []
    l3 = []
    if len(squares):
        for a, b, c, d, e, f, g, h, i in squares:
            l1 += [a, b, c]
            l2 += [d, e, f]
            l3 += [g, h, i]
        return l1, l2, l3
    return [], [], []

podane kwadraty powyżej, zwróć ograniczenia

więcej szczegółów w komentarzu do kodu

def sum_cols(*squares):
    """
    takes tuples for squares and returns lists corresponding to the cols:

    u1 u2 u3
    |  |  |
    a  b  c
    d  e  f
    g  h  i

    j  k  l
    m  n  o
    p  q  r

      ...

    """
    u1 = []
    u2 = []
    u3 = []
    if len(squares):
        for a, b, c, d, e, f, g, h, i in squares:
            u1 += [a, d, g]
            u2 += [b, e, h]
            u3 += [c, f, i]
        return u1, u2, u3
    return [], [], []

robi ciąg

def base95(A):
    if type(A) is int or type(A) is long:
        s = ''
        while A > 0:
            s += chr(32 + A % 95)
            A /= 95
        return s
    if type(A) is str:
        return sum((ord(c) - 32) * (95 ** i) for i, c in enumerate(A))

jest to zakodowana na stałe lista zależności dla każdego kwadratu

więcej szczegółów w komentarzu do kodu

"""
dependencies: every square as labeled
1 2 3
4 5 6
7 8 9
is dependent on those above and to the left

in a dictionary, it is:
square: ([above],[left])
"""
dependencies = {1: ([], []), 2: ([], [1]), 3: ([], [1, 2]), 4: ([1], []), 5: ([2], [4]), 6: ([3], [4, 5]),
                7: ([1, 4], []), 8: ([2, 5], [7]), 9: ([3, 6], [7, 8])}

jest to zakodowana lista maksymalnej liczby możliwych opcji dla każdego kwadratu

więcej szczegółów w komentarzu do kodu

"""
max possible options for a given element

  9 8 7   ? ? ?   3 2 1
  6 5 4  (12096)  3 2 1
  3 2 1   ? ? ?   3 2 1

  ? ? ?   ? ? ?   2 2 1
 (12096)  (420)   2 1 1    (limits for squares 2,4 determined experimentally)
  ? ? ?   ? ? ?   1 1 1    (limit for square 5 is a pessimistic guess, might be wrong)

  3 3 3   2 2 1   1 1 1
  2 2 2   2 1 1   1 1 1
  1 1 1   1 1 1   1 1 1
"""
possibilities = [362880, 12096, 216, 12096, 420, 8, 216, 8, 1]

łączą one powyższe funkcje i przekształcają tablicę w listę liczb całkowitych

def factorize_sudoku(board):
    squares = board_to_squares(board)
    factors = []

    for label in xrange(1, 10):
        above, left = dependencies[label]
        u1, u2, u3 = sum_cols(*[sq for i, sq in enumerate(squares) if i + 1 in above])
        l1, l2, l3 = sum_rows(*[sq for i, sq in enumerate(squares) if i + 1 in left])
        for i, k in enumerate(potential_squares(u1, u2, u3, l1, l2, l3)):
            if k == squares[label - 1]:
                factors.append(i)
                continue
    return factors

i z powrotem na tablicę

def unfactorize_sudoku(factors):
    squares = []
    for label in xrange(1, 10):
        factor = factors[label - 1]
        above, left = dependencies[label]
        u1, u2, u3 = sum_cols(*[sq for i, sq in enumerate(squares) if i + 1 in above])
        l1, l2, l3 = sum_rows(*[sq for i, sq in enumerate(squares) if i + 1 in left])
        for i, k in enumerate(potential_squares(u1, u2, u3, l1, l2, l3)):
            if i == factor:
                squares.append(k)
                continue
    return squares

ok, to są wszystkie funkcje

dla każdej planszy zrób ciąg i wydrukuj go

strings = []
for sudoku in inputs:
    board = [[int(x) for x in line.split()] for line in sudoku.strip().split('\n')]
    print_sudoku(board)
    factors = factorize_sudoku(board)

    i = 0
    for item, modulus in zip(factors, possibilities):
        i *= modulus
        i += item

    strings.append(base95(i))
    print 'integral representation:', i
    print 'bits of entropy:', i.bit_length()
    print 'base95 representation:', strings[-1]
    print ''

teraz wydrukuj całkowitą długość wszystkich łańcuchów

print 'overall output:', strings
print 'total length:', len(''.join(strings))
print ''

i un-stringify, aby udowodnić, że nie jest to kompresja w jedną stronę

for string in strings:
    print 'from:', string

    i = base95(string)
    retrieved = []
    for base in possibilities[::-1]:
        retrieved.append(i % base)
        i /= base

    squares = unfactorize_sudoku(retrieved[::-1])
    print_sudoku(squares_to_board(squares))
    print ''

wydajność:

9 7 3 5 8 1 4 2 6
5 2 6 4 7 3 1 9 8
1 8 4 2 9 6 7 5 3
2 4 7 8 6 5 3 1 9
3 9 8 1 2 4 6 7 5
6 5 1 7 3 9 8 4 2
8 1 9 3 4 2 5 6 7
7 6 5 9 1 8 2 3 4
4 3 2 6 5 7 9 8 1
integral representation: 65073646522550110083448
bits of entropy: 76
base95 representation: 23f!dvoR[pI+

7 2 4 8 6 5 1 9 3
1 6 9 2 4 3 8 7 5
3 8 5 1 9 7 2 4 6
8 9 6 7 2 4 3 5 1
2 7 3 9 5 1 6 8 4
4 5 1 3 8 6 9 2 7
5 4 2 6 3 9 7 1 8
6 1 8 5 7 2 4 3 9
9 3 7 4 1 8 5 6 2
integral representation: 45592184788002754998731
bits of entropy: 76
base95 representation: +gel3sJ?vL!(

1 5 7 6 8 2 3 4 9
4 3 2 5 1 9 6 8 7
6 9 8 3 4 7 2 5 1
8 2 5 4 7 6 1 9 3
7 1 3 9 2 8 4 6 5
9 6 4 1 3 5 7 2 8
5 4 1 2 9 3 8 7 6
2 8 9 7 6 1 5 3 4
3 7 6 8 5 4 9 1 2
integral representation: 3351617758498333760666
bits of entropy: 72
base95 representation: !"=W3R"`w|W

8 3 5 4 1 6 9 2 7
2 9 6 8 5 7 4 3 1
4 1 7 2 9 3 6 5 8
5 6 9 1 3 4 7 8 2
1 2 3 6 7 8 5 4 9
7 4 8 5 2 9 1 6 3
6 5 2 7 8 1 3 9 4
9 8 1 3 4 5 2 7 6
3 7 4 9 6 2 8 1 5
integral representation: 54077388556332388193975
bits of entropy: 76
base95 representation: zAu5Rvno.2P)

6 2 8 4 5 1 7 9 3
5 9 4 7 3 2 6 8 1
7 1 3 6 8 9 5 4 2
2 4 7 3 1 5 8 6 9
9 6 1 8 2 7 3 5 4
3 8 5 9 6 4 2 1 7
1 5 6 2 4 3 9 7 8
4 3 9 5 7 8 1 2 6
8 7 2 1 9 6 4 3 5
integral representation: 38664325462033435490761
bits of entropy: 76
base95 representation: ?8KJHGXS^hk&

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 8 9 7 2
6 4 8 9 7 2 5 3 1
9 7 2 5 3 1 6 4 8
integral representation: 9
bits of entropy: 4
base95 representation: )

1 4 5 7 9 2 8 3 6
3 7 6 5 8 4 1 9 2
2 9 8 3 6 1 7 5 4
7 3 1 9 2 8 6 4 5
8 5 9 6 4 7 3 2 1
4 6 2 1 3 5 9 8 7
6 2 4 8 7 3 5 1 9
5 8 7 4 1 9 2 6 3
9 1 3 2 5 6 4 7 8
integral representation: 2146071528999475941021
bits of entropy: 71
base95 representation: ]ib2[x.u*pC

5 2 7 4 1 6 9 3 8
8 6 4 3 2 9 1 5 7
1 3 9 5 7 8 6 4 2
2 9 1 8 5 4 3 7 6
3 4 8 6 9 7 5 2 1
6 7 5 1 3 2 4 8 9
7 1 2 9 4 5 8 6 3
4 8 3 2 6 1 7 9 5
9 5 6 7 8 3 2 1 4
integral representation: 31150627593616723824594
bits of entropy: 75
base95 representation: BFK1'H9}r9M%

2 4 6 7 1 3 9 8 5
1 8 5 4 9 6 7 3 2
9 3 7 8 2 5 1 4 6
6 7 8 5 4 2 3 9 1
4 9 3 1 6 8 2 5 7
5 1 2 3 7 9 4 6 8
8 2 4 9 5 7 6 1 3
7 5 9 6 3 1 8 2 4
3 6 1 2 8 4 5 7 9
integral representation: 9659549243898865961967
bits of entropy: 74
base95 representation: ;EOSPiy9T?b!

8 6 1 2 9 4 5 7 3
4 7 5 3 1 8 6 9 2
3 9 2 5 6 7 8 1 4
2 3 6 4 5 9 7 8 1
1 5 4 7 8 3 2 6 9
9 8 7 6 2 1 3 4 5
5 2 9 1 7 6 4 3 8
6 4 8 9 3 2 1 5 7
7 1 3 8 4 5 9 2 6
integral representation: 56473223126891371769434
bits of entropy: 76
base95 representation: 3TLSl3hPU3x)

overall output: ['23f!dvoR[pI+', '+gel3sJ?vL!(', '!"=W3R"`w|W', 'zAu5Rvno.2P)', '?8KJHGXS^hk&', ')', ']ib2[x.u*pC', "BFK1'H9}r9M%", ';EOSPiy9T?b!', '3TLSl3hPU3x)']
total length: 107

from: 23f!dvoR[pI+
9 7 3 5 8 1 4 2 6
5 2 6 4 7 3 1 9 8
1 8 4 2 9 6 7 5 3
2 4 7 8 6 5 3 1 9
3 9 8 1 2 4 6 7 5
6 5 1 7 3 9 8 4 2
8 1 9 3 4 2 5 6 7
7 6 5 9 1 8 2 3 4
4 3 2 6 5 7 9 8 1

from: +gel3sJ?vL!(
7 2 4 8 6 5 1 9 3
1 6 9 2 4 3 8 7 5
3 8 5 1 9 7 2 4 6
8 9 6 7 2 4 3 5 1
2 7 3 9 5 1 6 8 4
4 5 1 3 8 6 9 2 7
5 4 2 6 3 9 7 1 8
6 1 8 5 7 2 4 3 9
9 3 7 4 1 8 5 6 2

from: !"=W3R"`w|W
1 5 7 6 8 2 3 4 9
4 3 2 5 1 9 6 8 7
6 9 8 3 4 7 2 5 1
8 2 5 4 7 6 1 9 3
7 1 3 9 2 8 4 6 5
9 6 4 1 3 5 7 2 8
5 4 1 2 9 3 8 7 6
2 8 9 7 6 1 5 3 4
3 7 6 8 5 4 9 1 2

from: zAu5Rvno.2P)
8 3 5 4 1 6 9 2 7
2 9 6 8 5 7 4 3 1
4 1 7 2 9 3 6 5 8
5 6 9 1 3 4 7 8 2
1 2 3 6 7 8 5 4 9
7 4 8 5 2 9 1 6 3
6 5 2 7 8 1 3 9 4
9 8 1 3 4 5 2 7 6
3 7 4 9 6 2 8 1 5

from: ?8KJHGXS^hk&
6 2 8 4 5 1 7 9 3
5 9 4 7 3 2 6 8 1
7 1 3 6 8 9 5 4 2
2 4 7 3 1 5 8 6 9
9 6 1 8 2 7 3 5 4
3 8 5 9 6 4 2 1 7
1 5 6 2 4 3 9 7 8
4 3 9 5 7 8 1 2 6
8 7 2 1 9 6 4 3 5

from: )
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 8 9 7 2
6 4 8 9 7 2 5 3 1
9 7 2 5 3 1 6 4 8

from: ]ib2[x.u*pC
1 4 5 7 9 2 8 3 6
3 7 6 5 8 4 1 9 2
2 9 8 3 6 1 7 5 4
7 3 1 9 2 8 6 4 5
8 5 9 6 4 7 3 2 1
4 6 2 1 3 5 9 8 7
6 2 4 8 7 3 5 1 9
5 8 7 4 1 9 2 6 3
9 1 3 2 5 6 4 7 8

from: BFK1'H9}r9M%
5 2 7 4 1 6 9 3 8
8 6 4 3 2 9 1 5 7
1 3 9 5 7 8 6 4 2
2 9 1 8 5 4 3 7 6
3 4 8 6 9 7 5 2 1
6 7 5 1 3 2 4 8 9
7 1 2 9 4 5 8 6 3
4 8 3 2 6 1 7 9 5
9 5 6 7 8 3 2 1 4

from: ;EOSPiy9T?b!
2 4 6 7 1 3 9 8 5
1 8 5 4 9 6 7 3 2
9 3 7 8 2 5 1 4 6
6 7 8 5 4 2 3 9 1
4 9 3 1 6 8 2 5 7
5 1 2 3 7 9 4 6 8
8 2 4 9 5 7 6 1 3
7 5 9 6 3 1 8 2 4
3 6 1 2 8 4 5 7 9

from: 3TLSl3hPU3x)
8 6 1 2 9 4 5 7 3
4 7 5 3 1 8 6 9 2
3 9 2 5 6 7 8 1 4
2 3 6 4 5 9 7 8 1
1 5 4 7 8 3 2 6 9
9 8 7 6 2 1 3 4 5
5 2 9 1 7 6 4 3 8
6 4 8 9 3 2 1 5 7
7 1 3 8 4 5 9 2 6

Mathematica, wynik: 130 9

Aktualizacja:

Po opublikowaniu tej odpowiedzi zainspirowała ona nową lukę bliższą: „Optymalizacja dla podanych przypadków testowych” . Pozostawię jednak tę odpowiedź taką, jaka jest, jako przykład luki. Zapraszam do głosowania. Nie skrzywdzi mnie to.

rule=({#}&/@Union[Join[
        Range[#+1,Ceiling[#,9]],Range[#+9,81,9],
        Flatten[Outer[Plus,Range[Floor[#+8,9],Ceiling[#,27]-9,9],
            Floor[Mod[#-1,9],3]+Range[3]]]]])&/@Range[81];

encode[board_]:=
Block[{step,code,pos},
    step[{left_,x_,m_},n_]:={
        MapAt[Complement[#,{board[[n]]}]&,left,rule[[n]]],
        x+m(FirstPosition[left[[n]],board[[n]]][[1]]-1),m Length[left[[n]]]};
    code=Fold[step,{Table[Range[9],{81}],0,1},Range[81]][[2]];
    pos=Position[{206638498064127103948214,1665188010993633759502287,
        760714067080859855534739,1454154263752219616902129,6131826927558056238360710,
        237833524138130760909081600,8968162948536417279508170,3284755189143784030943149,
        912407486534781347155987,556706937207676220045188},code];
    code=If[pos==={},code+10,pos[[1,1]]-1];
    FromCharacterCode[If[code==0,{},IntegerDigits[code,95]+32]]
]    

decode[str_]:=
Block[{step,code},
    code=FromDigits[ToCharacterCode[str]-32,95];
    code=If[code<10,{206638498064127103948214,1665188010993633759502287,
        760714067080859855534739,1454154263752219616902129,6131826927558056238360710,
        237833524138130760909081600,8968162948536417279508170,3284755189143784030943149,
        912407486534781347155987,556706937207676220045188}[[code+1]],code-10];
    step[{left_,x_,board_},n_]:=Function[z,{
        MapAt[Complement[#,{z}]&,left,rule[[n]]],Quotient[x,Length[left[[n]]]],
        Append[board,z]}][left[[n,Mod[x,Length[left[[n]]]]+1]]];
    Fold[step,{Table[Range[9],{81}],code,{}},Range[81]][[3]]
]

Zakodowane przypadki testowe:

     <- empty string
!
"
#
$
%
&
'
(
)

Nie skutkuje to doskonałym kodowaniem (średnio ~ 11), ponieważ podstawowe zasady nie wykluczają niektórych wyborów, dla których w rzeczywistości nie ma rozwiązania. Wydajność można by dopracować (tzn. Duża liczba całkowita zawsze byłaby mniejsza niż liczba możliwych plansz Sudoku), sprawdzając, czy nie ma rozwiązania niektórych obecnych wyborów za pomocą solwera Sudoku, a także eliminując je.

J, 254 punkty

fwrite&'sudoku.z' 1 u: u: 32 + (26$95) #: (9 $ !9x)#. A."1 (1&".);._2 stdin''

echo A.&(>:i.9)"1 (9 $ !9x) #: 95x #. 32 -~ 3 u: fread'sudoku.z'

Standardowe We / Wy jest trochę nieporadne w J, ponieważ w jconsolerzeczywistości jest REPL, więc mogłem zapisać skompresowane wyjście do pliku.

Znajduje indeks anagramowy każdej linii, traktuje powstałe dziewięć liczb jako liczbę podstawową (9!), A następnie ostatecznie konwertuje na bazę 95, dodaje 32 i konwertuje do ASCII, tak jak w rozwiązaniu Martina Büttnera. Indeks anagramowy permutacji 1..n jest po prostu indeksem permutacji na uporządkowanej leksykalnie liście wszystkich takich permutacji, np. 5 4 3 2 1Ma indeks anagramowy 5! - 1 = 119 .

Wszystkie operacje mają łatwe inwersje, więc dekompresja jest prosta.

Jako bonus, przykłady są w formacie bardzo przyjaznym dla J, więc wejście / wyjście dla zdekompresowanych sudokusów jest dokładnie takie, jak podano w przykładach (chociaż wejście do kodera wymaga końca nowej linii).

Skompresowane ciągi dla przypadków testowych:

#p8<!w=C6Cpgi/-+vn)FU]AHr\
"bC]wPv{8ze$l,+jkCPi0,e>-D
2}2EZZB;)WZQF@JChz}~-}}_<
#2Ofs0Mm]).e^raUu^f@sSMWc"
":kkCf2;^U_UDC?I\PC"[*gj|!
#TISE3?d7>oZ_I2.C16Z*gg
,@ CE;zX{.l\xRAc]~@vCw)8R
!oN{|Y6V"C.q<{gq(s?M@O]"]9
VORd2"*T,J;JSh<G=rR*8J1LT
#?bHF:y@oRI8e1Zdl5:BzYO.P.

Python 3, 120 punktów

Ten program wyświetla wszystkie możliwe bloki 3x3 i pamięta, który z nich był rzeczywiście obecny w oryginalnym Sudoku, a następnie łączy wszystkie te liczby w reprezentację base-95. Chociaż jest to bardzo bliskie zakodowania na stałe, kompresuje i dekompresuje przykłady w około 5 sekund na moim komputerze.

import functools

def readSudoku(s):
    values = [int(c) for c in s.split()]
    blocks = []
    for i in range(3):
        for j in range(3):
            block = []
            for k in range(3):
                for l in range(3):
                    block.append(values[i * 27 + k * 9 + j * 3 + l])
            blocks.append(block)
    return blocks

def writeSudoku(blocks):
    text = ""
    for i in range(9):
        for j in range(9):
            text += str(blocks[3 * (i // 3) + (j // 3)][3 * (i % 3) + (j % 3)]) + " "
        text += "\n"
    return text

def toASCII(num):
    chars = "".join(chr(c) for c in range(32, 127))
    if num == 0:
        return chars[0]
    else:
        return (toASCII(num // len(chars)).lstrip(chars[0]) + chars[num % len(chars)])

def toNum(text):
    chars = "".join(chr(c) for c in range(32, 127))
    return sum((len(chars) ** i * chars.index(c) for (i, c) in enumerate(text[::-1])))

def compress(sudoku):
    info = compressInfo(readSudoku(sudoku))
    return toASCII(functools.reduce(lambda old, new: (old[0] + new[0] * old[1], old[1] * new[1]), info, (0, 1))[0])

def compressInfo(sudoku):
    finished = [[0]*9]*9
    indices = [(-1, 0)]*9
    for (index, block) in enumerate(sudoku):
        counter = 0
        actual = -1
        for (location, solution) in enumerate(possibleBlocks(finished, index)):
            counter += 1
            if block == solution:
                actual = location
        if actual == -1:
            print(finished)
            print(block)
            raise ValueError
        finished[index] = block
        indices[index] = (actual, counter)
    return indices

def decompress(text):
    number = toNum(text)
    finished = [[0]*9]*9
    for i in range(9):
        blocks = list(possibleBlocks(finished, i))
        index = number % len(blocks)
        number //= len(blocks)
        finished[i] = blocks[index]
    return writeSudoku(finished)

def possibleBlocks(grid, index):
    horizontals = [grid[i] for i in (3 * (index // 3), 3 * (index // 3) + 1, 3 * (index // 3) + 2)]
    verticals = [grid[i] for i in (index % 3, index % 3 + 3, index % 3 + 6)]
    for i1 in range(1, 10):
        if any((i1 in a[0:3] for a in horizontals)) or\
           any((i1 in a[0::3] for a in verticals)):
            continue
        for i2 in range(1, 10):
            if i2 == i1 or\
               any((i2 in a[0:3] for a in horizontals)) or\
               any((i2 in a[1::3] for a in verticals)):
                continue
            for i3 in range(1, 10):
                if i3 in (i2, i1) or\
                   any((i3 in a[0:3] for a in horizontals)) or\
                   any((i3 in a[2::3] for a in verticals)):
                    continue
                for i4 in range(1, 10):
                    if i4 in (i3, i2, i1) or\
                       any((i4 in a[3:6] for a in horizontals)) or\
                       any((i4 in a[0::3] for a in verticals)):
                        continue
                    for i5 in range(1, 10):
                        if i5 in (i4, i3, i2, i1) or\
                           any((i5 in a[3:6] for a in horizontals)) or\
                           any((i5 in a[1::3] for a in verticals)):
                            continue
                        for i6 in range(1, 10):
                            if i6 in (i5, i4, i3, i2, i1) or\
                               any((i6 in a[3:6] for a in horizontals)) or\
                               any((i6 in a[2::3] for a in verticals)):
                                continue
                            for i7 in range(1, 10):
                                if i7 in (i6, i5, i4, i3, i2, i1) or\
                                   any((i7 in a[6:9] for a in horizontals)) or\
                                   any((i7 in a[0::3] for a in verticals)):
                                    continue
                                for i8 in range(1, 10):
                                    if i8 in (i7, i6, i5, i4, i3, i2, i1) or\
                                       any((i8 in a[6:9] for a in horizontals)) or\
                                       any((i8 in a[1::3] for a in verticals)):
                                        continue
                                    for i9 in range(1, 10):
                                        if i9 in (i8, i7, i6, i5, i4, i3, i2, i1) or\
                                           any((i9 in a[6:9] for a in horizontals)) or\
                                           any((i9 in a[2::3] for a in verticals)):
                                            continue
                                        yield [i1, i2, i3, i4, i5, i6, i7, i8, i9]

Główne funkcje to compress(sudoku)i decompress(text).

Wyjścia:

!%XIjS+]P{'Y
$OPMD&Sw&tlc
$1PdUMZ7K;W*
*=M1Ak9Oj6i\
!SY5:tDJxVo;
!F ]ki%jK>*R
'PXM4J7$s?#%
#9BJZP'%Ggse
*iAH-!9%QolJ
#&L6W6i> Dd6

Python 2.5, 116 punktów

Kod:

emptysud=[[' ']*9 for l in range(9)]

def encconfig(dig,sud):
 conf1=[(sud[i].index(dig),i) for i in range(9)]; out=[]
 for xgroup in range(3):
  a=filter(lambda (x,y): xgroup*3<=x<(xgroup+1)*3, conf1)
  b=[x-xgroup*3 for (x,y) in sorted(a,key = lambda (x,y): y)]
  out.append([[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]].index(b))
 for ygroup in range(3):
  a=filter(lambda (x,y): ygroup*3<=y<(ygroup+1)*3, conf1)
  b=[y-ygroup*3 for (x,y) in sorted(a,key = lambda (x,y): x)]
  out.append([[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]].index(b))
 return sum([out[i]*(6**i) for i in range(6)])

def decconfig(conf,dig,sud=emptysud):
 inp=[]; conf1=[]; sud=[line[:] for line in sud]
 for i in range(6):
  inp.append([[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]][conf%6]); conf/=6
 for groupx in range(3):
  for groupy in range(3):
   conf1.append((groupx*3+inp[groupx][groupy],groupy*3+inp[groupy+3][groupx]))
 for (x,y) in conf1: sud[y][x]=dig
 return sud

def compatible(sud,conf,dig):
 a=reduce(lambda x,y: x+y, sud)
 b=decconfig(conf,dig,sud)
 c=reduce(lambda x,y: x+y, b)
 return a.count(' ')-c.count(' ')==9

def encode(sud):
 k=[encconfig(str(i),sud) for i in range(1,10)]; m=k[0]; p=6**6
 cursud=decconfig(k[0],'1')
 for i in range(1,9):
  t=filter(lambda u: compatible(cursud,u,str(i+1)), range(6**6))
  m=m+p*t.index(k[i]); p*=len(t)
  cursud=decconfig(k[i],str(i+1),cursud)
 return m

def decode(n):
 k=[n%46656]; n/=46656; cursud=decconfig(k[-1],'1')
 for i in range(2,10):
  t=filter(lambda u: compatible(cursud,u,str(i)), range(6**6))
  k.append(n%len(t)); n/=len(t); cursud=decconfig(t[k[-1]],str(i),cursud)
 return cursud

def base95(n):
 out=''
 while n: out+=chr(32+n%95); n/=95
 return out[::-1]

def base10(s): s=s[::-1]; return sum([(ord(s[i])-32)*(95**i) for i in range(len(s))])

import time
t0=time.clock()
for part in file('sudoku.txt','rb+').read().split('\r\n\r\n'):
 sudoku=[line.split(' ') for line in part.split('\r\n')]
 encsud=base95(encode(sudoku)); sud2=decode(base10(encsud))
 print encsud,sud2==sudoku
print time.clock()-t0

Wyniki:

!|/FC,">;&3z
rUH">FLSgT|
)3#m|:&Zxl1c
jh _N@MG/zr
%Iye;U(6(p;0
!21.+KD0//yG
"O\B*O@8,h`y
A$`TUE#rsQu
J}ANCYXX*y5
".u2KV#4K|%a

Bardzo wolno. Uruchomienie i sprawdzenie na mojej maszynie zajęło 517 sekund.

encconfig pobiera tablicę sudoku i cyfrę od 1 do 9, podaje współrzędne xy, w których pojawia się ta cyfra, i wyświetla liczbę w zakresie (6 ** 6), która reprezentuje te współrzędne. („konfiguracja cyfr”)

decconfig to funkcja odwrotna. Zajmuje liczbę z zakresu (6 ** 6), cyfrę i planszę sudoku (domyślnie jest pusta). Wysyła tablicę sudoku nałożoną na konfigurację cyfr. Jeśli jedna z pozycji w konfiguracji cyfr jest już zajęta na wprowadzonej planszy sudoku, cyfra w tej pozycji zostanie zastąpiona nową cyfrą.

Kompatybilny pobiera planszę sudoku i konfigurację cyfr (zdefiniowaną przez conf i dig), nakłada konfigurację cyfr na planszę sudoku i sprawdza konflikty. Następnie zwraca True lub False w zależności od wyniku.

Kod to funkcja kompresji. Pobiera tablicę sudoku i wyświetla liczbę reprezentującą ją. Robi to najpierw kopiując pozycje 1 na pustą tablicę i tworząc listę wszystkich konfiguracji liczby 2, które są kompatybilne z konfiguracją 1 (które nie zajmują żadnego z miejsc zajętych przez 1). Następnie wyszukuje na liście kolejność faktycznej konfiguracji 2 planszy i zapisuje ją, a następnie kopiuje tę konfigurację do nowej planszy, która zawiera teraz tylko 1 i 2. Następnie wyświetla wszystkie konfiguracje liczby 3, które są zgodne z pozycjami 1 i 2, i tak dalej.

dekodowanie jest funkcją odwrotną.

Python 2.5.

C #, 150 bajtów

Skompresowana moc wyjściowa:

KYxnUjIpNe/YDnA
F97LclGuqeTcT2c
i6D1SvMVkS0jPlQ
32FOiIoUHpz5GGs
aAazPo2RJiH+IWQ
CwAA5NIMyNzSt1I
Cc2jOjU1+buCtVM
OgQv3Dz3PqsRvGA
eSxaW3wY5e6NGFc
olQvtpDOUPJXKGw

Jak to działa:

Generuje wszystkie możliwe permutacje 123456789 i zapamiętuje je. Następnie porównuje permutacje z wierszami w sudoku. Po znalezieniu pasującej permutacji dla danego wiersza zapamiętuje indeks tej permutacji. Po każdym wierszu usunie wszystkie permutacje, w których jest co najmniej jeden znak w tej samej pozycji, co bieżący wiersz. Dzięki temu każda liczba jest unikalna w kolumnie. Następnie usuwa wszystkie permutacje, które nie działają już według kryteriów pudełkowych. Ponieważ ostatni wiersz jest trywialny, generuje 8 liczb. Sprawdziłem, jaka byłaby maksymalna wartość każdej z tych liczb, i wygenerowałem maskę cyfr dla każdej pozycji tych liczb. {6, 5, 3, 5, 3, 1, 2, 1, 1}. Pierwszy jest oczywiście najdłuższy z 362880 permutacjami. Korzystając z maski cyfr, tworzę BigInteger z wiodącą 1, aby miała długość 28 cyfr. Daje to w sumie 11 bajtów. Następnie bajty te są konwertowane na base64. Aby zapisać jeden znak, usuń znak = na końcu.

Rekonstrukcja działa podobnie.

Odtwarza BigInteger z ciągu base64, a następnie zamienia go ponownie w ciąg znaków i dzieli go ponownie za pomocą wspomnianej maski liczenia cyfr. Te ciągi są analizowane z powrotem do indeksów.

Następnie algorytm robi prawie to samo, zamiast znaleźć wiersz w permutacjach, po prostu używa indeksu, aby uzyskać wiersz, reszta działa tak samo.

Prawdopodobnie byłoby to trochę lepsze, aby naprawdę użyć 94 możliwych charachterów zamiast tylko 64, ale brakuje mi mózgów, aby to zrobić.

Źródło : Kopiowanie i wklejanie, aby działało z 10 przykładami. .dotNet-Fiddle mówi mi, że przekracza to limit pamięci, więc musisz uruchomić go na komputerze, aby wysłać SMS-a.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;

public class Programm
{
    public static void Main(string[] args)
    {
        string[] input = new[] {
            "973581426526473198184296753247865319398124675651739842819342567765918234432657981",
            "724865193169243875385197246896724351273951684451386927542639718618572439937418562", 
            "157682349432519687698347251825476193713928465964135728541293876289761534376854912", 
            "835416927296857431417293658569134782123678549748529163652781394981345276374962815", 
            "628451793594732681713689542247315869961827354385964217156243978439578126872196435", 
            "123456789456789123789123456214365897365897214897214365531648972648972531972531648", 
            "145792836376584192298361754731928645859647321462135987624873519587419263913256478",
            "527416938864329157139578642291854376348697521675132489712945863483261795956783214", 
            "246713985185496732937825146678542391493168257512379468824957613759631824361284579",
            "861294573475318692392567814236459781154783269987621345529176438648932157713845926" };

        string[] permutations = GetPermutations();
        foreach (string sudoku in input)
        {

            int[] indices = _compressSudoku(sudoku, permutations).ToArray();
            string compressedRepresentation = _toCompressedRepresentation(indices);

            Console.WriteLine(compressedRepresentation);
            indices = _fromCompressedRepresentation(compressedRepresentation);
            string decompressedSudoku = _decompressSudoku(indices, permutations);

            if (decompressedSudoku != sudoku)
                throw new Exception();
        }
        Console.ReadKey();
    }

    static int[] _digitMask = new int[] { 6, 5, 3, 5, 3, 1, 2, 1, 1 };

    private static int[] _fromCompressedRepresentation(string compressedRepresentation)
    {
        BigInteger big = new BigInteger(Convert.FromBase64String(compressedRepresentation + "="));

        string stringValue = big.ToString().Substring(1);

        List<int> indexes = new List<int>();
        int i = 0;
        while (stringValue.Length > 0)
        {
            int length = _digitMask[i++];
            string current = stringValue.Substring(0, length);
            stringValue = stringValue.Substring(length);
            indexes.Add(int.Parse(current));
        }
        return indexes.ToArray(); ;
    }

    private static string _toCompressedRepresentation(int[] indices)
    {
        StringBuilder builder = new StringBuilder("1");
        int i = 0;
        foreach (int index in indices)
        {
            string mask = "{0:D" + _digitMask[i++].ToString() + "}";
            builder.AppendFormat(mask, index);
        }

        string base64 = Convert.ToBase64String(BigInteger.Parse(builder.ToString()).ToByteArray());
        return base64.Substring(0, base64.Length - 1); // remove the = at the end.
    }

    private static IEnumerable<int> _compressSudoku(string input, string[] remainingPermutations)
    {
        string[] localRemainingPermutations = null;
        List<HashSet<char>> localUsed = null;
        for (int i = 0; i < 8; i++)
        {
            string currentRow = _getCurrentRow(input, i);
            if (i % 3 == 0)
            {
                localRemainingPermutations = remainingPermutations;
                localUsed = _initLocalUsed();
            }

            int index = 0;
            foreach (string permutation in localRemainingPermutations)
            {
                if (permutation == currentRow)
                {
                    yield return index;
                    break;
                }
                index++;
            }
            remainingPermutations = remainingPermutations.Where(permutation => _isStillValidPermutation(currentRow, permutation)).ToArray();
            if (i % 3 < 2)
            {
                for (int j = 0; j < 9; j++)
                    localUsed[j / 3].Add(currentRow[j]);
                localRemainingPermutations = localRemainingPermutations.Where(permutation => _isStillValidLocalPermutation(permutation, localUsed)).ToArray();
            }
        }
    }

    private static string _decompressSudoku(int[] indices, string[] remainingPermutations)
    {
        StringBuilder result = new StringBuilder();

        string[] localRemainingPermutations = null;
        List<HashSet<char>> localUsed = null;
        for (int i = 0; i < 9; i++)
        {
            if (i % 3 == 0)
            {
                localRemainingPermutations = remainingPermutations;
                localUsed = _initLocalUsed();
            }
            string currentRow = localRemainingPermutations[i < indices.Length ? indices[i] : 0];
            result.Append(currentRow);

            remainingPermutations = remainingPermutations.Where(permutation => _isStillValidPermutation(currentRow, permutation)).ToArray();
            if (i % 3 < 2)
            {
                for (int j = 0; j < 9; j++)
                    localUsed[j / 3].Add(currentRow[j]);
                localRemainingPermutations = localRemainingPermutations.Where(permutation => _isStillValidLocalPermutation(permutation, localUsed)).ToArray();
            }
        }
        return result.ToString();
    }

    private static string _getCurrentRow(string input, int i)
    {
        return new string(input.Skip(i * 9).Take(9).ToArray());
    }

    private static List<HashSet<char>> _initLocalUsed()
    {
        return new List<HashSet<char>> { new HashSet<char>(), new HashSet<char>(), new HashSet<char>() };
    }

    private static bool _isStillValidLocalPermutation(string permutation, List<HashSet<char>> localUsed)
    {
        for (int i = 0; i < 9; i++)
        {
            if (localUsed[i / 3].Contains(permutation[i]))
                return false;
        }
        return true;
    }

    private static bool _isStillValidPermutation(string currentRow, string permutation)
    {
        return permutation.Select((c, j) => c != currentRow[j]).All(b => b);
    }

    static string[] GetPermutations(char[] chars = null)
    {
        if (chars == null)
            chars = new[] { '1', '2', '3', '4', '5', '6', '7', '8', '9' };
        if (chars.Length == 2)
            return new[] { new String(chars), new String(chars.Reverse().ToArray()) };
        return chars.SelectMany(c => GetPermutations(chars.Where(sc => sc != c).ToArray()), (c, s) => c + s).ToArray();
    }
}

Perl - 290 znaków = 290 punktów

Ten program nie używa twardego kodowania i niezawodnie kompresuje siatkę dokładnie w 29 znakach (teoretycznie można byłoby znaleźć kilka mniejszych).

Oto jak to działa:

• Najpierw przekonwertuj tablicę 9 x 9 na 60 liczb. Można to zrobić jako ostatnią kolumnę, ostatni wiersz i ostatni kwadrat każdej komórki 3 x 3 można upuścić.

• Następnie przekonwertuj za pomocą biginta na jedną liczbę całkowitą, używając 9 ^ 60 elementów.

• Następnie przekonwertuj bigint na bazę 95.

Sprężarka i dekompresor:

#!/usr/bin/perl

use strict;
use warnings;
use Getopt::Long;
use bigint;

sub compress
{
    my @grid;
    my @nums;
    while (<>)
    {
        push @grid, [split];
    }

    # encode into 60 numbers omitting last from each row, column and 3 x 3 square
    my $i;
    my $j;
    for ($i=0; $i<=7; $i++)
    {
        for ($j=0; $j<=7; $j++)
        {
            push @nums, $grid[$i][$j] if (($i % 3 !=2 ) || ($j % 3 !=2));
        }
    }

    # encode into a big int
    my $code = 0;
    foreach my $n (@nums)
    {
        $code = $code * 9 + ($n-1);
    }

    # print in base 95
    my $out="";
    while ($code)
    {
        my $digit = $code % 95;
        $out = chr($digit+32).$out;
        $code -= $digit;
        $code /= 95;
    }

    print "$out";
}

sub decompress
{
    my @grid;
    my @nums;
    my $code = 0;

    # Read from base 95 into bigint
    while (<>)
    {
        chomp;
        foreach my $char (split (//, $_))
        {
            my $c =ord($char)-32;
            $code*=95;
            $code+=$c;
        }
    }

    # convert back to 60 numbers
    for (my $n = 0; $n<60; $n++)
    {
        my $d = $code % 9;
        $code -= $d;
        $code/=9;
        unshift @nums, $d+1;
    }

    # print filling in last column, row and 3 x 3 square
    for (my $i=0; $i<=8; $i++)
    {
        for (my $j=0; $j<=8; $j++)
        {
            if ($j == 8)
            {
                my $tot = 0;
                for (my $jj = 0; $jj<=7; $jj++)
                {
                    $tot += $grid[$i][$jj];
                }
                $grid[$i][$j]=45-$tot;
            }
            elsif ($i == 8)
            {
                my $tot = 0;
                for (my $ii = 0; $ii<=7; $ii++)
                {
                    $tot += $grid[$ii][$j];
                }
                $grid[$i][$j]=45-$tot;
            }
            elsif (($i % 3 == 2 ) && ($j % 3 == 2))
            {
                my $tot = 0;
                for (my $ii = $i-2; $ii<=$i; $ii++)
                {
                    for (my $jj = $j-2; $jj<=$j; $jj++)
                    {
                        next if (($ii % 3 == 2 ) && ($jj % 3 == 2));
                        $tot += $grid[$ii][$jj];
                    }
                }
                $grid[$i][$j]=45-$tot;
            }
            else
            {
                $grid[$i][$j] = shift @nums;
            }

            print $grid[$i][$j].(($j==8)?"":" ");
        }
        print "\n";
    }
}

my $decompress;
GetOptions ("d|decompress" => \$decompress);

if ($decompress)
{
    decompress;
}
else
{
    compress;
}

PHP, 214

<?php
// checks each row/col/block and removes impossible candidates
function reduce($cand){
    do{
        $old = $cand;
        for($r = 0; $r < 9; ++$r){
        for($c = 0; $c < 9; ++$c){
            if(count($cand[$r][$c]) == 1){ // if filled in
                // remove values from row and col and block
                $remove = $cand[$r][$c];
                for($i = 0; $i < 9; ++$i){
                    $cand[$r][$i] = array_diff($cand[$r][$i],$remove);
                    $cand[$i][$c] = array_diff($cand[$i][$c],$remove);
                    $br = floor($r/3)*3+$i/3;
                    $bc = floor($c/3)*3+$i%3;
                    $cand[$br][$bc] = array_diff($cand[$br][$bc],$remove);
                }
                $cand[$r][$c] = $remove;
            }
        }}
    }while($old != $cand);
    return $cand;
}

// checks candidate list for completion
function done($cand){
    for($r = 0; $r < 9; ++$r){
    for($c = 0; $c < 9; ++$c){
        if(count($cand[$r][$c]) != 1)
            return false;
    }}
    return true;
}

// board format: [[1,2,0,3,..],[..],..], $b[$row][$col]
function solve($board){
    $cand = [[],[],[],[],[],[],[],[],[]];
    for($r = 0; $r < 9; ++$r){
    for($c = 0; $c < 9; ++$c){
        if($board[$r][$c]){ // if filled in
            $cand[$r][$c] = [$board[$r][$c]];
        }else{
            $cand[$r][$c] = range(1, 9);
        }
    }}
    $cand = reduce($cand);

    if(done($cand))  // goto not really necessary
        goto end;    // but it feels good to use it 
    else return false;

    end:
    // back to board format
    $b = [];
    for($r = 0; $r < 9; ++$r){
        $b[$r] = [];
        for($c = 0; $c < 9; ++$c){
            if(count($cand[$r][$c]) == 1)
                $b[$r][$c] = array_pop($cand[$r][$c]);
            else 
                $b[$r][$c] = 0;
        }
    }
    return $b;
}

function add_zeros($board, $ind){
    for($r = 0; $r < 9; ++$r){
    for($c = 0; $c < 9; ++$c){
        $R = ($r + (int)($ind/9)) % 9;
        $C = ($c + (int)($ind%9)) % 9;
        if($board[$R][$C]){
            $tmp = $board[$R][$C];
            $board[$R][$C] = 0;
            if(!solve($board))
                $board[$R][$C] = $tmp;
        }   
    }}
    return $board;
}

function base95($str, $b, $z){
    $tmp = gmp_init($str, $b); $zero = gmp_init(0); $gmp95 = gmp_init(95);
    $out = '';
    while(gmp_cmp($tmp, $zero) > 0){
        $arr = gmp_div_qr($tmp, $gmp95);
        $tmp = $arr[0];
        $out .= chr(32+gmp_intval($arr[1]));
    }
    $out = chr((32+($z << 2))|($b - 10)) . strrev($out);
    return $out;
}

function encode($board, $ind){
    // remove last row+col
    $board[8] = [0,0,0,0,0,0,0,0,0];
    foreach($board as &$j) $j[8] = 0;

    // remove bottom corner of each box
    $board[2][2] = $board[2][5] = $board[5][2] = $board[5][5] = 0;

    $board = add_zeros($board, $ind);

    $str = '';$z=0;
    for($r = 0; $r < 8; ++$r){
        for($c = 0; $c < 8; ++$c){
            if(($r==2||$r==5)&&($c==2||$c==5)) continue;
            if($str == '' && !$board[$r][$c]) ++$z;
            else $str .= $board[$r][$c];
        }
    }

    $b10 = base95(rtrim($str,'0'), 10, $z);
    $b11 = base95(rtrim(str_replace(['00'],['A'],$str),'0'), 11, $z);
    $b12 = base95(rtrim(str_replace(['000','00'],['B','A'],$str),'0'), 12, $z);

    $l10 = strlen($b10);
    $l11 = strlen($b11);
    $l12 = strlen($b12);
    var_dump($z);
    if($l10 < $l11)
        if($l10 < $l12)
            return $b10;
        else 
            return $b12;
    else
        if($l11 < $l12)
            return $b11;
        else 
            return $b12;    
}

function decode($str){
    $fc = ord($str[0]);
    $base = 10 + ($fc & 3);
    $z = ($fc - 32) >> 2;

    $tmp = gmp_init(0);
    $zero = gmp_init(0); $gmp95 = gmp_init(95);
    while(strlen($str = substr($str, 1))){
        $tmp = gmp_mul($tmp, $gmp95);
        $tmp = gmp_add($tmp, gmp_init(ord($str[0])-32));
    }
    $str = gmp_strval($tmp, $base);
    $expanded = str_repeat('0', $z) . str_replace(['a','b'],['00','000'],$str) . str_repeat('0', 81);

    $board = [];
    $ind = 0;
    for($i = 0; $i < 8; ++$i){
        $board[$i] = [];
        for($j = 0; $j < 8; ++$j){
            if(($i == 2 || $i == 5) && ($j == 2 || $j == 5)) 
                $board[$i][$j] = 0;
            else
                $board[$i][$j] = (int)$expanded[$ind++];
        }
        $board[$i][8] = 0;
    }
    $board[8] = [0,0,0,0,0,0,0,0,0];
    return solve($board);
}

function printBoard($board){
    for($i = 0; $i < 9; ++$i){
        echo implode(' ', $board[$i]) . PHP_EOL;
    }
    flush();
}

function readBoard(){
    $board = [];
    for($r = 0; $r < 9; ++$r){
        $board[$r] = fscanf(STDIN, "%d%d%d%d%d%d%d%d%d");
    }
    return $board;
}
if(isset($argv[1])){
    if($argv[1] === 'enc'){
        $board = readBoard();
        $bests = ''; $bestl = 999;
        for($i = 0; $i < 71; ++$i){
            $str = encode($board, $i);
            $len = strlen($str);
            if($len < $bestl){
                $bestl = $len;
                $bests = $str;
            }
        }
        echo $bests . PHP_EOL;
    }else if($argv[1] === 'dec'){
        echo printBoard(decode(trim(fgets(STDIN))));
    }
}else{
    echo "Missing argument. Use `{$argv[0]} [enc|dec]`.\n";
}

To rozwiązanie najpierw usuwa prawą kolumnę i dolny rząd, a także prawy dolny róg każdego bloku 3x3. Następnie próbuje wyczyścić komórkę. Jeśli istnieje proste rozwiązanie, komórka pozostaje pusta.

Następnie siatka sudoku jest formatowana w ciąg znaków, od lewej do prawej i od góry do dołu, z wyłączeniem prawej kolumny, dolnego rzędu i prawego dolnego rogu. Zera wiodące są liczone (niech tak będziez ) i usuwane. Zera końcowe są również usuwane.

Łańcuch jest sformatowany w postaci liczby całkowitej 10, 11 lub 12 (niech ta podstawa będzie b), Areprezentując dwa zera iB trzy.

Jest to konwertowane na liczbę całkowitą base-95 i poprzedzone cyfrą reprezentującą base-95 z << 2 | (b - 10).

Wezwanie php sudoku-compress.php encdo kodowania i php sudoku-compress.php decdekodowania. Koder przyjmuje format podany w pytaniu, z obowiązkowym końcowym znakiem nowej linii.

Wyjścia testowe:

R'Ngxgi#Hu~+cR)0nE)+
Veu-b454j|:tRm(b-Xk'I
V.{mi;*6-/9Ufu[~GE"e>
F/YgX]PeyeKX5=M_+,z+Z
R&3mEHyZ6sSF'-$L<:VmX
"#b'npsIv0%L,t0yr^a.+'&
UNjx*#~I/siBGck7u9eaC%
Z!SuM^f{e<ji@F&hP-S<
*0:43tD r;=x8|&I0/k[&%
B1Mm-dx@G}[2lZId/-'h{zU

Java, 330 punktów

Zanim wyśmiewam się z tak wysokiego wyniku, pozwólcie, że wyjaśnię, że próbowałem rozwiązać ten problem w inny sposób, wiedząc, że prawdopodobnie nie będzie on tak optymalny, jak niektóre lepsze odpowiedzi tutaj. Byłem mniej więcej ciekawy, czy uda mi się zbliżyć co ku mojemu zaskoczeniu nie zdawałem sobie sprawy, o ile gorzej by się okazało. Oto podsumowanie mojego podejścia:

1. Opracuj algorytm rozwiązywania zagadek sudoku.

2. Opracuj mieszające się algo, które nadal będzie możliwe do rozwiązania. Robi to nieco losowo, jednocześnie usuwając wskazówki, które można trywialnie ustalić przed ręką. Mogłem rzetelnie uzyskać około 22 wskazówek, zanim zajęło to zdecydowanie zbyt dużo czasu.

3. Raz zaszyfrowana łamigłówka może być reprezentowana przez trójkę liczb całkowitych jednocyfrowych dla każdej wskazówki, w moim przypadku 22 trojaczki po 3. Pomyślałem, że jeśli mogę połączyć je w jedną 66 cyfr, to kodowanie kodu base95 to mam coś, co może łatwo dekodować.

Zakodowany ciąg okazał się dłuższy, niż się spodziewałem, na ogół około 33 znaków. W tym momencie wypróbowałem alternatywny sposób niż użycie Java BigInteger, w którym utworzyłem dużą liczbę z 81-bitowej maski reprezentującej 81 komórek siatki, gdzie 1 oznacza wskazówkę dla tej komórki. Następnie połączyłem tę maskę bitową z 4-bitowymi reprezentacjami każdej wartości komórki w kolejności sekwencyjnej, zaokrąglając w górę do bajtów i stwierdziłem, że z grubsza otrzymałem taką samą długość łańcucha po kodowaniu base95.

Zasadniczo więc publikuję swój kod na wypadek, gdyby ktoś był zainteresowany innym podejściem, które nie wyszło tak dobrze.

Class Puzz

public class Puzz {

    enum By {
        Row, Column, Block
    }

    static final List<Integer> NUMBERS = Arrays.asList(new Integer[] { 1, 2, 3,
            4, 5, 6, 7, 8, 9 });

    List<Square> entries = new ArrayList<Square>();
    HashMap<Integer, List<Square>> squaresByRow = new HashMap<Integer, List<Square>>();
    HashMap<Integer, List<Square>> squaresByColumn = new HashMap<Integer, List<Square>>();
    HashMap<Integer, List<Square>> squaresByBlock = new HashMap<Integer, List<Square>>();

    public Puzz(int[][] data) {

        // Create squares put them in squares by row hashtable
        for (int r = 0; r < 9; r++) {
            List<Square> squaresInRow = new ArrayList<Square>();
            for (int c = 0; c < 9; c++) {
                Square square = new Square(r, c, data[r][c], this);
                entries.add(square);
                squaresInRow.add(square);
            }
            squaresByRow.put(r, squaresInRow);
        }

        // Put squares in column hash table
        for (int c = 0; c < 9; c++) {
            List<Square> squaresInColumn = new ArrayList<Square>();
            for (int r = 0; r < 9; r++) {
                squaresInColumn.add(squaresByRow.get(r).get(c));
            }
            squaresByColumn.put(c, squaresInColumn);
        }

        // Put squares in block hash table
        for (int i = 1; i < 10; i++) {
            squaresByBlock.put(i, new ArrayList<Square>());
        }
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                int block = getBlock(r, c);
                squaresByBlock.get(block).add(get(r, c));
            }
        }

        // Discover the possibilities
        updatePossibilities();
    }

    public void updatePossibilities() {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                Square theSquare = get(r, c);
                if (theSquare.value != 0) {
                    theSquare.possibilities.removeAll(NUMBERS);
                    continue;
                } else {
                    theSquare.possibilities.addAll(NUMBERS);
                }
                int block = getBlock(r, c);
                HashSet<Square> squares = new HashSet<Square>();
                squares.addAll(squaresByRow.get(r));
                squares.addAll(squaresByColumn.get(c));
                squares.addAll(squaresByBlock.get(block));
                for (Square s : squares) {
                    if (s == theSquare)
                        continue;

                    theSquare.possibilities.remove(s.value);
                }
            }
        }
    }

    public int getValue(int row, int column) {
        return squaresByRow.get(row).get(column).value;
    }

    public Square get(int row, int column) {
        return squaresByRow.get(row).get(column);
    }

    public boolean set(int row, int column, int value) {
        if (value == 0) {
            squaresByRow.get(row).get(column).value = 0;
            updatePossibilities();
            return true;
        }

        if (isValid(row, column, value)) {
            squaresByRow.get(row).get(column).value = value;
            updatePossibilities();
            return true;
        } else {
            return false;
        }
    }

    public boolean isValidSubset(By subset, int row, int column, int value) {
        List<Dubs> dubss = new ArrayList<Dubs>();
        List<Trips> tripss = new ArrayList<Trips>();
        Square theSquare = get(row, column);
        int block = getBlock(row, column);
        List<Square> squares = new ArrayList<Square>();
        switch (subset) {
        case Row:
            squares.addAll(squaresByRow.get(row));
            break;
        case Column:
            squares.addAll(squaresByColumn.get(column));
            break;
        default:
            squares.addAll(squaresByBlock.get(block));
            break;
        }

        for (Square r : squares) {
            if (r == theSquare)
                continue;
            // if any of the impacted squares have this value then it is not a
            // valid value
            if (r.value == value)
                return false;

            if (r.possibilities.size() == 3) {
                List<Integer> poss = new ArrayList<Integer>(r.possibilities);
                tripss.add(new Trips(poss.get(0), poss.get(1), poss.get(2),
                        r.row, r.col));
            }

            if (r.possibilities.size() == 2) {
                List<Integer> poss = new ArrayList<Integer>(r.possibilities);
                dubss.add(new Dubs(poss.get(0), poss.get(1), r.row, r.col));
            }
        }

        // Find the trips and rule out the value if a triplet exists in squares
        List<Trips> tripsCopy = new ArrayList<Trips>(tripss);
        for (Trips trips : tripsCopy) {
            int countOfOccurrences = 0;
            for (Trips tr : tripss) {
                if (tr.equals(trips) && !(tr.row == row && tr.col == column))
                    countOfOccurrences++;
            }

            for (Dubs dubs : dubss) {
                if (trips.containedWithin(dubs)
                        && !(dubs.row == row && dubs.col == column))
                    countOfOccurrences++;
            }

            if (countOfOccurrences == 3 && trips.containedWithin(value))
                return false;
        }

        // Find the dubs and rule out the value if a double exists in squares
        List<Dubs> dubsCopy = new ArrayList<Dubs>(dubss);
        for (Dubs dubs : dubsCopy) {
            int countOfOccurrences = 0;
            for (Dubs du : dubss) {
                // Count occurrences of Dubs that are not the tested square
                if (du.equals(dubs) && !(du.row == row && du.col == column))
                    countOfOccurrences++;
            }

            if (countOfOccurrences == 2 && dubs.containedWithin(value))
                return false;
        }

        return true;
    }

    public boolean isValid(int row, int column, int value) {

        return isValidSubset(By.Row, row, column, value)
                && isValidSubset(By.Column, row, column, value)
                && isValidSubset(By.Block, row, column, value);
    }

    public int getBlock(int row, int column) {
        int blockRow = (int) Math.floor(row / 3);
        int columnRow = (int) Math.floor(column / 3) + 1;
        return (blockRow * 3) + columnRow;
    }

    public Puzz solve(Puzz arg, boolean top) throws Exception {
        // Make an original copy of the array
        Puzz p = (Puzz) arg.clone();
        for (int i = 1; i < 10; i++) {
            for (Square s : p.squaresByBlock.get(i)) {
                if (s.value == 0) {
                    for (Integer number : NUMBERS) {
                        if (p.set(s.row, s.col, number)) {
                            // System.out.println(p);
                            Puzz solved = solve(p, false);
                            if (solved != null)
                                return solved;
                        }
                    }
                    // no numbers fit here, return null and backtrack
                    p.set(s.row, s.col, 0);
                    return null;
                }
            }
        }

        // Check for remaining 0's
        for (Square s : p.entries) {
            if (s.value == 0)
                return null;
        }
        return p;
    }

    public Puzz scramble(int clues) throws Exception {
        Puzz p = (Puzz) clone();
        Random rand = new Random();
        int removed = 0;

        //Remove the last row, it is a freebie
        int toRemove = 81 - clues - 15;
        for (int c = 0; c < 9; c++) {
            p.set(8, c, 0);
        }
        p.set(0, 0, 0);
        p.set(0, 3, 0);
        p.set(0, 6, 0);
        p.set(3, 0, 0);
        p.set(3, 3, 0);
        p.set(3, 6, 0);

        // Keeping track of this because randomly removing squares can potentially create an 
        // unsolvable situation
        HashSet<Square> alreadyTried = new HashSet<Square>();
        while (removed < toRemove) {
            if (alreadyTried.size() >= ((toRemove + clues) - removed)) {
                // Start over
                removed = 0;
                alreadyTried = new HashSet<Square>();
                p = (Puzz)clone();
                for (int c = 0; c < 9; c++) {
                    p.set(8, c, 0);
                }
                p.set(0, 0, 0);
                p.set(0, 3, 0);
                p.set(0, 6, 0);
                p.set(3, 0, 0);
                p.set(3, 3, 0);
                p.set(3, 6, 0);
            }
            int randX = rand.nextInt((7) + 1);
            int randY = rand.nextInt((8) + 1);
            int existingValue = p.getValue(randX, randY);
            if (existingValue != 0) {
                p.set(randX, randY, 0);
                // confirm it is still solvable after removing this item
                Puzz psol = solve(p, true);
                if (psol != null && psol.equals(this)) {
                    removed++;
                    alreadyTried = new HashSet<Square>();
                    System.out.println("Clues Remaining: " + (81 - 15 - removed));
                } else {
                    // otherwise set it back to what it was and try again
                    p.set(randX, randY, existingValue);
                    Square s = new Square(randX, randY, existingValue, p);
                    alreadyTried.add(s);
                }
            }

        }
        p.updatePossibilities();
        return p;
    }

    public static String encode(Puzz p) { // Remove all zero'ed items
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < 9; i++) {
            for (Square s : p.squaresByRow.get(i)) {
                if (s.value == 0)
                    continue;
                sb.append(s.row).append(s.col).append(s.value);
            }
        }

        // number mod 95 gives lowest digit, subtract that from original number
        BigInteger num = new BigInteger(sb.toString());
        byte[] numBytes = num.toByteArray();

        StringBuffer retVal = new StringBuffer();
        while (num.compareTo(BigInteger.ZERO) > 0) {
            int modu = num.mod(new BigInteger("95")).intValue();
            retVal.append((char) (modu + 32));
            num = num.subtract(new BigInteger("" + modu));
            num = num.divide(new BigInteger("95"));
        }
        return retVal.toString();
    }


    @Override
    public boolean equals(Object arg0) {
        if (arg0 == null || !(arg0 instanceof Puzz))
            return false;

        Puzz p = (Puzz) arg0;
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                int val1 = getValue(r, c);
                int val2 = p.getValue(r, c);
                if (val1 != val2)
                    return false;
            }
        }
        return true;
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        int[][] data = new int[9][9];
        for (Square square : entries) {
            data[square.row][square.col] = square.value;
        }

        return new Puzz(data);
    }

    @Override
    public String toString() {
        if (entries == null)
            return "";
        StringBuffer sb = new StringBuffer();
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                sb.append(getValue(r, c)).append(' ');
            }
            sb.append('\n');
        }
        return sb.toString();
    }

}

class Square {

    public Square(int row, int col, Puzz p) {
        this.row = row;
        this.col = col;
        this.p = p;
    }

    public Square(int row, int col, int value, Puzz p) {
        this(row, col, p);
        this.value = value;
    }

    int row;
    int col;
    int value;
    HashSet<Integer> possibilities = new HashSet<Integer>(Puzz.NUMBERS);
    Puzz p;

    @Override
    protected Object clone() throws CloneNotSupportedException {
        Square s = new Square(row, col, value, p);
        s.possibilities = new HashSet<Integer>();
        for (Integer val : possibilities) {
            s.possibilities.add(new Integer(val));
        }
        return s;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Square))
            return false;

        Square s = (Square) obj;
        return row == s.row && col == s.col && value == s.value
                && p.equals(s.p);
    }

    @Override
    public int hashCode() {
        return row ^ col ^ value ^ p.hashCode();
    }
}

class Dubs {
    int p1;
    int p2;

    int row, col;

    public Dubs(int p1, int p2) {
        this.p1 = p1;
        this.p2 = p2;
    }

    public Dubs(int p1, int p2, int row, int col) {
        this(p1, p2);
        this.row = row;
        this.col = col;
    }

    public boolean containedWithin(int value) {
        return (p1 == value || p2 == value);
    }

    @Override
    public boolean equals(Object arg0) {
        if (!(arg0 instanceof Dubs))
            return false;

        Dubs d = (Dubs) arg0;
        return (this.p1 == d.p1 || this.p1 == d.p2)
                && (this.p2 == d.p1 || this.p2 == d.p2);
    }
}

class Trips {
    int p1;
    int p2;
    int p3;
    int row, col;

    public Trips(int p1, int p2) {
        this.p1 = p1;
        this.p2 = p2;
    }

    public Trips(int p1, int p2, int p3) {
        this(p1, p2);
        this.p3 = p3;
    }

    public Trips(int p1, int p2, int p3, int row, int col) {
        this(p1, p2, p3);
        this.row = row;
        this.col = col;
    }

    public boolean containedWithin(int value) {
        return (p1 == value || p2 == value || p3 == value);
    }

    public boolean containedWithin(Dubs d) {
        return (d.p1 == p1 || d.p1 == p2 || d.p1 == p3)
                && (d.p2 == p1 || d.p2 == p2 || d.p2 == p3);
    }

    public boolean equals(Object arg0) {
        if (!(arg0 instanceof Trips))
            return false;

        Trips t = (Trips) arg0;
        return (this.p1 == t.p1 || this.p1 == t.p2 || this.p1 == t.p3)
                && (this.p2 == t.p1 || this.p2 == t.p2 || this.p2 == t.p3)
                && (this.p3 == t.p1 || this.p3 == t.p2 || this.p3 == t.p3);
    }
}

Mój przypadek testowy

public class TestCompression extends TestCase {

    public static int[][] test1 = new int[][] {
            new int[] { 9, 7, 3, 5, 8, 1, 4, 2, 6 },
            new int[] { 5, 2, 6, 4, 7, 3, 1, 9, 8 },
            new int[] { 1, 8, 4, 2, 9, 6, 7, 5, 3 },
            new int[] { 2, 4, 7, 8, 6, 5, 3, 1, 9 },
            new int[] { 3, 9, 8, 1, 2, 4, 6, 7, 5 },
            new int[] { 6, 5, 1, 7, 3, 9, 8, 4, 2 },
            new int[] { 8, 1, 9, 3, 4, 2, 5, 6, 7 },
            new int[] { 7, 6, 5, 9, 1, 8, 2, 3, 4 },
            new int[] { 4, 3, 2, 6, 5, 7, 9, 8, 1 } };
    public static int[][] test2 = new int[][] {
            new int[] { 7, 2, 4, 8, 6, 5, 1, 9, 3 },
            new int[] { 1, 6, 9, 2, 4, 3, 8, 7, 5 },
            new int[] { 3, 8, 5, 1, 9, 7, 2, 4, 6 },
            new int[] { 8, 9, 6, 7, 2, 4, 3, 5, 1 },
            new int[] { 2, 7, 3, 9, 5, 1, 6, 8, 4 },
            new int[] { 4, 5, 1, 3, 8, 6, 9, 2, 7 },
            new int[] { 5, 4, 2, 6, 3, 9, 7, 1, 8 },
            new int[] { 6, 1, 8, 5, 7, 2, 4, 3, 9 },
            new int[] { 9, 3, 7, 4, 1, 8, 5, 6, 2 } };
    public static int[][] test3 = new int[][] {
            new int[] { 1, 5, 7, 6, 8, 2, 3, 4, 9 },
            new int[] { 4, 3, 2, 5, 1, 9, 6, 8, 7 },
            new int[] { 6, 9, 8, 3, 4, 7, 2, 5, 1 },
            new int[] { 8, 2, 5, 4, 7, 6, 1, 9, 3 },
            new int[] { 7, 1, 3, 9, 2, 8, 4, 6, 5 },
            new int[] { 9, 6, 4, 1, 3, 5, 7, 2, 8 },
            new int[] { 5, 4, 1, 2, 9, 3, 8, 7, 6 },
            new int[] { 2, 8, 9, 7, 6, 1, 5, 3, 4 },
            new int[] { 3, 7, 6, 8, 5, 4, 9, 1, 2 } };
    public static int[][] test4 = new int[][] {
            new int[] { 8, 3, 5, 4, 1, 6, 9, 2, 7 },
            new int[] { 2, 9, 6, 8, 5, 7, 4, 3, 1 },
            new int[] { 4, 1, 7, 2, 9, 3, 6, 5, 8 },
            new int[] { 5, 6, 9, 1, 3, 4, 7, 8, 2 },
            new int[] { 1, 2, 3, 6, 7, 8, 5, 4, 9 },
            new int[] { 7, 4, 8, 5, 2, 9, 1, 6, 3 },
            new int[] { 6, 5, 2, 7, 8, 1, 3, 9, 4 },
            new int[] { 9, 8, 1, 3, 4, 5, 2, 7, 6 },
            new int[] { 3, 7, 4, 9, 6, 2, 8, 1, 5 } };
    public static int[][] test5 = new int[][] {
            new int[] { 6, 2, 8, 4, 5, 1, 7, 9, 3 },
            new int[] { 5, 9, 4, 7, 3, 2, 6, 8, 1 },
            new int[] { 7, 1, 3, 6, 8, 9, 5, 4, 2 },
            new int[] { 2, 4, 7, 3, 1, 5, 8, 6, 9 },
            new int[] { 9, 6, 1, 8, 2, 7, 3, 5, 4 },
            new int[] { 3, 8, 5, 9, 6, 4, 2, 1, 7 },
            new int[] { 1, 5, 6, 2, 4, 3, 9, 7, 8 },
            new int[] { 4, 3, 9, 5, 7, 8, 1, 2, 6 },
            new int[] { 8, 7, 2, 1, 9, 6, 4, 3, 5 } };
    public static int[][] test6 = new int[][] {
            new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
            new int[] { 4, 5, 6, 7, 8, 9, 1, 2, 3 },
            new int[] { 7, 8, 9, 1, 2, 3, 4, 5, 6 },
            new int[] { 2, 1, 4, 3, 6, 5, 8, 9, 7 },
            new int[] { 3, 6, 5, 8, 9, 7, 2, 1, 4 },
            new int[] { 8, 9, 7, 2, 1, 4, 3, 6, 5 },
            new int[] { 5, 3, 1, 6, 4, 8, 9, 7, 2 },
            new int[] { 6, 4, 8, 9, 7, 2, 5, 3, 1 },
            new int[] { 9, 7, 2, 5, 3, 1, 6, 4, 8 } };
    public static int[][] test7 = new int[][] {
            new int[] { 1, 4, 5, 7, 9, 2, 8, 3, 6 },
            new int[] { 3, 7, 6, 5, 8, 4, 1, 9, 2 },
            new int[] { 2, 9, 8, 3, 6, 1, 7, 5, 4 },
            new int[] { 7, 3, 1, 9, 2, 8, 6, 4, 5 },
            new int[] { 8, 5, 9, 6, 4, 7, 3, 2, 1 },
            new int[] { 4, 6, 2, 1, 3, 5, 9, 8, 7 },
            new int[] { 6, 2, 4, 8, 7, 3, 5, 1, 9 },
            new int[] { 5, 8, 7, 4, 1, 9, 2, 6, 3 },
            new int[] { 9, 1, 3, 2, 5, 6, 4, 7, 8 } };
    public static int[][] test8 = new int[][] {
            new int[] { 5, 2, 7, 4, 1, 6, 9, 3, 8 },
            new int[] { 8, 6, 4, 3, 2, 9, 1, 5, 7 },
            new int[] { 1, 3, 9, 5, 7, 8, 6, 4, 2 },
            new int[] { 2, 9, 1, 8, 5, 4, 3, 7, 6 },
            new int[] { 3, 4, 8, 6, 9, 7, 5, 2, 1 },
            new int[] { 6, 7, 5, 1, 3, 2, 4, 8, 9 },
            new int[] { 7, 1, 2, 9, 4, 5, 8, 6, 3 },
            new int[] { 4, 8, 3, 2, 6, 1, 7, 9, 5 },
            new int[] { 9, 5, 6, 7, 8, 3, 2, 1, 4 } };
    public static int[][] test9 = new int[][] {
            new int[] { 2, 4, 6, 7, 1, 3, 9, 8, 5 },
            new int[] { 1, 8, 5, 4, 9, 6, 7, 3, 2 },
            new int[] { 9, 3, 7, 8, 2, 5, 1, 4, 6 },
            new int[] { 6, 7, 8, 5, 4, 2, 3, 9, 1 },
            new int[] { 4, 9, 3, 1, 6, 8, 2, 5, 7 },
            new int[] { 5, 1, 2, 3, 7, 9, 4, 6, 8 },
            new int[] { 8, 2, 4, 9, 5, 7, 6, 1, 3 },
            new int[] { 7, 5, 9, 6, 3, 1, 8, 2, 4 },
            new int[] { 3, 6, 1, 2, 8, 4, 5, 7, 9 } };
    public static int[][] test10 = new int[][] {
            new int[] { 8, 6, 1, 2, 9, 4, 5, 7, 3 },
            new int[] { 4, 7, 5, 3, 1, 8, 6, 9, 2 },
            new int[] { 3, 9, 2, 5, 6, 7, 8, 1, 4 },
            new int[] { 2, 3, 6, 4, 5, 9, 7, 8, 1 },
            new int[] { 1, 5, 4, 7, 8, 3, 2, 6, 9 },
            new int[] { 9, 8, 7, 6, 2, 1, 3, 4, 5 },
            new int[] { 5, 2, 9, 1, 7, 6, 4, 3, 8 },
            new int[] { 6, 4, 8, 9, 3, 2, 1, 5, 7 },
            new int[] { 7, 1, 3, 8, 4, 5, 9, 2, 6 } };

    @Test
    public void test2() throws Exception {
        int encodedLength = 0;
        Puzz expected = new Puzz(test1);
        Puzz test = (Puzz) expected.clone();

        long start = System.currentTimeMillis();
        test = test.scramble(22);
        long duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        String encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();


        expected = new Puzz(test2);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();

        expected = new Puzz(test3);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();

        expected = new Puzz(test4);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();

        expected = new Puzz(test5);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();

        expected = new Puzz(test6);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();

        expected = new Puzz(test7);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();

        expected = new Puzz(test8);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();

        expected = new Puzz(test9);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

        encoded = Puzz.encode(test);

        System.out.println("Encoded Length with BigInteger: " + encoded.length());
        encodedLength += encoded.length();

        expected = new Puzz(test10);
        test = (Puzz) expected.clone();

        start = System.currentTimeMillis();
        test = test.scramble(22);
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration of scramble for 22 clue puzzle: " + duration);
        System.out.println("Scrambled");
        System.out.println(test);

encoded = Puzz.encode(test);
encodedLength += encoded.length();

        System.out.println("Final Result: " + encodedLength); 
    }

}

Wyjście testowe

Duration of scramble for 22 clue puzzle: 427614
Scrambled
0 0 3 0 0 0 0 0 6 
0 2 0 0 0 0 0 9 0 
0 0 0 0 9 6 7 5 0 
0 4 0 0 0 5 0 1 0 
0 0 0 1 0 0 0 0 0 
0 5 0 0 0 0 8 4 0 
0 0 0 3 0 0 5 0 7 
7 0 0 9 0 8 0 3 0 
0 0 0 0 0 0 0 0 0 

Building encoded string: U5[XZ+C6Bgf)}O."gDE)`\)kNv7*6}1w+
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 167739
Scrambled
0 2 4 0 0 0 0 0 0 
1 6 0 0 4 0 8 0 5 
0 0 5 0 9 7 2 0 0 
0 0 0 0 2 4 0 0 1 
0 0 3 9 0 0 0 0 0 
0 0 0 0 0 0 0 0 7 
0 4 0 0 0 0 0 0 8 
0 1 0 5 0 0 0 3 0 
0 0 0 0 0 0 0 0 0 

Building encoded string: 7\c^oE}`H6@P.&E)Zu\t>B"k}Vf<[0a3&
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 136364
Scrambled
0 0 7 0 8 0 0 0 0 
0 3 2 0 0 9 6 0 0 
0 0 0 0 0 0 2 5 0 
0 2 0 0 0 6 0 0 0 
0 0 0 9 0 0 0 0 0 
0 0 4 1 0 5 7 2 0 
5 0 1 0 0 0 0 7 0 
2 8 9 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 

Building encoded string: [S#bHlTDwS,&w,moQ{WN}Z9!{1C>.vN{-
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 392150
Scrambled
0 0 0 0 0 6 0 0 0 
0 9 0 0 0 0 0 0 1 
4 0 0 0 0 3 6 0 8 
0 0 0 0 0 0 0 8 0 
0 0 3 0 7 8 0 0 9 
7 0 0 0 0 0 0 0 3 
6 0 2 0 0 0 0 9 0 
9 0 1 3 4 0 2 0 0 
0 0 0 0 0 0 0 0 0 

Building encoded string: T-yKJ2<d)Dj~[~>]334*9YpxM<JQNf2|<
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 169355
Scrambled
0 0 0 0 0 1 0 0 0 
0 9 4 7 0 0 0 8 0 
0 1 3 0 0 0 5 0 2 
0 0 0 0 0 0 0 0 9 
0 0 0 0 2 7 3 5 4 
0 8 0 0 0 0 0 1 0 
0 0 0 0 4 0 9 0 8 
0 0 0 5 0 0 0 0 6 
0 0 0 0 0 0 0 0 0 

Building encoded string: 5@.=FmOKws7jl5*hWMQqqou\lv'e^Q}D:
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 786
Scrambled
0 2 3 0 0 6 0 0 0 
0 5 0 7 0 0 1 2 3 
0 8 0 0 2 0 0 0 0 
0 0 0 0 0 5 0 0 7 
0 6 5 8 0 0 0 0 0 
0 0 7 0 0 4 3 0 0 
0 3 0 0 4 0 0 0 2 
0 0 0 0 0 2 0 0 0 
0 0 0 0 0 0 0 0 0 

Building encoded string: wY%(O9tOSDZu-PBaFl^.f0xH7C~e)=\3&
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 826530
Scrambled
0 0 0 0 9 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 9 0 3 0 1 7 0 0 
0 3 0 0 0 8 0 4 5 
0 0 9 0 0 7 3 0 0 
0 0 2 0 3 0 0 8 0 
6 0 0 0 0 0 0 0 9 
5 0 0 4 1 0 2 0 3 
0 0 0 0 0 0 0 0 0 

Building encoded string: K|>.Aa?,8e&NRL;*ut=+Iqk8E$@&-zlF9
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 4834
Scrambled
0 2 0 0 1 0 0 3 8 
8 6 0 3 0 0 1 0 0 
0 0 0 0 0 8 6 0 2 
0 0 0 0 0 0 0 7 0 
0 0 8 0 0 0 0 0 0 
0 0 0 0 3 0 0 0 0 
0 0 2 0 0 5 8 0 3 
4 0 0 0 0 1 7 9 0 
0 0 0 0 0 0 0 0 0 

Building encoded string: GOS0!r=&HR5PZ|ezy>*l7 HWU`wIN7Q4&
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 42126
Scrambled
0 0 0 0 0 3 0 0 5 
0 0 5 4 0 0 0 3 2 
9 0 0 8 0 0 0 0 0 
0 0 0 0 0 2 0 0 0 
0 0 0 0 6 8 2 0 7 
5 1 0 0 7 0 0 0 8 
8 0 0 0 5 0 0 1 0 
7 0 0 0 0 0 0 0 4 
0 0 0 0 0 0 0 0 0 

Building encoded string: [4#9D_?I1.!h];Y_2!iqLyngbBJ&k)FF;
Encoded Length with BigInteger: 33

Duration of scramble for 22 clue puzzle: 156182
Scrambled
0 6 0 0 0 0 0 7 0 
4 0 5 3 1 0 0 0 2 
0 0 0 0 6 0 0 0 0 
0 3 0 0 0 9 0 8 1 
0 0 0 0 0 0 0 0 0 
0 0 7 0 0 1 0 4 5 
5 0 9 0 0 0 0 0 8 
6 0 0 0 3 2 0 0 0 
0 0 0 0 0 0 0 0 0 

Building encoded string: r+a;I%hGj4YCA-pXz+n=ioRL:agzH'K<(
Encoded Length with BigInteger: 33
Final Result: 330

C ++ 241, wynik: 82 * 10 = 820

Dodaje „!” na początku zakodowanego ciągu, aby określić, którą operację wykonać.

Gra w golfa 241 znaków

void D(char i){static int x=0;cout<<(int)(i-'a')<<" ";if(x++%8==0) cout<<endl;}
int main()
{
int i=81;int n;string S;
char c=cin.peek();
if(c=='!'){cin>>S;for_each(S.begin()+1,S.end(),D);}
else{S.push_back('!');while(i--){cin>>n;S.push_back(n+'a');}cout<<S;}
}

Nieoszlifowane 312 znaków

void decode(char i) {
static int x=0;
cout<<(int)(i-'a')<<" ";
if(x++%8==0) cout<<endl;
}
int main()
{
int i=81;
int n;
string d;
char c=cin.peek();
if(c=='!'){
cin>>d;
for_each(d.begin()+1,d.end(),decode);
}
else{
d.push_back('!');
while(i--)
{
cin>>n;
d.push_back(n+'a');
}
cout<<d;
}
}