Latin square compression A Latin square is a square that has no repeated symbols in the rows or columns:. 

13420
21304
32041
04213
40132


And as many Sudoku players know, you don't need all of the numbers to deduce the remaining numbers.

Your challenge is to compress a Latin square into as few bytes as possible.  You need to provide one or two program(s) that compresses/decompresses.

Various info:


The numbers used will always be 0..N-1, where N is the length of the square's edge, and N&lt;=25
On decompression, the latin square must be identical to the input.
Your program(s) should be able to (de)compress any latin square (within the maximum square size), not just the ones I've provided.  Compression ratios should be similar as well.
You must actually run the compression and decompressor to obtain your score (No end-of-universe runtimes)


The test cases can be found on github.  Your score is total size of compressed test cases.

EDIT: As of 20:07 on July 7th, I updated the test cases (in order to fix a generation issue).  Please rerun your program on the new test cases.  Thanks Anders Kaseorg.
Python, 1281.375 1268.625 bytes

We encode the Latin square one “decision” at a time, where each decision is of one of these three forms:


which number goes in row i, column j;
in row i, which column the number k goes in;
in column j, which row the number k goes in.


At each step, we make all the logical inferences we can based on previous decisions, then pick the decision with the smallest number of possible choices, which therefore take the smallest number of bits to represent.

The choices are provided by a simple arithmetic decoder (div/mod by the number of choices).  But that leaves some redundancy in the encoding: if k decodes to a square where the product of all the numbers of choices was m, then k + m, k + 2⋅m, k + 3⋅m, … decode to the same square with some leftover state at the end.

We take advantage of this redundancy to avoid explicitly encoding the size of the square.  The decompressor starts by trying to decode a square of size 1.  Whenever the decoder finishes with leftover state, it throws out that result, subtracts m from the original number, increases the size by 1, and tries again.

import numpy as np

class Latin(object):
    def __init__(self, size):
        self.size = size
        self.possible = np.full((size, size, size), True, dtype=bool)
        self.count = np.full((3, size, size), size, dtype=int)
        self.chosen = np.full((3, size, size), -1, dtype=int)

    def decision(self):
        axis, u, v = np.unravel_index(np.where(self.chosen == -1, self.count, self.size).argmin(), self.count.shape)
        if self.chosen[axis, u, v] == -1:
            ws, = np.rollaxis(self.possible, axis)[:, u, v].nonzero()
            return axis, u, v, list(ws)
        else:
            return None, None, None, None

    def choose(self, axis, u, v, w):
        t = [u, v]
        t[axis:axis] = [w]
        i, j, k = t
        assert self.possible[i, j, k]
        assert self.chosen[0, j, k] == self.chosen[1, i, k] == self.chosen[2, i, j] == -1

        self.count[1, :, k] -= self.possible[:, j, k]
        self.count[2, :, j] -= self.possible[:, j, k]
        self.count[0, :, k] -= self.possible[i, :, k]
        self.count[2, i, :] -= self.possible[i, :, k]
        self.count[0, j, :] -= self.possible[i, j, :]
        self.count[1, i, :] -= self.possible[i, j, :]
        self.count[0, j, k] = self.count[1, i, k] = self.count[2, i, j] = 1
        self.possible[i, j, :] = self.possible[i, :, k] = self.possible[:, j, k] = False
        self.possible[i, j, k] = True
        self.chosen[0, j, k] = i
        self.chosen[1, i, k] = j
        self.chosen[2, i, j] = k

def encode_sized(size, square):
    square = np.array(square, dtype=int)
    latin = Latin(size)
    chosen = np.array([np.argmax(square[:, :, np.newaxis] == np.arange(size)[np.newaxis, np.newaxis, :], axis=axis) for axis in range(3)])
    num, denom = 0, 1
    while True:
        axis, u, v, ws = latin.decision()
        if axis is None:
            break
        w = chosen[axis, u, v]
        num += ws.index(w)*denom
        denom *= len(ws)
        latin.choose(axis, u, v, w)
    return num

def decode_sized(size, num):
    latin = Latin(size)
    denom = 1
    while True:
        axis, u, v, ws = latin.decision()
        if axis is None:
            break
        if not ws:
            return None, 0
        latin.choose(axis, u, v, ws[num % len(ws)])
        num //= len(ws)
        denom *= len(ws)
    return latin.chosen[2].tolist(), denom

def compress(square):
    size = len(square)
    assert size &gt; 0
    num = encode_sized(size, square)
    while size &gt; 1:
        size -= 1
        square, denom = decode_sized(size, num)
        num += denom
    return '{:b}'.format(num + 1)[1:]

def decompress(bits):
    num = int('1' + bits, 2) - 1
    size = 1
    while True:
        square, denom = decode_sized(size, num)
        num -= denom
        if num &lt; 0:
            return square
        size += 1

total = 0
with open('latin_squares.txt') as f:
    while True:
        square = [list(map(int, l.split(','))) for l in iter(lambda: next(f), '\n')]
        if not square:
            break

        bits = compress(square)
        assert set(bits) &lt;= {'0', '1'}
        assert square == decompress(bits)
        print('Square {}: {} bits'.format(len(square), len(bits)))
        total += len(bits)

print('Total: {} bits = {} bytes'.format(total, total/8.0))


Output:

Square 1: 0 bits
Square 2: 1 bits
Square 3: 3 bits
Square 4: 8 bits
Square 5: 12 bits
Square 6: 29 bits
Square 7: 43 bits
Square 8: 66 bits
Square 9: 94 bits
Square 10: 122 bits
Square 11: 153 bits
Square 12: 198 bits
Square 13: 250 bits
Square 14: 305 bits
Square 15: 363 bits
Square 16: 436 bits
Square 17: 506 bits
Square 18: 584 bits
Square 19: 674 bits
Square 20: 763 bits
Square 21: 877 bits
Square 22: 978 bits
Square 23: 1097 bits
Square 24: 1230 bits
Square 25: 1357 bits
Total: 10149 bits = 1268.625 bytes