Jane Street puzzle writeup: Number Cross 5

Overview

This puzzle is about solving an 11 by 11 grid containing 9 different bordered regions.

Source: https://www.janestreet.com/puzzles/may-2025-update.png

Regions:

Start by inserting numbers 1-9 into the different regions. Not all numbers in the set 1-9 need to be used.

1. Each region needs to contain the same digit throughout

2. Neighboring regions must contain different digits

The same number can be reused in non-adjacent regions (Restriction 2)

Tiles:

Next, tiles need to be placed into the grid.

1. Tiles can’t be placed on yellow “locked” spaces

2. Tiles can’t be placed directly above or below another tile

3. Tiles need to be at least 2 spaces apart horizontally

   • This ensures that each segment between tiles forms a valid number (minimum two digits)

   • Tiles can be placed directly next to the grid borders

   • Tiles cannot be placed one space away from the grid borders since this one space cannot form a valid number

When a tile is placed, it displaces the digit it covers. This displaced value is absorbed by its four orthogonal neighbors. A few additional constraints:

• No space can be incremented past 9

• Yellow “locked” spaces cannot be changed => They always retain the original region-digit

• As a result of this distribution-process two spaces in different regions are allowed to have the same digit

After this operation is complete no numbers (formed between tiles) are allowed to repeat within the grid.

Clues:

Clues are written on each row. Each number (consecutive digits between tiles) needs to satisfy the given clue.

Solution:

Once the grid is complete and all clues are satisfied, the solution is the sum of the final numbers in the grid.

Full puzzle: https://www.janestreet.com/puzzles/number-cross-5-index/

Preliminary Analysis

A closer look at the puzzle allows for some early deductions:

• The blue region has to be mapped to the number 2, since the locked spaces in the second row cannot be altered. Thus they must still have their original value and that value must satisfy the clue “product of digits is 20”. The prime factorization of 20 is 2×2×5.

• This also helps to fix the tile positions in row 09: ◻️◻️⬛◻️◻️◻️⬛◻️◻️◻️⬛
  Since spaces 4 and 5 are locked and cannot contain tiles, any number spanning those cells must begin and end with a 5 either before or after these locked cells.
  If space 3 were not a tile the number would stretch to at least four digits that is too long to produce a product of 20 using only the digits 2 and 5.
  Therefore, space 3 must be a tile to constrain the segment length. This logic also determines the placement of the remaining tiles in the row.

• Consequently, the red region must be either 4 or 5.
  Since the clue for the first number is "product of digits is 20" and we already have 2 as one digit.
  The only two-digit combinations left are 4 × 5 or 5 × 4.

• The green region must then be 1.
  This deduction results from looking at the next clue which is "product of digits is 25."
  The prime factorization of 25 is 5 × 5.
  Valid numbers for that product include 55, 551, 155, etc.
  Since we've already allocated 4 or 5 to red the only available digit that fits reasonably in this pattern and remains unallocated is 1. Assigning 1 to green allows the number groupings to work—while also ensuring compliance with the rule that no digits may repeat within the completed grid.

Algorithmic Solution

Overview

Now with the preliminary analysis completed it is time to start thinking about the algorithm.

I opted for a relatively straight forward solution. That being:

Pre-Solving:

1. Generate All Possible Tile Arrangements

2. Filter Legal Arrangements
   For each row, discard any illegal configurations (tiles on locked spaces)

Solver:

1. Generate Region-to-Digit Mappings
   Enumerate all valid mappings of regions to digits 1–9 with respect to the adjacency rules.

2. Iterate Over All Combinations
   Apply all possible combinations of tile arrangements and mappings for the row

3. Try to solve each number in the row
   For each segment of digits between tiles:

   1. Identify the start and end of the number to solve

   2. Identify the tiles below, left and right of the number

   3. Identify which digits will be altered by each tile.

   4. Try all possible combinations of tile-values

   5. Check if the number is valid using the clue

