Наиболее эффективный способ поиска комбинаций в C

Question

#include <stdio.h> 
#include <stdlib.h> 

int chessboard[8][8]; 
int indicator, x, i, j, b, checksum, testerint, temp, row, column; 
int rescounter, resstarter; 

void togglecolumn(int columnumber) { 
    // 
    for (j = 0; j < 8; j++) { 
     // 
     chessboard[j][columnumber] = toggleint(chessboard[j][columnumber]); 
    } 
} 

void togglerow(int rownumber) { 
    // 
    for (j = 0; j < 8; j++) { 
     // 
     chessboard[rownumber][j] = toggleint(chessboard[rownumber][j]); 
    } 
} 

void fulltoggle(int i, int j) { 
    // 
    togglerow(i); 
    togglecolumn(j); 
    chessboard[i][j] = toggleint(chessboard[i][j]); 

} 

int toggleint(int a) { 
    // 
    if (a == 0) { 
     b = 1; 
    } 
    if (a == 1) { 
     b = 0; 
    } 
    return b; 
} 

void fillchessboard() { 
    x = 1; 
    // 
    for (i = 0; i < 8; i++) { 
     x = toggleint(x); 
     for (j = 0; j < 8; j++) { 
      // 
      chessboard[i][j] = x; 
      x = toggleint(x); 
     } 
    } 
} 

void showchessboard() { 
    // 
    printf("------------------- \n \n"); 

    for (i = 0; i < 8; i++) { 
     // 
     for (j = 0; j < 8; j++) { 
      // 
      if (j == 7) { 
       //if end of the row 
       printf("%d \n", chessboard[i][j]); 
      } else { 
       // 
       printf("%d ", chessboard[i][j]); 
      } 
     } 

    } 
    printf("\n \n"); 
    printf("------------------- \n \n"); 

} 

int checkboard() { 
    checksum = 0; 

    for (i = 0; i < 8; i++) { 
     // 
     for (j = 0; j < 8; j++) { 
      // 
      if (chessboard[i][j] == 1) { 
       // 
       return 1; 
      } 
     } 
    } 

    return 0; 
} 

void rowcolindicator(int i) { 
    // 
    if (i % 8 == 0) { 
     column = 7; 
     row = i/8 - 1; 
    } else { 
     row = i/8; 
     column = i % 8 - 1; 
    } 
} 

// for proper operation i should be chosen 0 

int recurfuntion(int i, int stepcounter) { 
    if (stepcounter != 0) { 
     stepcounter--; 
     temp = i; 
     for (i = temp + 1; i < 65; i++) { 
      //do row and column for 
      rowcolindicator(i); 
      fulltoggle(row, column); 
      recurfuntion(i, stepcounter); 
     } 
     if (i == 65) { 
      i = temp++; 
      rowcolindicator(temp); 
      fulltoggle(row, column); 
      stepcounter++; 
     } 
    } else { 
     // 
     temp = i; 
     for (i = temp + 1; i < 65; i++) { 
      //do row and column for i code and return iteration number if board turns all right 
      rowcolindicator(i); 
      fulltoggle(row, column); 

      if (checkboard() == 0) { 
       // 
       showchessboard(); 
       return 1; 
      } else { 
       // 
       fulltoggle(row, column); 
      } 
     } 
     if (i == 65) { 
      i = temp++; 
      rowcolindicator(temp); 
      fulltoggle(row, column); 
      stepcounter++; 
      //showchessboard(); 
     } 
    } 
} 

int main(int argc, char *argv[]) { 

    fillchessboard(); 
    showchessboard(); 
    indicator = checkboard(); 
    printf("indicator is %d \n", indicator); 

    for (rescounter = 0; rescounter < 1000; rescounter++) { 
     fillchessboard(); 
     printf("iiteration number: %d \n", rescounter); 
     if (recurfuntion(0, rescounter) == 1) { 
      printf("iteration number is %d so is the answer :) \n", rescounter); 
     } 
    } 

    system("PAUSE"); 

    return 0; 
} 

Я пытаюсь решить эту проблему: «У вас есть таблица 8x8 на экране компьютера со всеми квадратами, окрашенными в белый цвет. На каждом шаге вы выберете любой квадрат и, как результат все квадраты в том же ряду и столбце, включая выбранный квадрат, будут переключаться на их цвета (белый становится черным, а черный становится белым). Какое минимальное количество шагов требуется для получения стандартной цветной шахматной доски? "

Для этого я пропустил шахматную доску на 64 части (8x8) и вычислил все комбинации этого 64-кластерного кластера от 1 до 64. (Я знаю, что ответ между 1 и 64).

