How to solve 5x5 grid with 16 diagonals?

Question

I have a grid 5x5 and I have to fill 16 little squares with a diagonal

Rules

• You cannot place more than 1 diagonal in each square
• The diagonals cannot touch each other (example bellow)

Click here to view the solution

But what I seek here is a mathematical solution for this puzzle, I don't even know where to start looking for information.

Can someone explain how do I solve this puzzle using equations?

Answer 1

Think of it this way: You have a 5x5 array, and you need to fill it with values 0, 1, or -1, with three restrictions:

1. The cells sharing an edge with a cell with a $\pm 1$ cannot contain a $\mp 1$.
2. If a cell contains a 1, the adjacent cells to the top-left and bottom-right cannot also contain a 1.
3. If a cell contains a -1, the adjacent cells to the bottom-left and top-right cannot also contain a -1.

Here, cells containing a "1" have a diagonal running top-left to bottom-right, and cells containing a "-1" have a diagonal running the other way. Cells containing 0 do not have a diagonal at all.

So, for the example grid you provide, you start with the grid:

$$ \begin{matrix}0&0&-1&0&0\\0&-1&0&-1&1\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{matrix} $$

I don't think there's "a mathematical solution" to it - that is, I doubt that one could immediately find the "right answer" without some level of trial and error. But it does give a good starting point to automating the search, if you want to try solving it computationally.

Answer 2

If we encode the solution grid ($5 \times 5$) as a vector (of length $25$) and denote the diagonals / as 1 and \ as -1, e.g., with blank space in a cell as 0, we can use backtracking to solve the 16-diagonals problem.

Starting from empty solution vector the solution can be recursively extended with backtracking, at each stage checking if the partial solution is valid (i.e., none of the diagonals touch) with the function can_be_extended_to_solution() as shown in the next code snippet, otherwise discard the current solution.

The following figure shows what the function can_be_extended_to_solution() should check to ensure that there are no touching diagonals in the solution.

The function num_diag() counts the number of diagonals present in the solution so far, we can terminate if we have $16$ diagonals.

def can_be_extended_to_solution(solution_vector):
    # check if any of the diagonals touch in the solution sol far
    if ∃ a pair of touching diagonals in the solution:
       return False
    return True

def extend_solution_with_backtracking(solution_vector, n):
  if len(solution_vector) == 25 and num_diag(solution_vector) == 16:
      # found solution!
      print(solution_vector) 
      exit()
  for k in range(-1,2): 
    # try /, \ or blank in the next position
    solution_vector.append(k)
    if can_be_extended_to_solution(solution_vector):
        extend_solution_with_backtracking(grid_vec, n)            
    solution_vector.pop()

def num_diag(solution_vector):
    # return number of / or \ diagonals present in the solution
    return sum([1 for x in solution_vectorif x != 0])

The following figure shows a solution obtained with the above backtracking algorithm.

The following animation shows how the partial solutions can be extended using backtracking: