организовать восемь последовательных числа в матрице, так что никакие два числа не являются смежными

Question

Необходимость числа от 1 до 8 в следующей схеме таким образом, что не два числа в соседней ячейке не являются последовательными друг с другом Выкройка:

 * 
    *** 
    *** 
    * 

Где каждый * содержит число от 1 до 8, а два соседних * не являются кондуктивным числом.

Answer 1

Предполагая, что соседи по горизонтали и по вертикали (не по диагонали), жадным решением было бы переставить, пока не найдете решение. Ваш массив достаточно мал, поэтому вам нужно немного больше, чем 24 попытки в среднем найти совпадение.

import java.util.Random; 

public class EightPattern { 
    private static Random rnd = new Random(); 

    /* 
    * -0- 
    * 123 
    * 456 
    * -7- 
    */ 
    private static boolean isOK(int[] array) { 
     if (  Math.abs(array[0] - array[2]) == 1 
       || Math.abs(array[1] - array[2]) == 1 
       || Math.abs(array[2] - array[3]) == 1 
       || Math.abs(array[1] - array[4]) == 1 
       || Math.abs(array[2] - array[5]) == 1 
       || Math.abs(array[3] - array[6]) == 1 
       || Math.abs(array[4] - array[5]) == 1 
       || Math.abs(array[5] - array[6]) == 1 
       || Math.abs(array[5] - array[7]) == 1) { 
      return false; 
     } 
     return true; 
    } 

    //shuffle until you find an isOK solution 
    public static void patternShuffle(int[] array) { 
     do { 
      shuffleArray(array); 
     }while(!isOK(array)); 
    } 


    //Fisher–Yates shuffle 
    static void shuffleArray(int[] ar) { 
     for (int i = ar.length - 1; i > 0; i--) { 
      int index = rnd.nextInt(i + 1); 
      int a = ar[index]; 
      ar[index] = ar[i]; 
      ar[i] = a; 
     } 
    } 

    private static void printPattern(int[] array) { 
     System.out.println(" " + array[0]); 
     System.out.println("" + array[1] + array[2] + array[3]); 
     System.out.println("" + array[4] + array[5] + array[6]); 
     System.out.println(" " + array[7]); 
    } 

    public static void main(String args[]) { 
     int[] a = new int[]{1,2,3,4,5,6,7,8}; 
     patternShuffle(a); 
     printPattern(a); 
    } 
} 

Answer 2

Если вы попробуете все возможные варианты, вам нужно попробовать 8! варианты, но если вы думаете, что заметили, что есть две ячейки с семью соседями (где вам нужно заполнить 1 и 8 в любом порядке). Эти клетки не могут быть заполнены никаким числом от 2 до 7, потому что каждое число k имеет два соседства k + 1 и k-1, но у нас остается только одна ячейка, оставшаяся для заполнения соседом.

 
_ 2 _ 
5 8 6 
3 1 4 
_ 7 _