Ваша задача - написать программу (или две отдельные программы) на любом языке, который:

1. Может взять заполненную доску судоку в качестве входных данных (в любом логическом формате) и сжать ее в строку символов
2. Может взять сжатую строку в качестве ввода и распаковать ее, чтобы получить точно такую же заполненную доску судоку (вывод в любом логическом формате из 9 строк)

Примечание: используйте правила судоку в ваших интересах; это идея этого вызова.
Судоку правил в Википедии

правила

• Только сжатые символы ASCII (32 - 126) допускаются в сжатом выводе (например, нет многобайтовых символов ).
• Вы можете предположить, что вход является действительной доской Судоку 3х3 (нормальные правила, без изменений).
• Я не буду устанавливать временные ограничения, но не буду создавать алгоритм перебора. Или, отправители должны иметь возможность проверить свои материалы перед публикацией (Спасибо Ян Дворжак).

Если у вас есть какие-либо вопросы или проблемы, вы можете попросить разъяснения или внести предложения в комментариях.

Условия выигрыша

Оценка = сумма количества символов из всех десяти тестовых случаев

Самый низкий балл побеждает.

Тестовые случаи

Вы можете использовать их, чтобы проверить, насколько хорошо работает ваша программа.

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

Благодарим http://www.opensky.ca/~jdhildeb/software/sudokugen/ за некоторые из этих

Если вы обнаружите какие-либо проблемы с тестовыми примерами, пожалуйста, сообщите мне.

Хаскелл, 107 очков

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

Результаты теста:

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*

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

Поднятие тяжестей выполняется solution2ixфункцией, которая для каждого блока 3x3 генерирует все возможные перестановки с учетом ограничений слева и сверху, пока не найдет одну в закодированном решении, запоминая только индекс упомянутой перестановки. Затем он объединяет индексы, используя некоторые предварительно вычисленные веса и схему Хорнера.

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

assignmentsпростая, но уродливая развернутая рекурсия с использованием монады списка. Он генерирует список перестановок с учетом набора ограничений.

Реальная сила исходит от жестких границ длины списка перестановок:

• Верхний левый угол без ограничений. Количество перестановок просто 9!. Это значение никогда не используется, кроме как для поиска верхней границы для выходной длины.
• Блоки рядом с ним имеют только один набор ограничений - сверху слева. Наивная верхняя граница 6*5*4*6!в семь раз хуже, чем фактическое число, найденное при перечислении:12096
• Верхний правый угол ограничен дважды слева. Каждая строка может иметь только шесть перестановок, и в худшем случае (фактически в каждом действительном случае) назначение является независимым. Аналогично для нижнего левого угла.
• Центральную часть было труднее всего оценить. Опять побеждает грубая сила - подсчитайте перестановку для каждого возможного набора ограничений вплоть до изоморфизма. Требуется время, но это нужно только один раз.
• Правая центральная часть имеет двойное ограничение слева, что приводит к перестановке каждой строки, но также и одно ограничение сверху, которое гарантирует, что фактически возможны только две перестановки на строку. Аналогично для нижней центральной части.
• Нижний правый угол полностью определяется соседями. Единственная перестановка фактически никогда не проверяется при вычислении индекса. Принудительная оценка была бы легкой, просто не обязательной.

Результатом всех этих ограничений является 71025136897117189570560~ = 95^11.5544, что означает, что ни один код не должен быть длиннее 12 символов, и почти половина из них должна быть 11 символов или меньше. Я решил не делать различий между более короткой строкой и той же строкой, дополненной пробелами. Пространства где-либо еще являются значительными.

Теоретическое ограничение эффективности кодирования для кодов без префиксов - логарифм base-95 6670903752021072936960- 11.035означает, что даже оптимальный алгоритм не может избежать создания выходных данных длины 12, хотя он будет производить их только в 3,5% всех случаев. Разрешение длины быть значительным (или, что то же самое, добавление конечных пробелов) действительно добавляет несколько кодов (1% от общего количества), но этого недостаточно, чтобы устранить необходимость в кодах длины-12.

Питон, 130 баллов

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"!

