new puzzle challenge

[brouhaha]

I wrote a recursive Python program to do a search with backtracking, and it finds 12 solutions, but only one is unique and the remainder are rotations and/or reflections. It would be much faster if written in C. It shouldn't be too difficult to translate the Python program to RPL, though it will take much longer to run on a 50g than the Python program takes on an x86.

I haven't figured out how to restrict the search space optimally to avoid rotations and reflections, but you can restrict it slightly. A row of three pieces must have at least one piece that is 11 or less. If you start from a row along one edge, and from one end of that edge, you only have to handle cases where that end piece is 1 through 11, or the end piece is greater than 11 and the middle piece of the row is 1 though 11. Unfortunately this doesn't actually speed up the program much if backtracking is used.

On a 4.0 GHz AMD FX-8350 CPU, running Fedora 21 64-bit and Python 2.7.8, it finds the seven reported solutions in at elapsed times of 4.6, 8.0, 179.9, 200.8, 259.7, 265.2, and 917.9 seconds.

Code:


#!/usr/bin/python2
import sys
import time

size = 19
avail = [ True ] * size
board = [ None ] * size

# first element of each row tuple should be the highest location in the tuple,
# and the list should be sorted by the first element of the tuple
rows = {  2: ((2, 1, 0),),
          6: ((6, 5, 4, 3),),
          7: ((7, 3, 0),),
         11: ((11, 6, 2),
              (11, 10, 9, 8, 7)),
         12: ((12, 8, 4, 1),),
         15: ((15, 10, 5, 1),
              (15, 14, 13, 12)),
         16: ((16, 12, 7),
              (16, 13, 9, 5, 2)),
         17: ((17, 13, 8, 3),
              (17, 14, 10, 6)),
         18: ((18, 15, 11),
              (18, 17, 16),
              (18, 14, 9, 4, 0)) }

def print_board():
    global start_time
    print "elapsed time:",time.time() - start_time
    print '   ', '  '.join(["%2d" % board[pos] for pos in range(0, 3)])
    print ' ', '  '.join(["%2d" % board[pos] for pos in range(3, 7)])
    print '  '.join(["%2d" % board[pos] for pos in range(7, 12)])
    print ' ', '  '.join(["%2d" % board[pos] for pos in range(12, 16)])
    print '   ', '  '.join(["%2d" % board[pos] for pos in range(16, 19)])
    print
    sys.stdout.flush()

def check_board(pos):
    # remove the following test if you want all 12 solutions
    if pos == 1 and board[0] > 11 and board[1] > 11:
        return False
    rows_to_check = rows.get(pos)
    if rows_to_check is not None:
        for row in rows_to_check:
            #print "row", row, "content", [board[pos] for pos in row], "sum", sum([board[pos] for pos in row])
            if sum([board[pos] for pos in row]) != 38:
                return False
    return True

def fill_position(pos):
    for piece in range(size):
        if avail[piece]:
            board[pos] = piece + 1
            if check_board(pos):
                avail[piece] = False
                if (pos+1) == size:
                    print_board()
                else:
                    fill_position(pos+1)
                avail[piece] = True

start_time = time.time()
fill_position(0)
print "total elapsed time:",time.time() - start_time