Optimize paper folding to mitigate inkblots
Python

Exhaustively tries different combinations of folds for the first few folds, then does the rest of the folds using a greedy approach.

The exhaustive approach is bounded within a reasonable range of folds in the center, such that it won't take forever, while not ignoring too many possible folds to yield a good minimum.

Ran using pypy on my macbook air.

Answers:

20*20D9R15R6D11R10R9D10R11
40*20D6D13D9R19R21R20D11D10
40*40D21R21R11D19R23R20D23D15
20*80D33D47D40R10D39D41R9R11


Outputs:

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.2
Time taken: 4.016076s
Score: 7.91125
20*20D9R15R6D11R10R9D10R11

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.2
Time taken: 28.529278s
Score: 16.34375
40*20D6D13D9R19R21R20D11D10

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.25
Time taken: 98.430465s
Score: 42.13
40*40D21R21R11D19R23R20D23D15

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.25
Time taken: 234.873787s
Score: 32.30875
20*80D33D47D40R10D39D41R9R11


Total Score: 7.91125 + 16.34375 + 42.13 + 32.30875 = 98.69375 

Code:

import time, math
from collections import deque

numberOfFolds = 8 # Total number of folds

startTime = time.clock()

exec "grid = ("+"""
1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1
1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1
0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0
0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1
0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0
1 0 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 1
0 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0
1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1
1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0
0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1
0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0
0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1
0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1
1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1
0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0
0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0
0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 1 
""".replace(" ",",").replace("\n","],[")[2:-2]+")"

def getAverage(grid):
    count = total = 0
    for j in grid:
        for i in j:
            count += 1
            total += i
    return total/float(count)

def getScore(grid, average):
    score = 0
    for j in grid:
        for i in j:
            score += abs(average-i)
    return score

def downFoldedGrid(grid, row, width, height, copy=True):
    if copy: grid = [r[:] for r in grid]
    foldRange = min(row, height-row)
    for j in xrange(foldRange):
        rowRef1 = grid[row+j]
        rowRef2 = grid[row-1-j]
        for i in xrange(width):
            rowRef1[i] = rowRef2[i] = (rowRef1[i] + rowRef2[i]) * .5
    return grid

def downFoldedScore(grid, score, average, row, width, height):
    foldRange = min(row, height-row)
    average2  = 2*average
    for j in xrange(foldRange):
        rowRef1 = grid[row+j]
        rowRef2 = grid[row-1-j]
        a = b = c = 0
        for i in xrange(width):
            a = rowRef1[i] 
            b = rowRef2[i]
            c = a+b
            score += abs(average2-c) - abs(average-a) - abs(average-b)
    return score

def rightFoldedGrid(grid, column, width, height, copy=True):
    if copy: grid = [r[:] for r in grid]
    foldRange = min(column, width-column)
    for j in xrange(height):
        rowRef = grid[j]
        for i in xrange(foldRange):
            a = column+i
            b = column-1-i
            rowRef[a] = rowRef[b] = (rowRef[a] + rowRef[b]) * .5
    return grid

def rightFoldedScore(grid, score, average, column, width, height):
    foldRange = min(column, width-column)
    average2 = 2*average
    for j in xrange(height):
        rowRef = grid[j]
        a = b = c = 0
        for i in xrange(foldRange):
            a = rowRef[column+i]
            b = rowRef[column-1-i]
            c = a+b
            score += abs(average2-c) - abs(average-a) - abs(average-b)
    return score

def bestFoldsGreedy(grid, average, maxFolds, width, height):
    score  = getScore(grid, average)
    folds  = []
    append = folds.append
    for z in xrange(maxFolds):
        bestFold      = 0
        bestFoldScore = score
        bestFoldGrid  = grid
        for i in xrange(1, width): #Try all right folds
            foldScore = rightFoldedScore(grid, score, average, i, width, height)
            if foldScore &lt; bestFoldScore:
                bestFold      = i
                bestFoldScore = foldScore
        for i in xrange(1, height): #Try all down folds
            foldScore = downFoldedScore(grid, score, average, i, width, height)
            if foldScore &lt; bestFoldScore:
                bestFold      = -i
                bestFoldScore = foldScore
        if bestFold:
            append(bestFold)
            score = bestFoldScore
            if bestFold &gt; 0: rightFoldedGrid(grid, bestFold, width, height, False)
            else:            downFoldedGrid(grid, -bestFold, width, height, False)
    return score, folds


# Get the height and width
height  = len(grid)
width   = len(grid[0])

# Transpose the grid if height &gt; width for better locality of reference
transposed = False
if height &gt; width:
    grid = [[grid[i][j] for i in range(height)] for j in range(width)]
    transposed = True
    height, width = width, height

# The exhaustive grids and folds attempted
exhaustiveGridsAndFolds = deque([(grid,[])])
popleft = exhaustiveGridsAndFolds.popleft
append  = exhaustiveGridsAndFolds.append

# Set the bounds to exhaustively test for
exhaustiveLevels   = 3
prunePadding       = [0.2, 0.25][width*height &gt; 1000]
leftBound          = int(max(width*prunePadding, 1))
rightBound         = int(width*(1.0-prunePadding))
topBound           = int(max(height*prunePadding, 1))
bottomBound        = int(height*(1.0-prunePadding))

# Populate the exhaustive grids and folds
while 1:
    grid, folds = popleft()
    if len(folds) == exhaustiveLevels:
        append((grid, folds))
        break
    for i in xrange(leftBound, rightBound):
        if i not in folds:
            append((rightFoldedGrid(grid, i, width, height), folds+[i]))
    for i in xrange(topBound, bottomBound):
        if -i not in folds:
            append((downFoldedGrid(grid, i, width, height), folds+[-i]))

# Test all the exhaustive grids and folds greedily
average             = getAverage(grid)
bestFinalScore      = getScore(grid, average)
bestFinalFolds      = []
numberOfGreedyFolds = numberOfFolds-exhaustiveLevels
while exhaustiveGridsAndFolds:
    grid, exhaustiveFolds = popleft()
    finalScore, greedyFolds = bestFoldsGreedy(grid, average, numberOfGreedyFolds, width, height)
    if finalScore &lt;= bestFinalScore:
        bestFinalScore = finalScore
        bestFinalFolds = exhaustiveFolds + greedyFolds


# Repeat the last fold till the total number of folds if needed
if len(bestFinalFolds) &lt; numberOfFolds:
    bestFinalFolds += [bestFinalFolds[-1]]*(numberOfFolds-len(bestFinalFolds))

# Print the best result
foldsString = ""
down  = "D"
right = "R"
if transposed:
    down,  right  = right,  down
    width, height = height, width
for fold in bestFinalFolds:
    if   fold &gt; 0: foldsString += right+str(fold)
    elif fold &lt; 0: foldsString += down+str(-fold)
print "Exhaustive folds levels: " + str(exhaustiveLevels)
print "Percentage pruned from sides from exhaustive folds: " + str(prunePadding)
print "Time taken: " + str(time.clock()-startTime) + "s"
print "Score: " + str(bestFinalScore)
print str(width) + "*" + str(height) + foldsString