Алгоритм работает, кодируя каждую позицию на доске, по одному, в большое целое число. Для каждой позиции рассчитываются возможные значения с учетом всех закодированных назначений. Поэтому, если [1,3,7,9] являются возможными значениями для данной позиции, для кодирования выбора требуется 2 бита.

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

Получив большое целое число, мы записываем его в базу 95.

Возможно, порядок кодирования лучше, чем в лексикографическом, но я об этом особо не задумывался.

Кодер:

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

декодер:

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])

Запустите это так:

> 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 - оценка 115 113 103 113

Выход:

"#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%-

Выход:

                  # 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

Ни одна из этих строк не имеет завершающего пробела. Обратите внимание, что первая строка пуста.

Этот алгоритм работает следующим образом. Сжать:

1. Начните с пустой текущей строки, представляющей сетку судоку

2. Попробуйте добавить по очереди каждую цифру 1 ... 9 к этой строке и определить, какая из них является жизнеспособной.

3. Получить следующую цифру из сетки ответов (и добавить ее к текущей)

4. Если только один является жизнеспособным, нет ничего, чтобы закодировать

5. Если существует более одного жизнеспособного, подсчитайте количество жизнеспособных опций, отсортируйте их и закодируйте эту цифру в качестве индекса в отсортированный массив. Запишите в массиве цифру и число в качестве 2-кортежа.

6. Когда все сделано, закодируйте каждый из 2-х кортежей (в обратном порядке) в число на основе переменной, сохраненное как bigint.

7. Экспресс бигинт в базе 95.

Расшифровать:

1. Начните с пустой текущей строки, представляющей сетку судоку

2. Расшифровать номер base95 в бигинт

3. Попробуйте добавить по очереди каждую цифру 1 ... 9 к этой строке и определить, какая из них является жизнеспособной.

4. Если только один является жизнеспособным, нет ничего, чтобы закодировать; добавить этот выбор в сетку

5. Если существует более одного жизнеспособного, подсчитайте количество жизнеспособных опций, отсортируйте их и закодируйте эту цифру в качестве индекса в отсортированный массив.

6. Декодируйте переменную base bigint, используя количество жизнеспособных опций в качестве базы и модуль в качестве индекса в массиве, и выводите эту цифру в качестве значения ячейки.

Для определения количества жизнеспособных опций используется Games :: Sudoku :: Solver. Это в основном для ясности, так как на этом сайте есть 3 линейных решателя судоку.

На все 10 ушло 8 секунд на моем ноутбуке.

fudgeОперация сортирует массив по- разному , чтобы достичь минимального значения для тестов. Как задокументировано, это выдумка. Выдумка снижает оценку со 115 до 103. Это сделано вручную, чтобы гарантировать, что код bigint для первого теста равен 0. Наихудший результат для любого судоку - 12, что дает оценку 120. Поэтому я не думаю, что это считается как жесткий код; скорее это оптимизирует для тестовых данных. Чтобы увидеть его работу без этого изменения sort fudgeв sortобоих местах.

Код следует:

#!/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 байтов

Это просто быстрое базовое решение. Извините, я сделал это на языке игры в гольф, но на самом деле это был самый простой способ сделать это. Я добавлю объяснение фактического кода завтра, но я обрисовал в общих чертах алгоритм ниже.

кодировщик

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

дешифратор

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

Проверьте это здесь.

Вход кодера (на STDIN) и выход декодера (на STDOUT) имеют форму вложенного массива CJam. Например

[[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 тестовых выходов:

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

Алгоритм очень прост:

• Удалить последний столбец и строку.
• Рассматривайте оставшиеся 64 цифры как число основания 9 (после уменьшения каждой цифры на 1).
• Преобразуйте это в base-95, добавьте 32 к каждой цифре и превратите в соответствующий символ ASCII.
• Для декодирования измените базовое преобразование и заполните последний столбец и строку пропущенными числами.

Python 2.7, всего 107 символов

TL; DR перебор всех 3х3 квадратов с ограничениями сверху + слева

контрольные примеры:

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')

вспомогательная функция для печати судоку

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

генерирует все возможные квадраты с учетом ограничений сверху и слева

см код комментария для более подробной информации

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)

извлекает все квадраты из доски судоку как кортежи

см код комментария для более подробной информации

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)]

