そこで最近、英国の GCHQ が投稿した次のパズルを見ました。
25x25 のノノグラムを解く必要があります。
ノノグラムは、隠された絵を明らかにするために、グリッドの横の数字に応じてグリッド内のセルを色付けするか空白のままにする必要がある絵論理パズルです。このタイプのパズルでは、数字は離散トモグラフィーの形式であり、特定の行または列に塗りつぶされた正方形の途切れのない行がいくつあるかを測定します。たとえば、「4 8 3」の手がかりは、4 つ、8 つ、3 つの塗りつぶされた正方形のセットがこの順序であり、連続するグループの間に少なくとも 1 つの空白の正方形があることを意味します。
当然のことながら、私はそれを解決するプログラムを作成しようとする傾向がありました。行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
}
}
}