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 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 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 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 at 1:00
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$ – Dmitry Kamenetsky Feb 24 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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