преобразует квадраты обратно в судоку

в основном обратная функция выше

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

заданных квадратов осталось, вернуть ограничения

см код комментария для более подробной информации

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 [], [], []

заданные квадраты выше, возвратные ограничения

см код комментария для более подробной информации

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 [], [], []

делает строку

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

это жестко закодированный список зависимостей для каждого квадрата

см код комментария для более подробной информации

"""
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])}

это жестко запрограммированный список максимального количества возможных вариантов для каждого квадрата

см код комментария для более подробной информации

"""
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]

они объединяют вышеуказанные функции и преобразуют доску в список целых чисел

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

и обратно на доску

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

хорошо, это все функции

для каждой доски сделайте строку и распечатайте ее

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 ''

Теперь выведите общую длину всех строк.

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

и unringringify, чтобы доказать, что это не одностороннее сжатие

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 ''

выход:

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, оценка: 130 9

Обновить:

После того, как этот ответ был опубликован, он вдохновил новую лазейку ближе: «Оптимизация для данных тестовых случаев» . Однако я оставлю этот ответ как есть, как пример лазейки. Не стесняйтесь понижать голос. Мне не будет больно.

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]]
]

Закодированные тестовые случаи:

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

Это не приводит к идеальному кодированию (в среднем ~ 11), так как основные правила не исключают некоторые варианты, для которых фактически нет решения. Производительность может быть улучшена (т. Е. Большое целое число всегда будет меньше, чем число возможных плат Судоку), проверив, не существует ли решения для некоторых из текущих вариантов с использованием решателя Судоку, и исключив их.

J, 254 балла

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'

Стандартные операции ввода-вывода немного неуклюжи в J, поскольку jconsoleна самом деле это REPL, поэтому я позволил себе записать сжатый вывод в файл.

Находит индекс анаграммы каждой строки, обрабатывает полученные девять чисел как число base (9!), А затем, наконец, преобразует в base-95, добавляет 32 и преобразует в ASCII, как в решении Мартина Бюттнера. Индекс анаграммы перестановки 1..n - это просто индекс перестановки в лексически отсортированном списке всех таких перестановок, например, 5 4 3 2 1имеет индекс анаграммы 5! - 1 = 119 .

Все операции имеют простые инверсии, поэтому декомпрессия проста.

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

Сжатые строки для тестовых случаев:

#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 баллов

Эта программа перечисляет все возможные 3x3-блоки и запоминает, какой из них действительно присутствовал в оригинальном судоку, а затем объединяет все эти числа в представление base-95. Хотя это очень близко к жесткому кодированию, оно сжимает и распаковывает примеры примерно на 5 секунд каждый на моей машине.

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]

Основными функциями являются compress(sudoku)и decompress(text).

Выходы:

!%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 баллов

Код:

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

Полученные результаты:

!|/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

Очень медленно. Потребовалось 517 секунд, чтобы запустить и проверить на моей машине.

encconfig берет доску судоку и цифру от 1 до 9, перечисляет координаты xy, где появляется эта цифра, и выводит число в диапазоне (6 ** 6), которое представляет эти координаты. («цифровая конфигурация»)

decconfig - это обратная функция. Требуется число в диапазоне (6 ** 6), цифра и доска судоку (по умолчанию пусто). Она выводит плату судоку с наложенной на нее цифрой. Если одна из позиций в конфигурации цифр уже занята на введенной доске судоку, цифра в этой позиции заменяется новой цифрой.

Совместимость принимает плату судоку и конфигурацию цифр (определяется с помощью conf и dig), накладывает конфигурацию цифр на плату судоку и проверяет наличие конфликтов. Затем он возвращает True или False в зависимости от результата.

закодировать это функция сжатия. Он берет доску судоку и выводит число, представляющее ее. Он делает это, сначала копируя позиции единиц на пустую доску и составляя список всех конфигураций числа 2, которые совместимы с конфигурацией 1 (которые не занимают места, уже занятые 1 - х). Затем он находит порядок фактической 2-конфигурации платы в списке и сохраняет ее, затем копирует эту конфигурацию на новую плату, которая теперь содержит только 1 и 2. Затем он перечисляет все конфигурации числа 3, которые совместимы с позициями 1 и 2, и так далее.