4. Validate the Row
   If all numbers in the row are valid append the row to a list of solved rows

5. Repeat for all rows

Generating possible tile states

Possible tile arrangements are simply generated by counting in binary to 2048 (2^11) and rejecting non valid arrangements

def bit_list(n, length=11):
  bit_string = bin(n)[2:] # Cut off the "0b"
  bit_string = bit_string[::-1] # Flip the string to convert to big endian
  return [int(digit) for digit in bit_string] + [0] * (length - len(bit_string)) # Add padding

def is_valid_arrangement(tile_map):
  for i in range(len(tile_map)-1):
    # Skip if there is no tile
    if tile_map[i] == 0:
      continue


    # If a tile is at the second position, there is no space for two spaces
    if i == 1:
      return False


    # If a tile is at the second to last position, there is no space for two spaces
    if i == len(tile_map) - 2:
      return False

    # Check the offsets around the tile
    for offset in [-2, -1, 1, 2]:
      if i + offset < 0 or i + offset >= len(tile_map):
        continue

      if tile_map[i + offset] == 1:
        return False

  # If there are no conflicts, the alignment is valid
  return True

arrangements = []

for i in range(pow(2,11)):
  bits = bit_list(i)
  if is_valid_arrangement(bits):
    arrangements.append(bits)

Continuing to generating all arrangements per row:

# Map of the locked spaces
BOARD_MASK = [[0] * 11 for _ in range(11)]

BOARD_MASK[1][4] = 1
BOARD_MASK[2][4] = 1
BOARD_MASK[2][5] = 1
BOARD_MASK[3][5] = 1
BOARD_MASK[4][5] = 1
BOARD_MASK[4][6] = 1
BOARD_MASK[5][5] = 1

BOARD_MASK[3][1] = 1
BOARD_MASK[4][1] = 1
BOARD_MASK[4][2] = 1

BOARD_MASK[7][8] = 1
BOARD_MASK[7][9] = 1
BOARD_MASK[8][9] = 1

BOARD_MASK[8][4] = 1
BOARD_MASK[9][4] = 1
BOARD_MASK[9][3] = 1

#####################

def is_valid_alignment_with_row(bits, row):
  # Check if there is no 1 in the board mask
  for i in range(len(bits)):
    if bits[i] == 1 and BOARD_MASK[row][i] == 1:
      return False

arrangements_for_row = []

for i in range(11):
  valid_alignments = []
  for j in range(len(arrangements)):
    if is_valid_alignment_with_row(arrangements[j], i):
      valid_alignments.append(arrangements[j])
  arrangements_for_row.append(valid_alignments)

Generating board mappings:

# Representaion of the different regions of the board (the other way around to make it easier to work with)
INDEX_BOARD = [
  [5,5,8,8,8,8,8,8,5,5,5],
  [5,5,5,5,5,5,5,5,5,5,5],
  [5,5,5,5,6,5,6,7,7,7,7],
  [1,5,6,6,6,6,6,6,6,7,7],
  [1,5,6,6,1,1,4,4,6,4,4],
  [1,1,1,1,1,4,4,4,4,4,3],
  [1,2,2,1,2,4,4,3,3,4,3],
  [1,2,2,1,2,4,3,3,3,3,3],
  [1,1,2,2,2,2,3,3,3,0,3],
  [0,1,0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0], 
]

# A mapping of region-index to neighboring region indices (from which the original region needs to be different)
difference_mapping = {
  0: [1,2,3],
  1: [0,2,4,5,6],
  2: [0,1,3,4],
  3: [0,2,4],
  4: [1,2,3,6,7],
  5: [1,6,7,8],
  6: [1,4,5,7],
  7: [4,5,6],
  8: [5],
}

from itertools import product

mappings_cache = {}

