5
$\begingroup$

Rodolfo Kurchan created a wonderful new grid puzzle called One Up that you can play on his website. There is one main rule:

Each horizontal and vertical sequence of N cells between walls, must contain every number between 1 and N, in some order.

For example, here are the possible sequences in the following 4x4 grid:

enter image description here enter image description here

There are 5 ways to place walls on an empty 2x2 grid, such that they produce a One Up puzzle with a unique solution:

enter image description here

How many ways are there to place walls on an empty 3x3 grid to get a One Up puzzle with a unique solution?

$\endgroup$
4
  • $\begingroup$ I don’t think this is a solve by hand kind of puzzle lol. $\endgroup$
    – PDT
    Commented May 4 at 14:50
  • $\begingroup$ Probably not, but I have been proven wrong in the past. $\endgroup$ Commented May 4 at 14:57
  • 1
    $\begingroup$ What if we consider only grids that are connected, i.e., that don't have some sections completely blocked off by walls? Not only does that make the resulting puzzles more aesthetically pleasing imo (since a disconnected grid is really two separate puzzles) but it also makes it more manageable to count them by hand. $\endgroup$
    – Carmeister
    Commented May 5 at 12:28
  • $\begingroup$ @Carmeister that is a good idea. $\endgroup$ Commented May 5 at 15:02

2 Answers 2

3
$\begingroup$

I think the answer for $3\times3$ is

203.

For $4\times4$, I get

44293.

I generated all possible sets of walls ($2^{12}$ for $3\times3$ and $2^{24}$ for $4\times4$) and ran a back-tracking algorithm for each of those. For $5\times5$ there are $2^{40}$ sets of walls, so something smarter is needed to go any further.

$\endgroup$
3
  • $\begingroup$ Great results! Unfortunately I don't have a program to verify them yet. $\endgroup$ Commented May 5 at 15:04
  • 2
    $\begingroup$ In order to have a solution, horizontal walls should enforce the same number of 1s as the vertical ones, which means that the counts of horizontal and vertical walls are equal. This alone reduces the number of candidates to check from $2^{2n(n-1)}$ to $_{2n(n-1)}C_{n(n-1)}$. Enforcing the multisets of space lengths to be equal is harder to analyze mathematically, but for $n=5$, the count is $15334080384 \approx 1.53 \times 10^{10}$. It's still quite a lot though. $\endgroup$
    – Bubbler
    Commented May 7 at 0:35
  • 1
    $\begingroup$ Answer confirmed now. $\endgroup$ Commented May 7 at 11:36
4
$\begingroup$

I can confirm Pontus's answers for $3 \times 3$ and $4 \times 4$. I used Python for enumerating possible boards and Z3 for checking if each board has a unique solution:

