GVSU REU 2019

Can you find a solution?

Extremal Numbrix Puzzles

Numbrix puzzles are written by Marilyn vos Savant (of Ask Marilyn fame) and have appeared in Parade Magazine since 2008. Numbrix, similar to Sudoku, is played on a 9x9 grid. Some “clues” are given, that is, numbers that are filled in on certain cells of the grid. The goal is to fill in the rest of the numbers in such a way that the numbers 1 through 81 create a path through the grid. For example, the number 5 should appear to the left, right, above, or below the number 4. We will consider an extremal problem in a more general case. The puzzle will be an mxn grid for some integers m and n at least 1 and we use the integers 1 through mn.

We say a puzzle is defined if there exists a unique solution to the puzzle. Does there exist a unique solution to the puzzle on the left?

What will the research involve?

One overall goal of the project is to find the minimum number of clues necessary to define a Numbrix puzzle. The project will first involve generating examples where some coding may be helpful (most likely in Python or Sage). We will explore connections to other topics in graph theory and combinatorics - for example, one connection is to Hamiltonian circuits in grid graphs.

Desirable Experiences for Applicants

Applicants should have an introduction to proofs course as well as some familiarity with graph theory (a full course in graph theory is not necessary). It would be advantageous to have some experience in coding. The main qualifications are intellectual curiosity and perseverance.

Here is one solution. Can you find others?