Какой алгоритм найдет сетку квадратов за разумное время?

Question

я нашел результат, который есть сетка размером 9x13 со следующими свойствами:

Каждая клетка содержит цифру в базе 10.

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

Например, если мы имеем следующую сетку:

340934433 
324324893 
455423343 

Тогда можно выбрать крайний левый верхний ряд 3 и выбрать направление движения вправо и вниз, чтобы прочитать номера 3, 32 и 325.

Теперь нужно доказать, что существует сетка размером 9x13, где можно прочитать квадраты от 1 до 100, т. Е. Можно прочитать все целые числа вида i^2, где i = 1, ..., 100 из квадрат.

Лучшая сетка, которую я нашел в сети, имеет размер 11x11, данный в Solving a recreational square packing problem. Но, похоже, сложно изменить программу, чтобы найти целые числа в прямоугольной сетке.

Итак, какой алгоритм вывел бы подходящую сетку в разумные сроки?

Я только что получил ключевую ошибку из этого кода:

import random, time, sys 

N = 9 
M = 13 
K = 100 

# These are the numbers we would like to pack 
numbers = [str(i*i) for i in xrange(1, K+1)] 

# Build the global list of digits (used for weighted random guess) 
digits = "".join(numbers) 

def random_digit(n=len(digits)-1): 
    return digits[random.randint(0, n)] 

# By how many lines each of the numbers is currently covered 
count = dict((x, 0) for x in numbers) 

# Number of actually covered numbers 
covered = 0 

# All lines in current position (row, cols, diags, counter-diags) 
lines = (["*"*N for x in xrange(N)] + 
     ["*"*M for x in xrange(M)] + 
     ["*"*x for x in xrange(1, N)] + ["*"*x for x in xrange(N, 0, -1)] + 
     ["*"*x for x in xrange(1, M)] + ["*"*x for x in xrange(M, 0, -1)]) 

# lines_of[x, y] -> list of line/char indexes 
lines_of = {} 
def add_line_of(x, y, L): 
    try: 
     lines_of[x, y].append(L) 
    except KeyError: 
     lines_of[x, y] = [L] 
for y in xrange(N): 
    for x in xrange(N): 
     add_line_of(x, y, (y, x)) 
     add_line_of(x, y, (M + x, y)) 
     add_line_of(x, y, (2*M + (x + y), x - max(0, x + y - M + 1))) 
     add_line_of(x, y, (2*M + 2*N-1 + (x + N-1 - y), x - max(0, x + (M-1 - y) - M + 1))) 

# Numbers covered by each line 
covered_numbers = [set() for x in xrange(len(lines))] 

# Which numbers the string x covers 
def cover(x): 
    c = x + "/" + x[::-1] 
    return [y for y in numbers if y in c] 

# Set a matrix element 
def setValue(x, y, d): 
    global covered 
    for i, j in lines_of[x, y]: 
     L = lines[i] 
     C = covered_numbers[i] 
     newL = L[:j] + d + L[j+1:] 
     newC = set(cover(newL)) 
     for lost in C - newC: 
      count[lost] -= 1 
      if count[lost] == 0: 
       covered -= 1 
     for gained in newC - C: 
      count[gained] += 1 
      if count[gained] == 1: 
       covered += 1 
     covered_numbers[i] = newC 
     lines[i] = newL 

def do_search(k, r): 
    start = time.time() 

    for i in xrange(r): 
     x = random.randint(0, N-1) 
     y = random.randint(0, M-1) 
     setValue(x, y, random_digit()) 

    best = None 
    attempts = k 
    while attempts > 0: 
     attempts -= 1 
     old = [] 
     for ch in xrange(1): 
      x = random.randint(0, N-1) 
      y = random.randint(0, M-1) 
      old.append((x, y, lines[y][x])) 
      setValue(x, y, random_digit()) 
     if best is None or covered > best[0]: 
      now = time.time() 
      sys.stdout.write(str(covered) + chr(13)) 
      sys.stdout.flush() 
      attempts = k 
     if best is None or covered >= best[0]: 
      best = [covered, lines[:N][:]] 
     else: 
      for x, y, o in old[::-1]: 
       setValue(x, y, o) 
    print 
    sys.stdout.flush() 
    return best 