def puzz126600():
    class DisjointSet(object):
        def __init__(self, n):
            self.parent = [*range(n)]
            self.rank = [0] * n
        
        def find(self, n):
            while self.parent[n] != n:
                self.parent[n] = self.parent[self.parent[n]]
                n = self.parent[n]
            return n
        
        def union(self, n1, n2):
            n1 = self.find(n1)
            n2 = self.find(n2)
            if n1 == n2: return False
            if self.rank[n1] < self.rank[n2]:
                n1, n2 = n2, n1
            self.parent[n2] = n1
            if self.rank[n1] == self.rank[n2]:
                self.rank[n1] += 1
            return True

    import z3
    from itertools import product
    from collections import defaultdict
    def partitions(n):
        dp = [[[]]]
        for l in range(1, n+1):
            cur = []
            for first in range(1, l+1):
                rest = l - first
                for r in dp[rest]:
                    cur.append([first] + r)
            dp.append(cur)
        return dp[-1]

    def grid_printer(n, horizontal, vertical):
        canvas_row1 = '+-' * n + '+'
        canvas_row2 = '| ' * n + '|'
        canvas = [list(row) for row in [canvas_row1, canvas_row2] * n + [canvas_row1]]
        for r in range(n):
            start_idx = 0
            for width in horizontal[r]:
                canvas_r = r * 2 + 1
                for c in range(start_idx, start_idx + width - 1):
                    canvas_c = c * 2 + 1
                    canvas[canvas_r][canvas_c + 1] = ' '
                start_idx += width
        for c in range(n):
            start_idx = 0
            for width in vertical[c]:
                canvas_c = c * 2 + 1
                for r in range(start_idx, start_idx + width - 1):
                    canvas_r = r * 2 + 1
                    canvas[canvas_r + 1][canvas_c] = ' '
                start_idx += width
        for row in canvas:
            print(''.join(row))

    def solve(n, connected_only=False):
        parts = partitions(n)
        frag_sets = defaultdict(list)
        for grid in product(parts, repeat=n):
            counts = [0] * n
            for row in grid:
                for part in row:
                    counts[part-1] += 1
            frag_sets[tuple(counts)].append(grid)
        # print(sum(len(grids) ** 2 for grids in frag_sets.values()))
        answer = 0
        cases_checked = 0
        for grids in frag_sets.values():
            for horizontal in grids:
                for vertical in grids:
                    dset = DisjointSet(n * n)
                    components = n * n
                    solver = z3.SolverFor('QF_FD')
                    grid = [[z3.Int(f'a{r}{c}') for c in range(n)] for r in range(n)]
                    for r in range(n):
                        start_idx = 0
                        for width in horizontal[r]:
                            for c in range(start_idx, start_idx + width - 1):
                                components -= dset.union(r * n + c, r * n + c + 1)
                            space = [grid[r][c] for c in range(start_idx, start_idx + width)]
                            for v in space:
                                solver += 1 <= v
                                solver += v <= width
                            solver += z3.Distinct(*space)
                            start_idx += width
                    for c in range(n):
                        start_idx = 0
                        for width in vertical[c]:
                            for r in range(start_idx, start_idx + width - 1):
                                components -= dset.union(r * n + c, (r + 1) * n + c)
                            space = [grid[r][c] for r in range(start_idx, start_idx + width)]
                            for v in space:
                                solver += 1 <= v
                                solver += v <= width
                            solver += z3.Distinct(*space)
                            start_idx += width
                    if connected_only and components != 1: continue
                    if solver.check() == z3.sat:
                        model = solver.model()
                        solution = [[model.eval(v) for v in row] for row in grid]
                        solver += z3.Or(*[v != sol for vrow, solrow in zip(grid, solution) for v, sol in zip(vrow, solrow)])
                        if solver.check() == z3.unsat:
                            #print('unique', horizontal, vertical)
                            #grid_printer(n, horizontal, vertical)
                            answer += 1
            cases_checked += len(grids) ** 2
            print(f'{cases_checked} cases checked')
        print(answer)
    
    solve(3, False)
    solve(4, False)

For an additional challenge by Carmeister (the ones where all cells are connected), I found

exactly 2 different grids up to symmetry:

Analysis:

If one of the rows has a (1,1,1) partition, one of the columns must be too. (In order to have three chunks of ones without a (1,1,1), all three columns must be either (1,2) or (2,1), but the two remaining rows cannot be divided into three chunks of 2.) Then the cell at the intersection of such row and column is isolated.

On the other hand, if all rows are (3) i.e. no dividers at all, all columns are also (3) and there are 6 solutions in this board. Therefore, at least one row and one column are either (1,2) or (2,1), and the rest are (3).

If two rows are (1,2), i.e. a divider on the same side, there are two 1s forced on the first column, so there must be a divider on it. Then one or two cells are isolated in all cases. Therefore, a valid solution has at most one (1,2) and one (2,1) for its rows, and the same goes for columns.

The rest was mental case bashing on the remaining cases. The answer was cross-checked by running solve(3, True) in the code above.

$\endgroup$
1
  • $\begingroup$ Awesome work! I am surprised that there are so few connected grids. $\endgroup$ Commented May 7 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.