декодирование - обратная функция.

Python 2.5.

C #, 150 байт

Сжатый выход:

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

Как это работает:

Он генерирует все возможные перестановки 123456789 и запоминает их. Затем он сравнивает перестановки со строками в судоку. Когда совпадающая перестановка для заданной строки найдена, она запоминает индекс этой перестановки. После каждой строки будут удалены все перестановки, где есть хотя бы один символ в той же позиции, что и текущая строка. Это гарантирует, что каждое число уникально в своем столбце. Затем он удаляет все перестановки, которые больше не работают по критериям коробки. Поскольку последний ряд тривиален, он генерирует 8 чисел. Я проверил, каково будет максимальное значение каждого из этих чисел, и сгенерировал маску подсчета цифр для каждой их позиции. {6, 5, 3, 5, 3, 1, 2, 1, 1}. Первый, очевидно, самый длинный с 362880 перестановками. Используя цифровую маску, я создаю BigInteger с ведущей 1, чтобы сделать его длиной 28 цифр. В результате получается всего 11 байтов. Затем эти байты преобразуются в base64. Чтобы сохранить один символ, я убираю знак = в конце.

Работы по реконструкции аналогичны.

Он восстанавливает BigInteger из строки base64, а затем снова превращает его в строку и снова разделяет, используя упомянутую маску подсчета цифр. Эти строки анализируются обратно в индексы.

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

Возможно, было бы немного лучше по-настоящему использовать 94 возможных символа вместо только 64, но мне не хватает мозгов, чтобы сделать это.

Источник : Скопируйте и вставьте, чтобы он работал с 10 примерами. .dotNet-Fiddle говорит мне, что это превышает ограничение памяти, поэтому вам нужно запустить его на своем компьютере, чтобы текст.

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 символов = 290 баллов

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

Вот как это работает:

• Сначала преобразуйте массив 9 x 9 в 60 чисел. Это можно сделать, так как последний столбец, последний ряд и последний квадрат каждой ячейки 3 × 3 могут быть отброшены.

• Затем преобразуйте с помощью bigint в одно целое число, используя 9 ^ 60 элементов.

• Затем конвертируйте бигинт в базу 95.

Компрессор и декомпрессор:

#!/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";
}

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

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

Строка форматируется как целое число 10, 11 или 12 (пусть это будет основание b) с Aпредставлением двух нулей, иB трех.

Это преобразуется в целое число base-95 и добавляется перед цифрой base-95, представляющей z << 2 | (b - 10) .

Позвоните, php sudoku-compress.php encчтобы закодировать, иphp sudoku-compress.php dec декодирования. Кодировщик принимает формат, указанный в вопросе, с обязательным завершающим переводом строки.

Тестовые выходы:

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 баллов

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

1. Разработайте алгоритм решения головоломки Судоку.

2. Разработайте алгоритм шифрования, который еще можно решить. Он делает это несколько случайным образом, удаляя подсказки, которые можно легко определить заранее. Я мог получить примерно 22 подсказки, прежде чем это заняло слишком много времени.

3. После скремблирования головоломка может быть представлена ​​триплетом однозначных целых чисел для каждой подсказки, в моем случае 22 тройки из 3. Я подумал, что если бы я мог объединить их в одно 66-значное число, тогда base95 закодировал бы это, тогда у меня есть кое-что, что может быть легко расшифрованным.

Закодированная строка оказалась длиннее, чем я ожидал, обычно около 33 символов. В этот момент я попробовал альтернативный способ, чем использование Java BigInteger, где я создал большое число из 81-битной маски, представляющей 81 ячейку сетки, где 1 означает, что для этой ячейки существует подсказка. Затем я скомбинировал эту битовую маску с 4-битными представлениями каждого значения ячейки в последовательном порядке, округлил до байтов и обнаружил, что я получил примерно одинаковую длину кодированной строки после кодирования base95.

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

Класс Пазз

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

Мой тестовый кейс

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

}

Тестовый вывод

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

С ++ 241, оценка: 82 * 10 = 820

Добавляет '!' в начало закодированной строки, чтобы определить, какую операцию выполнить.

Игра в гольф 241 символ

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

Ungolfed 312 символов

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