for y in xrange(N): 
    for x in xrange(N): 
     setValue(x, y, random_digit()) 

best = None 
while True: 
    if best is not None: 
     for y in xrange(M): 
      for x in xrange(N): 
       setValue(x, y, best[1][y][x]) 
    x = do_search(100000, M) 
    if best is None or x[0] > best[0]: 
     print x[0] 
     print "\n".join(" ".join(y) for y in x[1]) 
    if best is None or x[0] >= best[0]: 
     best = x[:] 

Answer 1

Чтобы создать такую ​​сетку, я бы начал со списком строк, представляющих собой квадраты первого K (100) чисел.

Уменьшите эти строки насколько возможно, где многие содержатся в других (например, 625 содержит 25, поэтому 625 покрывает квадраты 5 и 25).

Это должно дать первоначальный список из 81 уникальных площадей, что требует как минимум около 312 цифр:

def construct_optimal_set(K): 
    # compute a minimal solution: 
    numbers = [str(n*n) for n in range(0,K+1)] 
    min_numbers = [] 
    # note: go in reverse direction, biggest to smallest, to maximize elimination of smaller numbers later 
    while len(numbers) > 0: 
    i = 0 
    while i < len(min_numbers): 
     q = min_numbers[i] 
     qr = reverse(min_numbers[i]) 
     # check if the first number is contained within any element of min_numbers 
     if numbers[-1] in q or numbers[-1] in qr: 
     break 
     # check if any element of min_numbers is contained within the first number 
     elif q in numbers[-1] or qr in numbers[-1]: 
     min_numbers[i] = numbers[-1] 
     break 
     i += 1 
    # if not found, add it 
    if i >= len(min_numbers): 
     min_numbers.append(numbers[-1]) 
    numbers = numbers[:-1] 
    min_numbers.sort() 
    return min_numbers 

Это возвращает минимальный набор квадратов, с любыми площадями, которые являются подмножествами других квадратов удалены. Расширьте это, объединив любые элементы с перекрытием (например, 484 и 841 на 4841); Я оставляю это как упражнение, так как он будет строить знакомство с этим кодом.

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

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

def merge(digits): 
    result = 0 
    for i in range(len(digits)-1,-1,-1): 
    result = result * 10 + digits[i] 
    return result 
def merge_reverse(digits): 
    result = 0 
    for i in range(0, len(digits)): 
    result = result * 10 + digits[i] 
    return result 

