0
$\begingroup$

This puzzle is an extension of this one: Minimize the longest King chain on a 5x5 binary board

Given a grid filled with numbers, we define a King chain to be a path on the grid such that:

  1. The path can be traversed with chess King's moves (moving to one of 8 adjacent cells at a time),
  2. The numbers on the path are all equal, and
  3. The path does not visit any cell more than once.

The length of a King chain is the number of cells visited by the King.

Can you find a 7x7 grid filled with zeros and ones, such that every pair of zeros and every pair of ones are connected via some King chain, and the longest King chain is as small as possible?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Do you have reason to believe that there is a 'nice' solution to this? If not, this seems more like a computer programming challenge than a puzzle. $\endgroup$
    – Deusovi ♦
    Feb 24, 2021 at 0:49
  • $\begingroup$ I have found some 'nice' solutions to this puzzle, although I haven't proven their optimality. $\endgroup$
    – Dmitry Kamenetsky
    Feb 24, 2021 at 0:52
  • 3
    $\begingroup$ You ask for optimality in the question, though - so something can't be a "solution" unless it is optimal. $\endgroup$
    – Deusovi ♦
    Feb 24, 2021 at 0:53
  • $\begingroup$ I've worded it such that sub-optimal solutions are also accepted. I want to see how good a solution we can find. $\endgroup$
    – Dmitry Kamenetsky
    Feb 24, 2021 at 1:00

1 Answer 1

Reset to default
4
$\begingroup$

Using a modified version of Albert Lang's method on the previous question, the best I've managed so far is

12

As follows

1 0 1 0 1 0 1
1 0 1 0 1 0 1
1 0 1 0 1 0 1
0 1 0 1 0 1 0
0 1 0 1 0 1 0
0 1 0 1 0 1 0
1 1 0 1 0 1 0

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is the nice solution I had in mind. I have found other solutions with the same cost, but none with lower cost. $\endgroup$
    – Dmitry Kamenetsky
    Feb 24, 2021 at 12:36

Your Answer

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

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