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?

$\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$ 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$ Feb 24, 2021 at 1:00

1 Answer 1

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

$\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$ 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.