def generate_mappings(fixed, variable):
  if any(idx in fixed for idx in variable):
    raise ValueError("Variable indices contain already fixed indices.")

  key = (tuple(sorted(variable)), tuple(sorted(fixed.items())))
  if key in mappings_cache:
    return mappings_cache[key]

  all_digits = list(range(1, 10))
  results = []

  for digits in product(all_digits, repeat=len(variable)):
    candidate = dict(zip(variable, digits))
    candidate.update(fixed)

    valid = True
    for i in candidate:
      for j in candidate:
        if i != j:
          if (j in difference_mapping.get(i, [])) or (i in difference_mapping.get(j, [])):
            if candidate[i] == candidate[j]:
              valid = False
              break
      if not valid:
          break

    if valid:
      results.append(candidate)

  mappings_cache[key] = results
  return results

This is a function for generating mapping from region indices to numbers 1-9 respecting the difference rule and allowing for some indices to be fixed.

Solving a single number

def solve_number(board, number_indices, number_index, row_index, condition, down):
  """
  Tries every possible tile state for a given number section in a row and returns
  a list of boards that satisfy the condition.

  Args:
    board         : The current board.
    number_indices: A list of dictionaries with start and end indices for numbers.
    number_index  : The index of the current number in number_indices.
    row_index     : The row in which the number is located.
    condition     : A function that checks if the number is valid.
    down          : A boolean flag to inform tile placement direction.

  Returns:
    A list of boards with valid distributions or None if number_index is out of range.
  """
  if number_index >= len(number_indices):
    return None

  # Determine the section of the number we are going to solve.
  current_number_range = number_indices[number_index]
  number_start = current_number_range["start"]
  number_end = current_number_range["end"]

  solutions = []

  # Determine tile positions that may affect this number.
  block_locations = find_block_locations_for_number(board, number_start, number_end, row_index, down)
  replaced_numbers = extract_remaining_numbers(board, block_locations)

  current_solving_number = board.get_section(row_index, number_start, number_end)
  possible_tile_states = nested_count(replaced_numbers)
  mapping = map_block_locations_to_number(board, row_index, block_locations, number_start, number_end)

  for tile_state in possible_tile_states:
    candidate_number = current_solving_number.copy()
    invalid_state = False

    # Apply each tile state increment to the candidate number.
    for idx, tile_value in enumerate(tile_state):
      num_index = mapping[idx]["num_index"]
      index_into_row = number_start + num_index

      if board.is_locked_space(row_index, index_into_row):
        invalid_state = True
        break

      candidate_number[num_index] += tile_value
      if candidate_number[num_index] > 9:
        invalid_state = True
        break

    if invalid_state:
      continue

    # If candidate number meets the condition, try to distribute the tiles.
    if condition(candidate_number):
      sol_board = board.copy()
      distribution_error = False

      for idx, tile_value in enumerate(tile_state):
        tile_x, tile_y = mapping[idx]["coords"]
        direction = mapping[idx]["direction"]
        num_index = mapping[idx]["num_index"]
        index_into_row = number_start + num_index

        if board.is_locked_space(row_index, index_into_row):
          distribution_error = True
          break

        sol_board.set_distribution(tile_x, tile_y, direction, tile_value)

      if distribution_error:
        continue

      # If this is the last number in the row, mark the row solved and update locked tiles.
      if number_index == len(number_indices) - 1:
        sol_board.solved[row_index] = True
        for tile_idx, tile in enumerate(sol_board.tile_board[row_index]):
          if tile == 1:
            tile_info = sol_board.tile_info_board[row_index][tile_idx]
            if tile_info["remaining"] != 0:
              try:
                direction = "down" if down else "up"
                sol_board.set_distribution(row_index, tile_idx, direction, tile_info["remaining"])
              except Exception:
                sol_board.solved[row_index] = False
                distribution_error = True
                break

      if distribution_error:
        continue

      solutions.append(sol_board)

  return solutions

