Создание массива целых чисел без нарушения ограничений

Question

Я борюсь с проблемой часами. Это проблема ограничения ограничений. Позвольте мне описать это на простом примере:

Предположим, что существует массив целых чисел длиной 8. Каждая ячейка может принимать определенные значения. Первые 4 ячейки могут принимать 0, 1 или 2, а другая половина может принимать 0 или 1. Эти 3 массива могут быть некоторыми примерами.

{2,1,0,2,1,1,0,1} 
{2,2,1,0,0,1,0,0} 
{0,0,0,2,0,0,0,1} 

Однако есть некоторые ограничения для построения массивов следующим образом:

constraint1 = {1,-,-,-,-,1,-,-} // !(cell2=1 && cell6=1) cell2 and cell6 can not be in these format. 
constraint2 = {0,-,-,-,-,-,-,0} // !(cell1=0 && cell8=0) 
constraint3 = {-,-,-,2,1,1,-,-} // !(cell4=2 && cell5=1 && cell6=1) 
constraint4 = {1,1,-,-,-,-,-,-} // !(cell1=1 && cell2=1) 

Для лучшего понимания;

{0,1,1,2,0,1,0,0} // this is not valid, because it violates the constraint2 
{1,1,2,2,1,1,0,1} // this is not valid, because it violates the constraint3 and constraint4 
{1,1,0,0,0,1,0,0} // this is not valid, because it violates the constraint4 

Мне нужно создать массив целых чисел, который не нарушает ни одно из заданных ограничений.

В моем подходе;

1) Create an array (called myArray) and initialize every cell to -1 
2) Count the number of cells which are used in constraints. Above example, cell1 is used 3 times, cell2 is used 1 time, cell3 is not used, so on so forth. 
3) Choose the cell which is used more in constraints (it is cell1, used 3 times) 
4) Find the distribution of numbers in this cell. (In cell1, 1 is used 2 times and 0 is used 1 time) 
5) Change this chosen cell in myArray to the number which is used less. (In cell1, since 0 is used less than 1, cell1 in myArray will be 0) 
6) Delete all the constraints from the list which has 1 or 2 in their cell1. 
7) Go to step 2 and do same steps until all constraints are eliminated 

Идея этого алгоритма состоит в том, чтобы выбрать ячейку и ее значение таким образом, чтобы устранить больше ограничений.

Однако этот алгоритм не работает, когда число ограничений выше.

Важное примечание. Это простой пример. В нормальном случае длина массива длиннее (в среднем 100), а число ограничений выше (более 200). Мой вход - длина массива, ограничения N и значения, которые может принимать каждая ячейка.

Есть ли у кого есть идея решить эту проблему?

Answer 1

Вот код, который я написал на C#, чтобы создать случайную матрицу, а затем удалить ограничение в матрице.

class Program 
{ 
    static void Main(string[] args) 
    { 

     int[] inputData = new int[4] { 3, 7, 3, 3 }; 
     int matrixRowSize = 6; 

     /////////////////////////// Constraints 

     int []constraint1 = new int[4] { 1, -1, -1, 2}; // here is the constaint that i want to remove. 
     // note the constaints could be more than 1, so there could be a generic method 

     Random r = new Random(); 
     int[,] Random_matrix = new int[matrixRowSize, inputData.Length]; 
     ///////////// generate random matrix 
     for (int i = 0; i < inputData.Length; i++) 
     { 
      for (int j = 0; j < matrixRowSize; j++) 
      {  
       int k = r.Next(0, inputData[i]); 


       Random_matrix[j, i] = k; 
      } 
     } 

}