Мой метод должен начинаться от конца (шахматная доска) до всех белых. Поэтому я заполняю доску теми (черными) и нулями (белый) и успешно завершаю шахматную доску в функции fillchessboard(). И я могу прекрасно переключаться между строкой и столбцом, на котором я выбираю начальный квадрат.

Метод проверки, если вся доска белого цвета - это контрольная панель(). Эта функция возвращает индикатор как 0, если все доски белые, 1 если нет. Я начинаю с небольших комбинаций до больших комбинаций и проверяю плату на каждом шагу. Поэтому, когда индикатор возвращается как 0 в первый раз, это будет наименьший номер итерации, чтобы сделать панель полностью белой и быть ответом на вопрос.

До сих пор мой код работает, и через 10 часов он может перейти на десятую итерацию. Однако потребуется больше времени, поэтому 11-я итерация займет около 10 часов, а 12-я итерация займет 20 часов и т. Д. ... Мой вопрос в том, есть ли какой-либо метод этих инструкций более быстрый и эффективный? Я не могу дождаться недели, чтобы решить эту проблему. Я ценю любую помощь. Благодаря!

Answer 1

Во-первых, давайте делать некоторые именование:

• c_{i,j} является ячейка на пересечении строки и столбца ij.
• cross_{i,j} это набор: { c_{r,c}/r=i or c=j }. Это крест всех элементов из ряда i union column j. Он содержит нечетное число количество ячеек.
• odd(cross_{i,j}) - это функция, которая возвращает 0, если четное число черных ячеек в cross_{i,j} и 1, если имеется нечетное число черных ячеек.

Давайте рассмотрим влияние выбора ячейки c_{i,j}:

1. Это переключит нечетное число клеток в cross_{i,j} и так будет переключать значение odd(cross_{i,j}).
2. Для всех других «крестов» количество воздействующих ячеек будет четным, и поэтому значение odd(cross_{k,l}) для любого (k,l) \neq (i,j)не изменится.

Причина пункт 2 является то, что есть только три случая для пересечения cross_{k,l} с cross_{i,j}:

1. Это целый ряд, с четным числом клеток.
2. Это целая колонка с четным количеством ячеек.
3. Это одна ячейка для ряда k и одна ячейка для столбца l.

Таким образом, для каждой возможности четное количество ячеек меняет цвета, и поэтому значение odd(cross_{k,l}) не изменяется.

Таким образом, единственный способ переключить значение odd(cross_{i,j}) - это выбрать c_{i,j}.

В конце игры есть 32 кресты, которые имеют значение переключения. Таким образом, минимальное количество шагов для любого решения составляет 32.

Теперь предыдущие рассуждения также показывают, что выбор 32 ячеек, представляющих интерес, приведет к окончательному состоянию шахматной доски.

Так что это минимальное решение.

Мне очень жаль, но нет нет программирования здесь :)

Answer 2

Это не решение, а некоторые указатели, которые должны помочь уменьшить сложность (но не сложность) проблемы.

Шахматная доска имеет 2^64 различных состояния.

Есть некоторые свойства шахматной доски, которые помогут вам уменьшить количество интересных состояний.

Каждое перемещение переворачивает 15 плиток (нечетное число). Поскольку вы начинаете и заканчиваете четным количеством белых плит, вы знаете, что общее количество ходов четное.

Кроме того, порядок, в котором выполняются ходы, не имеет значения. И выбор того же квадрата дважды меняет предыдущий флип. Поэтому нам нужно только выяснить, какой из 64 фрагментов выбрать.

Таким образом, мы можем использовать 64 бита для представления решения, и каждый бит представляет либо выбранную плиту, либо невыбранную плитку. Мы могли бы использовать 64-битную длину для хранения возможного решения.

Кроме того, если вы используете 64-разрядную длину для хранения состояния платы, каждый шаг представляет собой XOR с числом, которое переворачивает правые 15 фрагментов (число, которое содержит эти 15 бит).

Шахматная доска симметрична. Не важно, поворачиваете ли вы его или зеркалируете. Государство будет таким же. Это еще больше уменьшает сложность, так как доказывает, что если X является решением, то дополнение к X также является решением. Поэтому, если не найдено ни одного решения с 32 выбранными элементами, тогда решения не существует.

Моя интуиция (или, скорее, симметрия) предполагает, что решение, если оно существует) должно быть кратным 8 и быть либо 8, 16, либо 32, причем наиболее вероятным является 16. Однако у меня нет доказательств.Мне должно быть довольно легко доказать, что в 8 ходах нет решения (и вы доказали это, используя грубую силу, если ваша программа верна).