This function is responsible for solving a number within a row. It does this by finding the bounds of the number and figuring out which tiles affect which digits. Subsequently it tries all possible combinations of the tiles until the given condition is met.

Solving a row

def solve_row(board, number_indices, row_index, current_number_index, condition, down):
  boards = solve_number(board, number_indices, current_number_index, row_index, condition, down)

  if boards == None:
    return []
  if len(boards) == 0:
    return []

  results = []

  for i in range(len(boards)):
    b = boards[i]

    if b.solved[row_index]:
      numbers = []

      rules_satisfied = True


      # Check if there are no duplicate numbers in any solved row
      for index in range(len(b.number_board)):
        if b.solved[index] == False:
          continue


        _number_indices = b.row_get_number_indices(index)

        for j in range(len(_number_indices)):
          number = b.get_number(index, _number_indices[j]["start"], _number_indices[j]["end"])
          if number in numbers:
            rules_satisfied = False
          numbers.append(number)

      for j in range(len(b.solved)):
        # Check if there are no unsatisfied tiles in the already solved rows
        if b.solved[j] == True and j != row_index:
          for x in range(len(b.tile_info_board[j])):
            if b.tile_board[j][x] == 1:
              if b.tile_info_board[j][x]["remaining"] != 0:
                rules_satisfied = False
                raise Exception("Tile is not satisfied")

      if not rules_satisfied:
        continue

      results.append(b)
    else:
      results += solve_row(b, number_indices, row_index, current_number_index + 1, condition, down)
  return results

This function is used for solving a row. It works by calling solve_number until the row is solved. All solved boards are returned as results if the board has no unsatisfied tiles and no duplicates.

Solution:

10: 🟨3️⃣4️⃣2️⃣2️⃣2️⃣5️⃣🟨3️⃣2️⃣4️⃣
09: 5️⃣4️⃣🟨2️⃣2️⃣5️⃣🟨2️⃣5️⃣2️⃣🟨
08: 🟨5️⃣3️⃣4️⃣3️⃣🟨6️⃣5️⃣🟨2️⃣6️⃣
07: 7️⃣3️⃣6️⃣🟨3️⃣2️⃣🟨5️⃣4️⃣4️⃣🟨
06: 🟨5️⃣5️⃣5️⃣🟨2️⃣2️⃣🟨8️⃣1️⃣6️⃣
05: 5️⃣5️⃣🟨5️⃣5️⃣1️⃣🟨1️⃣5️⃣5️⃣🟨
04: 🟨3️⃣6️⃣7️⃣4️⃣4️⃣1️⃣2️⃣🟨1️⃣5️⃣
03: 7️⃣3️⃣7️⃣🟨9️⃣6️⃣9️⃣🟨9️⃣9️⃣🟨
02: 3️⃣4️⃣🟨4️⃣6️⃣3️⃣6️⃣8️⃣🟨8️⃣9️⃣
01: 5️⃣3️⃣5️⃣9️⃣3️⃣🟨5️⃣9️⃣9️⃣5️⃣🟨
00: 🟨4️⃣7️⃣🟨8️⃣8️⃣7️⃣🟨4️⃣3️⃣3️⃣

10: 342225 + 324
09: 54 + 225 + 252
08: 5343 + 65 + 26
07: 736 + 32 + 544
06: 555 + 22 + 816
05: 55 + 551 + 155
04: 3674412 + 15
03: 737 + 969 + 99
02: 34 + 46368 + 89
01: 53593 + 5995
00: 47 + 887 + 433

342225 + 324 + 54 + 225 + 252 + 5343 + 65 + 26 + 736 + 32 + 544 + 555 + 22 + 816 + 55 + 551 + 155 + 3674412 + 15 + 737 + 969 + 99 + 34 + 46368 + 89 + 53593 + 5995 + 47 + 887 + 433

Source Code:

https://gist.github.com/Addelec/266b70900279cbe4b64652c87d6ea156