Mar-12-2019, 06:20 PM
I found this problem in a programming forum Ohjelmointiputka:
https://www.ohjelmointiputka.net/postit/...nus=ahdruu and
https://www.ohjelmointiputka.net/postit/...us=ahdruu2
Somebody said that there is a solution found by a computer, but I was unable to find a proof.
Find the smallest rectangle digits such that one can read the squares of the numbers 1, 2, ..., 100.
Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.
But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a matrix that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.
What kind of algorithm will find the matrix?
I saw from https://stackoverflow.com/questions/3382...ng-problem that the following program solves the problem in the case 11x11:
https://www.ohjelmointiputka.net/postit/...nus=ahdruu and
https://www.ohjelmointiputka.net/postit/...us=ahdruu2
Somebody said that there is a solution found by a computer, but I was unable to find a proof.
Find the smallest rectangle digits such that one can read the squares of the numbers 1, 2, ..., 100.
Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.
But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a matrix that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.
What kind of algorithm will find the matrix?
I saw from https://stackoverflow.com/questions/3382...ng-problem that the following program solves the problem in the case 11x11:
# # An attempt to solve a nice problem from SO using a random search approach # # The problem is to place the squares of all numbers from 1 to 100 in # a 11x11 grid writing them either horizontally, vertically or in diagonal. # 11*11 is only 121 and this means that the required packing is very tight # (the total number of digits is 358, giving that on average each grid # cell needs to be used for 2.95 different square numbers). # # Do whatever you want with this code, just don't blame me if it doesn't # do what you think or if it even doesn't do what I say it does. # # Andrea "6502" Griffini # import random, time, sys N = 11 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)] + ["*"*N for x in xrange(N)] + ["*"*x for x in xrange(1, N)] + ["*"*x for x in xrange(N, 0, -1)] + ["*"*x for x in xrange(1, N)] + ["*"*x for x in xrange(N, 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, (N + x, y)) add_line_of(x, y, (2*N + (x + y), x - max(0, x + y - N + 1))) add_line_of(x, y, (2*N + 2*N-1 + (x + N-1 - y), x - max(0, x + (N-1 - y) - N + 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, N-1) setValue(x, y, random_digit()) best = None attempts = k while attempts > 0: attempts -= 1 x = random.randint(0, N-1) y = random.randint(0, N-1) old = 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: setValue(x, y, old) 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(N): for x in xrange(N): setValue(x, y, best[1][y][x]) x = do_search(100000, N) 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[:]But how this can be generalized to solve the problem in non-square cases? I heard that the squares if integers 1–100 can be put to the grid of 117 elements (https://www.ohjelmointiputka.net/postit/...us=ahdruu2) . And how this code can be simplified?