# given a grid where each element contains a single numeric digit, 
# return list of every ordering of those digits less than SQK, 
# such that you pick a starting point and one of eight directions, 
# and assemble digits until either end of grid or larger than SQK; 
# this will construct only the unique combinations; 
# also note that this will not construct a large number of values, 
# since for any given direction, there are at most 
#  (sqrt(n*n + m*m))! 
# possible arrangements, and there will rarely be that many. 
def construct_lines(grid, k): 
    # rather than build a dictionary type, use a little more memory to use faster simple array indexes; 
    # index is #, and value at index indicates existence: 0 = does not exist, >0 means exists in grid 
    sqk = k*k 
    combinations = [0]*(sqk+1) 

    # do all horizontals, since they are easiest 
    for y in range(len(grid)): 
    digits = [] 
    for x in range(len(grid[y])): 
     digits.append(grid[y][x]) 
     # for every possible starting point... 
     for q in range(1,len(digits)): 
     number = merge(digits[q:]) 
     if number <= sqk: 
      combinations[number] += 1 

    # now do all verticals 
    # note that if the grid is really square, grid[0] will give an accurate width of all grid[y][] rows 
    for x in range(len(grid[0])): 
    digits = [] 
    for y in range(len(grid)): 
     digits.append(grid[y][x]) 
     # for every possible starting point... 
     for q in range(1,len(digits)): 
     number = merge(digits[q:]) 
     if number <= sqk: 
      combinations[number] += 1 

    # the longer axis (x or y) in both directions will contain every possible diagonal 
    # e.g. x is the longer axis here (using random characters to more easily distinguish idea): 
    # [1 2 3 4] 
    # [a b c d] 
    # [. , $ !] 
    # 'a,' can be obtained by reversing the diagonal starting on the bottom and working up and to the left 
    # this means that every set must be reversed as well 
    if len(grid) > len(grid[0]): 

    # for each y, grab top and bottom in each of two diagonal directions, for a total of four sets, 
    # and include the reverse of each set 
    for y in range(len(grid)): 

     digitsul = [] # origin point upper-left, heading down and right 
     digitsur = [] # origin point upper-right, heading down and left 
     digitsll = [] # origin point lower-left, heading up and right 
     digitslr = [] # origin point lower-right, heading up and left 

     revx = len(grid[y])-1 # pre-adjust this for computing reverse x coordinate 

     for deltax in range(len(grid[y])): # this may go off the grid, so check bounds 
     if y+deltax < len(grid): 
      digitsul.append(grid[y+deltax][deltax]) 
      digitsll.append(grid[y+deltax][revx - deltax]) 

      for q in range(1,len(digitsul)): 
      number = merge(digitsul[q:]) 
      if number <= sqk: 
       combinations[number] += 1 
      number = merge_reverse(digitsul[q:]) 
      if number <= sqk: 
       combinations[number] += 1 

      for q in range(1,len(digitsll)): 
      number = merge(digitsll[q:]) 
      if number <= sqk: 
       combinations[number] += 1 
      number = merge_reverse(digitsll[q:]) 
      if number <= sqk: 
       combinations[number] += 1 

     if y-deltax >= 0: 
      digitsur.append(grid[y-deltax][deltax]) 
      digitslr.append(grid[y-deltax][revx - deltax]) 

      for q in range(1,len(digitsur)): 
      number = merge(digitsur[q:]) 
      if number <= sqk: 
       combinations[number] += 1 
      number = merge_reverse(digitsur[q:]) 
      if number <= sqk: 
       combinations[number] += 1 

      for q in range(1,len(digitslr)): 
      number = merge(digitslr[q:]) 
      if number <= sqk: 
       combinations[number] += 1 
      number = merge_reverse(digitslr[q:]) 
      if number <= sqk: 
       combinations[number] += 1 

    else: 

    # for each x, ditto above 
    for x in range(len(grid[0])): 

     digitsul = [] # origin point upper-left, heading down and right 
     digitsur = [] # origin point upper-right, heading down and left 
     digitsll = [] # origin point lower-left, heading up and right 
     digitslr = [] # origin point lower-right, heading up and left 

     revy = len(grid)-1 # pre-adjust this for computing reverse y coordinate 

     for deltay in range(len(grid)): # this may go off the grid, so check bounds 
     if x+deltay < len(grid[0]): 
      digitsul.append(grid[deltay][x+deltay]) 
      digitsll.append(grid[revy - deltay][x+deltay]) 

      for q in range(1,len(digitsul)): 
      number = merge(digitsul[q:]) 
      if number <= sqk: 
       combinations[number] += 1 
      number = merge_reverse(digitsul[q:]) 
      if number <= sqk: 
       combinations[number] += 1 

      for q in range(1,len(digitsll)): 
      number = merge(digitsll[q:]) 
      if number <= sqk: 
       combinations[number] += 1 
      number = merge_reverse(digitsll[q:]) 
      if number <= sqk: 
       combinations[number] += 1 

     if x-deltay >= 0: 
      digitsur.append(grid[deltay][x-deltay]) 
      digitslr.append(grid[revy - deltay][x - deltay]) 

      for q in range(1,len(digitsur)): 
      number = merge(digitsur[q:]) 
      if number <= sqk: 
       combinations[number] += 1 
      number = merge_reverse(digitsur[q:]) 
      if number <= sqk: 
       combinations[number] += 1 

      for q in range(1,len(digitslr)): 
      number = merge(digitslr[q:]) 
      if number <= sqk: 
       combinations[number] += 1 
      number = merge_reverse(digitslr[q:]) 
      if number <= sqk: 
       combinations[number] += 1 

    # now filter for squares only 
    return [i for i in range(0,k+1) if combinations[i*i] > 0] 

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

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

Это не будет обрабатывать все комбинации и не будет упаковываться так же сильно, как и всякое возможное расположение и вычисление того, сколько квадратов покрыто, поэтому некоторые могут быть пропущены, но по сравнению с O ((N * M)!), Это алгоритм на самом деле завершится в вашей жизни (я бы оценил несколько минут на приличном компьютере - больше, если вы распараллеливаете проверку места размещения).