Недавно я увидел опубликованную головоломку от британского GCHQ:
Он включает решение нонограммы 25x25:
Нонограмма - это логическая головоломка с картинками, в которой ячейки в сетке должны быть окрашены или оставлены пустыми в соответствии с числами сбоку сетки, чтобы открыть скрытое изображение. В этом типе головоломок числа представляют собой форму дискретной томографии, которая измеряет, сколько непрерывных линий заполненных квадратов есть в любой данной строке или столбце. Например, подсказка «4 8 3» будет означать, что есть наборы из четырех, восьми и трех заполненных квадратов в указанном порядке, по крайней мере, с одним пустым квадратом между последовательными группами ».
Естественно, у меня была склонность попробовать написать программу, которая решила бы эту проблему за меня. Я думал о рекурсивном алгоритме поиска с возвратом, который начинается в строке 0, и для каждого возможного расположения этой строки с учетом информации из подсказки строки он помещает возможную комбинацию следующей строки и проверяет, является ли это допустимым размещением с учетом столбца подсказки. Если это так, он продолжается, если нет, он возвращается, пока все строки не будут помещены в допустимую конфигурацию или все возможные комбинации строк не будут исчерпаны.
Я тестировал его на нескольких пазлах 5x5, и он отлично работает. Проблема в том, что вычисление головоломки 25x25 GCHQ занимает слишком много времени. Мне нужны способы сделать этот алгоритм более эффективным - достаточно, чтобы он мог решить головоломку, указанную выше. Любые идеи?
Вот мой код для создания набора возможных строк для каждой строки, а также кода для решателя (примечание * он использует некоторые нестандартные библиотеки, но это не должно отвлекать от сути):
// The Vector<int> input is a list of the row clues eg. for row 1, input = {7,3,1,1,7}. The
// int currentElemIndex keeps track of what block of the input clue we are dealing with i.e
// it starts at input[0] which is the 7 sized block and for all possible places it can be
// placed, places the next block from the clue recursively.
// The Vector<bool> rowState is the state of the row at the current time. True indicates a
// colored in square, false indicates empty.
// The Set< Vector<bool> >& result is just the set that stores all the possible valid row
// configurations.
// The int startIndex and endIndex are the bounds on the start point and end point between
// which the function will try to place the current block. The endIndex is calculated by
// subtracting the width of the board from the sum of the remaining block sizes + number
// of blocks remaining. Ie. if for row 1 with the input {7,3,1,1,7} we were placing the
// first block, the endIndex would be (3+1+1+7)+4=16 because if the first block was placed
// further than this, it would be impossible for the other blocks to fit.
// BOARD_WIDTH = 25;
// The containsPresets funtion makes sure that the row configuration is only added to the
// result set if it contains the preset values of the puzzle (the given squares
// at the start of the puzzle).
void Nonogram::rowPossibilitiesHelper(int currentElemIndex, Vector<bool>& rowState,
Vector<int>& input, Set< Vector<bool> >& result,
int startIndex, int rowIndex) {
if(currentElemIndex == input.size()) {
if(containsPresets(rowState, rowIndex)) {
result += rowState;
}
} else {
int endIndex = BOARD_WIDTH - rowSum(currentElemIndex+1, input);
int blockSize = input[currentElemIndex];
for(int i=startIndex; i<=endIndex-blockSize; i++) {
for(int j=0; j<blockSize; j++) {
rowState[i+j] = true; // set block
}
rowPossibilitiesHelper(currentElemIndex+1, rowState, input, result, i+blockSize+1, rowIndex); // explore
for(int j=0; j<blockSize; j++) {
rowState[i+j] = false; // unchoose
}
}
}
}
// The function is initally passed in 0 for the rowIndex. It gets a set of all possible
// valid arrangements of the board and for each one of them, sets the board row at rowIndex
// to the current rowConfig. Is then checks if the current configuration so far is valid in
// regards to the column clues. If it is, it solves the next row, if not, it unmarks the
// current configuration from the board row at rowIndex.
void Nonogram::solveHelper(int rowIndex) {
if(rowIndex == BOARD_HEIGHT) {
printBoard();
} else {
for(Vector<bool> rowConfig : rowPossisbilities(rowIndex)) {
setBoardRow(rowConfig, rowIndex);
if(isValidConfig(rowIndex)) { // set row
solveHelper(rowIndex+1); // explore
}
unsetBoardRow(rowIndex); // unset row
}
}
}
