有效地解决填字游戏
Solving crosswords efficiently
我有一个填字游戏和一个可用于解决它的单词列表（单词可以放置 多次，甚至一次都不能 ）。对于给定的填字游戏和单词列表，总有一个解决方案。
我搜索了有关如何解决此问题的线索，发现它是 NP-Complete。我的最大填字游戏大小是 250 x 250，列表的最大长度（可用于解决它的单词数量）是 200。我的目标是通过暴力 force/backtracking 来解决这个大小的填字游戏，这应该是可能在几秒钟内（这是我的粗略估计，如果我错了请纠正我）。
例如：
可用于解决填字游戏的给定单词列表：
- 可以
- 音乐
- 金枪鱼
- 嗨
给定的空填字游戏（X为不能填写的字段，空的字段需要填写）：
解决方法：
现在我目前的方法是将填字游戏表示为二维数组并搜索空格（对填字游戏进行 2 次迭代）。然后我根据单词的长度将单词匹配到空格，然后我尝试将单词的所有组合都匹配到具有相同长度的空格。这种方法很快就变得非常混乱，我在尝试实现它时迷路了，有没有更优雅的解决方案？
你是对的，问题是 NP- 完成。所以你最好的机会是通过蛮力解决它（如果你找到多项式算法请告诉我，我们都可以成为有钱人=））。
我建议你看看backtracking。它将允许您为纵横字谜问题编写一个优雅的（但考虑到您的输入大小但速度较慢）解决方案。
如果您需要更多灵感material，请查看this solver，它使用回溯作为导航解决方案树的方法。
请注意，有些算法在实践中可能比纯暴力算法表现得更好（即使仍然具有指数复杂性）。
此外，在 scholar 上快速搜索会发现大量关于您可能想要查看的主题的论文，例如：
填字游戏是约束满足问题，通常是 NP 完全问题，但有许多求解器会将最有效的算法应用于您指定的约束问题。 Z3 SMT 求解器可以非常轻松地大规模解决这些问题。您所要做的就是编写一个 Java 程序，将填字游戏转换为求解器可以理解的 SMT 问题，然后将其交给求解器来解决。 Z3 有 Java 绑定，所以它应该很简单。我已经编写了用于解决下面第一个示例的 Z3 代码。按照 Java 程序中的模式指定任意大的十字路口谜题对您来说应该不难。
; Declare each possible word as string literals
(define-const str1 String "tuna")
(define-const str2 String "music")
(define-const str3 String "can")
(define-const str4 String "hi")
; Define a function that returns true if the given String is equal to one of the possible words defined above.
(define-fun validString ((s String)) Bool
(or (= s str1) (or (= s str2) (or (= s str3) (= s str4)))))
; Declare the strings that need to be solved
(declare-const unknownStr1 String)
(declare-const unknownStr2 String)
(declare-const unknownStr3 String)
(declare-const unknownStr4 String)
; Assert the correct lengths for each of the unknown strings.
(assert (= (str.len unknownStr1) 4))
(assert (= (str.len unknownStr2) 5))
(assert (= (str.len unknownStr3) 3))
(assert (= (str.len unknownStr4) 2))
; Assert each of the unknown strings is one of the possible words.
(assert (validString unknownStr1))
(assert (validString unknownStr2))
(assert (validString unknownStr3))
(assert (validString unknownStr4))
; Where one word in the crossword puzzle intersects another assert that the characters at the intersection point are equal.
(assert (= (str.at unknownStr1 1) (str.at unknownStr2 1)))
(assert (= (str.at unknownStr2 3) (str.at unknownStr4 1)))
(assert (= (str.at unknownStr2 4) (str.at unknownStr3 0)))
; Solve the model
(check-sat)
(get-model)
我推荐 Z3 SMT 求解器，但还有很多其他约束求解器。您无需实现自己的约束求解算法，就像您无需实现自己的排序算法一样。
为了使这个问题更容易解决，我将把它分解成更小、更容易的问题。请注意，我不包括 code/algorithms，因为我认为这对这里没有帮助（如果我们想要最好的代码，就会有索引和数据库以及让你的头在看到它时爆炸的黑魔法）。相反，这个答案试图通过讨论有助于 OP 使用最适合 reader.
的方法解决这个问题（以及未来的问题）的思维方法来回答问题。
你需要知道什么
此答案假定您知道如何执行以下操作
- 创建和使用具有属性和功能的对象
- 选择一个适合（不一定好）的数据结构来满足您对其内容的处理需求。
为您建模 space
因此，将您的填字游戏加载到 n x m 矩阵（二维数组，特此 'grid'）中非常容易，但这在实用上非常有用。因此，让我们从将您的填字游戏从网格解析为合法对象开始。
就您的程序而言，填字游戏中的每个条目都有 4 个属性。
- 网格中第一个字母的 X-Y 坐标
- 一个方向（向下或横向）
- 字长
- 字值
- 绑定索引图
- 键：与另一个条目共享的单词索引
- 值：与索引共享的条目
- （您可以将其设为一个元组并包含来自其他条目的共享索引以便于参考）
您可以在扫描时根据这些规则在网格中找到它们。
- 如果Row_1_up是关闭的，Row_1_down是打开的，这是一个下词的起始索引。 （向下扫描长度。对于绑定索引，左或右 space 将打开。向左扫描以获取链接条目 coord-id）
- 与 1 相同，但跨词旋转（您可以在扫描 1 的同时执行此操作）
在您的填字游戏对象中，您可以使用坐标+方向作为键存储条目，以便于参考和转换to/from文本网格形式。
使用您的模型
您现在应该有一个包含填字游戏条目集合的对象，其中包含它们的相关索引绑定。您现在需要找到一组满足您所有条目的值。
您的条目对象应该有像 isValidEntry(str) 这样的辅助方法来检查给定值和填字游戏的当前状态，我可以把这个词放在这里吗？通过使模型中的每个对象负责其自己的逻辑级别，一个思考层的问题代码可以调用逻辑而不用担心它的实现（在这个例子中，你的求解器不必担心逻辑of 是一个有效的值，它可以只要求 isValidEntry 为此）
如果您已正确完成上述操作，那么解决问题就是简单地遍历所有条目的所有单词以找到解决方案。
子问题列表
作为参考，这是我的子问题列表，您需要写一些东西来解决。
- 我怎样才能对我的工作进行理想的建模 -space 对我来说很容易处理？
- 对于我的模型的每一部分，它需要知道什么？它可以为我处理什么逻辑？
- 如何将文本输入转换为可用的模型对象？
- 如何使用我的模型对象解决我的问题？ （对你来说，它是迭代所有 words/all 个条目来找到一个有效的集合。可能使用递归）
你的基本思路很合理：
- 识别板上的插槽。
- 用每个合适的单词尝试每个插槽。
- 如果每个slot都能填满而不冲突，那就解决了。
这是一个绝妙的计划。
下一步是将其转化为设计。
对于这样的小程序，我们可以直接使用伪代码。
正如其他答案所解释的那样，它的要点是 recursion:
1 Draw a slot from the slot pool.
2 If slot pool is empty (all slots filled), stop solving.
3 For each word with correct length:
4 If part of the slot is filled, check conflict.
5 If the word does not fit, continue the loop to next word.
// No conflict
6 Fill the slot with the word.
// Try next slot (down a level)
7 Recur from step 1.
8 If the recur found no solution, revert (take the word back) and try next.
// None of them works
9 If no words yield a solution, an upper level need to try another word.
Revert (put the slot back) and go back.
下面是我根据您的要求编写的一个简短但完整的示例。
There is more than one way to skin a cat.
My code swapped step 1 and 2, and combines step 4 to 6 in one fill loop.
要点：
- 使用格式化程序使代码符合您的风格。
- 二维板存储在线性字符数组中row-major order。
- 这允许板由
clone() 保存并由 arraycopy 恢复。
- 创建时，从两个方向分两次扫描电路板以查找插槽。
- 两个槽列表是用同一个循环求解的，区别主要在于槽的填充方式。
- 显示了重复过程，因此您可以看到它是如何工作的。
- 做了很多假设。没有单个字母槽，所有单词大小写相同，棋盘正确等
- 耐心点。学习任何新事物并给自己时间吸收它。
来源：
import java.awt.Point;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Supplier;
import java.util.stream.Stream;
public class Crossword {
public static void main ( String[] args ) {
new Crossword( Arrays.asList( "5 4 4\n#_#_#\n_____\n#_##_\n#_##_\ntuna\nmusic\ncan\nhi".split( "\n" ) ) );
new Crossword( Arrays.asList( "6 6 4\n##_###\n#____#\n___#__\n#_##_#\n#____#\n##_###\nnice\npain\npal\nid".split( "\n" ) ) );
}
private final int height, width; // Board size
private final char[] board; // Current board state. _ is unfilled. # is blocked. other characters are filled.
private final Set<String> words; // List of words
private final Map<Point, Integer> vertical = new HashMap<>(), horizontal = new HashMap<>(); // Vertical and horizontal slots
private String indent = ""; // For formatting log
private void log ( String message, Object... args ) { System.out.println( indent + String.format( message, args ) ); }
private Crossword ( List<String> lines ) {
// Parse input data
final int[] sizes = Stream.of( lines.get(0).split( "\s+" ) ).mapToInt( Integer::parseInt ).toArray();
width = sizes[0]; height = sizes[1];
board = String.join( "", lines.subList( 1, height+1 ) ).toCharArray();
words = new HashSet<>( lines.subList( height+1, lines.size() ) );
// Find horizontal slots then vertical slots
for ( int y = 0, size ; y < height ; y++ )
for ( int x = 0 ; x < width-1 ; x++ )
if ( isSpace( x, y ) && isSpace( x+1, y ) ) {
for ( size = 2 ; x+size < width && isSpace( x+size, y ) ; size++ ); // Find slot size
horizontal.put( new Point( x, y ), size );
x += size; // Skip past this horizontal slot
}
for ( int x = 0, size ; x < width ; x++ )
for ( int y = 0 ; y < height-1 ; y++ )
if ( isSpace( x, y ) && isSpace( x, y+1 ) ) {
for ( size = 2 ; y+size < height && isSpace( x, y+size ) ; size++ ); // Find slot size
vertical.put( new Point( x, y ), size );
y += size; // Skip past this vertical slot
}
log( "A " + width + "x" + height + " board, " + vertical.size() + " vertical, " + horizontal.size() + " horizontal." );
// Solve the crossword, horizontal first then vertical
final boolean solved = solveHorizontal();
// Show board, either fully filled or totally empty.
for ( int i = 0 ; i < board.length ; i++ ) {
if ( i % width == 0 ) System.out.println();
System.out.print( board[i] );
}
System.out.println( solved ? "\n" : "\nNo solution found\n" );
}
// Helper functions to check or set board cell
private char get ( int x, int y ) { return board[ y * width + x ]; }
private void set ( int x, int y, char character ) { board[ y * width + x ] = character; }
private boolean isSpace ( int x, int y ) { return get( x, y ) == '_'; }
// Fit all horizontal slots, when success move to solve vertical.
private boolean solveHorizontal () {
return solve( horizontal, this::fitHorizontal, "horizontally", this::solveVertical );
}
// Fit all vertical slots, report success when done
private boolean solveVertical () {
return solve( vertical, this::fitVertical, "vertically", () -> true );
}
// Recur each slot, try every word in a loop. When all slots of this kind are filled successfully, run next stage.
private boolean solve ( Map<Point, Integer> slot, BiFunction<Point, String, Boolean> fill, String dir, Supplier<Boolean> next ) {
if ( slot.isEmpty() ) return next.get(); // If finished, move to next stage.
final Point pos = slot.keySet().iterator().next();
final int size = slot.remove( pos );
final char[] state = board.clone();
/* Try each word */ indent += " ";
for ( String word : words ) {
if ( word.length() != size ) continue;
/* If the word fit, recur. If recur success, done! */ log( "Trying %s %s at %d,%d", word, dir, pos.x, pos.y );
if ( fill.apply( pos, word ) && solve( slot, fill, dir, next ) )
return true;
/* Doesn't match. Restore board and try next word */ log( "%s failed %s at %d,%d", word, dir, pos.x, pos.y );
System.arraycopy( state, 0, board, 0, board.length );
}
/* No match. Restore slot and report failure */ indent = indent.substring( 0, indent.length() - 2 );
slot.put( pos, size );
return false;
}
// Try fit a word to a slot. Return false if there is a conflict.
private boolean fitHorizontal ( Point pos, String word ) {
final int x = pos.x, y = pos.y;
for ( int i = 0 ; i < word.length() ; i++ ) {
if ( ! isSpace( x+i, y ) && get( x+i, y ) != word.charAt( i ) ) return false; // Conflict
set( x+i, y, word.charAt( i ) );
}
return true;
}
private boolean fitVertical ( Point pos, String word ) {
final int x = pos.x, y = pos.y;
for ( int i = 0 ; i < word.length() ; i++ ) {
if ( ! isSpace( x, y+i ) && get( x, y+i ) != word.charAt( i ) ) return false; // Conflict
set( x, y+i, word.charAt( i ) );
}
return true;
}
}
Exercise: You can rewrite recursion to iteration; faster and can support bigger boards.
Once that's done it can be converted to multi-thread and run even faster.
我刚刚在 Scala 中实现了一个代码来解决这些难题。我只是使用递归来解决问题。简而言之，对于每个单词，我找到所有可能的位置，然后选择一个位置并用该单词填充它，并尝试用递归解决部分难题。如果拼图不能用剩下的单词填满，它会尝试另一个插槽，等等。如果没有，拼图就解决了。
这是我的代码的 link：
https://github.com/mysilver/AMP/blob/master/Crossword.scala
我有一个填字游戏和一个可用于解决它的单词列表（单词可以放置 多次，甚至一次都不能 ）。对于给定的填字游戏和单词列表，总有一个解决方案。
我搜索了有关如何解决此问题的线索，发现它是 NP-Complete。我的最大填字游戏大小是 250 x 250，列表的最大长度（可用于解决它的单词数量）是 200。我的目标是通过暴力 force/backtracking 来解决这个大小的填字游戏，这应该是可能在几秒钟内（这是我的粗略估计，如果我错了请纠正我）。
例如：
可用于解决填字游戏的给定单词列表：
- 可以
- 音乐
- 金枪鱼
- 嗨
给定的空填字游戏（X为不能填写的字段，空的字段需要填写）：
解决方法：
现在我目前的方法是将填字游戏表示为二维数组并搜索空格（对填字游戏进行 2 次迭代）。然后我根据单词的长度将单词匹配到空格，然后我尝试将单词的所有组合都匹配到具有相同长度的空格。这种方法很快就变得非常混乱，我在尝试实现它时迷路了，有没有更优雅的解决方案？
你是对的，问题是 NP- 完成。所以你最好的机会是通过蛮力解决它（如果你找到多项式算法请告诉我，我们都可以成为有钱人=））。
我建议你看看backtracking。它将允许您为纵横字谜问题编写一个优雅的（但考虑到您的输入大小但速度较慢）解决方案。
如果您需要更多灵感material，请查看this solver，它使用回溯作为导航解决方案树的方法。
请注意，有些算法在实践中可能比纯暴力算法表现得更好（即使仍然具有指数复杂性）。 此外，在 scholar 上快速搜索会发现大量关于您可能想要查看的主题的论文，例如：
填字游戏是约束满足问题，通常是 NP 完全问题，但有许多求解器会将最有效的算法应用于您指定的约束问题。 Z3 SMT 求解器可以非常轻松地大规模解决这些问题。您所要做的就是编写一个 Java 程序，将填字游戏转换为求解器可以理解的 SMT 问题，然后将其交给求解器来解决。 Z3 有 Java 绑定，所以它应该很简单。我已经编写了用于解决下面第一个示例的 Z3 代码。按照 Java 程序中的模式指定任意大的十字路口谜题对您来说应该不难。
; Declare each possible word as string literals
(define-const str1 String "tuna")
(define-const str2 String "music")
(define-const str3 String "can")
(define-const str4 String "hi")
; Define a function that returns true if the given String is equal to one of the possible words defined above.
(define-fun validString ((s String)) Bool
(or (= s str1) (or (= s str2) (or (= s str3) (= s str4)))))
; Declare the strings that need to be solved
(declare-const unknownStr1 String)
(declare-const unknownStr2 String)
(declare-const unknownStr3 String)
(declare-const unknownStr4 String)
; Assert the correct lengths for each of the unknown strings.
(assert (= (str.len unknownStr1) 4))
(assert (= (str.len unknownStr2) 5))
(assert (= (str.len unknownStr3) 3))
(assert (= (str.len unknownStr4) 2))
; Assert each of the unknown strings is one of the possible words.
(assert (validString unknownStr1))
(assert (validString unknownStr2))
(assert (validString unknownStr3))
(assert (validString unknownStr4))
; Where one word in the crossword puzzle intersects another assert that the characters at the intersection point are equal.
(assert (= (str.at unknownStr1 1) (str.at unknownStr2 1)))
(assert (= (str.at unknownStr2 3) (str.at unknownStr4 1)))
(assert (= (str.at unknownStr2 4) (str.at unknownStr3 0)))
; Solve the model
(check-sat)
(get-model)
我推荐 Z3 SMT 求解器，但还有很多其他约束求解器。您无需实现自己的约束求解算法，就像您无需实现自己的排序算法一样。
为了使这个问题更容易解决，我将把它分解成更小、更容易的问题。请注意，我不包括 code/algorithms，因为我认为这对这里没有帮助（如果我们想要最好的代码，就会有索引和数据库以及让你的头在看到它时爆炸的黑魔法）。相反，这个答案试图通过讨论有助于 OP 使用最适合 reader.
的方法解决这个问题（以及未来的问题）的思维方法来回答问题。你需要知道什么
此答案假定您知道如何执行以下操作
- 创建和使用具有属性和功能的对象
- 选择一个适合（不一定好）的数据结构来满足您对其内容的处理需求。
为您建模 space
因此，将您的填字游戏加载到 n x m 矩阵（二维数组，特此 'grid'）中非常容易，但这在实用上非常有用。因此，让我们从将您的填字游戏从网格解析为合法对象开始。
就您的程序而言，填字游戏中的每个条目都有 4 个属性。
- 网格中第一个字母的 X-Y 坐标
- 一个方向（向下或横向）
- 字长
- 字值
- 绑定索引图
- 键：与另一个条目共享的单词索引
- 值：与索引共享的条目
- （您可以将其设为一个元组并包含来自其他条目的共享索引以便于参考）
您可以在扫描时根据这些规则在网格中找到它们。
- 如果Row_1_up是关闭的，Row_1_down是打开的，这是一个下词的起始索引。 （向下扫描长度。对于绑定索引，左或右 space 将打开。向左扫描以获取链接条目 coord-id）
- 与 1 相同，但跨词旋转（您可以在扫描 1 的同时执行此操作）
在您的填字游戏对象中，您可以使用坐标+方向作为键存储条目，以便于参考和转换to/from文本网格形式。
使用您的模型
您现在应该有一个包含填字游戏条目集合的对象，其中包含它们的相关索引绑定。您现在需要找到一组满足您所有条目的值。
您的条目对象应该有像 isValidEntry(str) 这样的辅助方法来检查给定值和填字游戏的当前状态，我可以把这个词放在这里吗？通过使模型中的每个对象负责其自己的逻辑级别，一个思考层的问题代码可以调用逻辑而不用担心它的实现（在这个例子中，你的求解器不必担心逻辑of 是一个有效的值，它可以只要求 isValidEntry 为此）
如果您已正确完成上述操作，那么解决问题就是简单地遍历所有条目的所有单词以找到解决方案。
子问题列表
作为参考，这是我的子问题列表，您需要写一些东西来解决。
- 我怎样才能对我的工作进行理想的建模 -space 对我来说很容易处理？
- 对于我的模型的每一部分，它需要知道什么？它可以为我处理什么逻辑？
- 如何将文本输入转换为可用的模型对象？
- 如何使用我的模型对象解决我的问题？ （对你来说，它是迭代所有 words/all 个条目来找到一个有效的集合。可能使用递归）
你的基本思路很合理：
- 识别板上的插槽。
- 用每个合适的单词尝试每个插槽。
- 如果每个slot都能填满而不冲突，那就解决了。
这是一个绝妙的计划。 下一步是将其转化为设计。 对于这样的小程序，我们可以直接使用伪代码。 正如其他答案所解释的那样，它的要点是 recursion:
1 Draw a slot from the slot pool.
2 If slot pool is empty (all slots filled), stop solving.
3 For each word with correct length:
4 If part of the slot is filled, check conflict.
5 If the word does not fit, continue the loop to next word.
// No conflict
6 Fill the slot with the word.
// Try next slot (down a level)
7 Recur from step 1.
8 If the recur found no solution, revert (take the word back) and try next.
// None of them works
9 If no words yield a solution, an upper level need to try another word.
Revert (put the slot back) and go back.
下面是我根据您的要求编写的一个简短但完整的示例。
There is more than one way to skin a cat. My code swapped step 1 and 2, and combines step 4 to 6 in one fill loop.
要点：
- 使用格式化程序使代码符合您的风格。
- 二维板存储在线性字符数组中row-major order。
- 这允许板由
clone()保存并由 arraycopy 恢复。 - 创建时，从两个方向分两次扫描电路板以查找插槽。
- 两个槽列表是用同一个循环求解的，区别主要在于槽的填充方式。
- 显示了重复过程，因此您可以看到它是如何工作的。
- 做了很多假设。没有单个字母槽，所有单词大小写相同，棋盘正确等
- 耐心点。学习任何新事物并给自己时间吸收它。
来源：
import java.awt.Point;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Supplier;
import java.util.stream.Stream;
public class Crossword {
public static void main ( String[] args ) {
new Crossword( Arrays.asList( "5 4 4\n#_#_#\n_____\n#_##_\n#_##_\ntuna\nmusic\ncan\nhi".split( "\n" ) ) );
new Crossword( Arrays.asList( "6 6 4\n##_###\n#____#\n___#__\n#_##_#\n#____#\n##_###\nnice\npain\npal\nid".split( "\n" ) ) );
}
private final int height, width; // Board size
private final char[] board; // Current board state. _ is unfilled. # is blocked. other characters are filled.
private final Set<String> words; // List of words
private final Map<Point, Integer> vertical = new HashMap<>(), horizontal = new HashMap<>(); // Vertical and horizontal slots
private String indent = ""; // For formatting log
private void log ( String message, Object... args ) { System.out.println( indent + String.format( message, args ) ); }
private Crossword ( List<String> lines ) {
// Parse input data
final int[] sizes = Stream.of( lines.get(0).split( "\s+" ) ).mapToInt( Integer::parseInt ).toArray();
width = sizes[0]; height = sizes[1];
board = String.join( "", lines.subList( 1, height+1 ) ).toCharArray();
words = new HashSet<>( lines.subList( height+1, lines.size() ) );
// Find horizontal slots then vertical slots
for ( int y = 0, size ; y < height ; y++ )
for ( int x = 0 ; x < width-1 ; x++ )
if ( isSpace( x, y ) && isSpace( x+1, y ) ) {
for ( size = 2 ; x+size < width && isSpace( x+size, y ) ; size++ ); // Find slot size
horizontal.put( new Point( x, y ), size );
x += size; // Skip past this horizontal slot
}
for ( int x = 0, size ; x < width ; x++ )
for ( int y = 0 ; y < height-1 ; y++ )
if ( isSpace( x, y ) && isSpace( x, y+1 ) ) {
for ( size = 2 ; y+size < height && isSpace( x, y+size ) ; size++ ); // Find slot size
vertical.put( new Point( x, y ), size );
y += size; // Skip past this vertical slot
}
log( "A " + width + "x" + height + " board, " + vertical.size() + " vertical, " + horizontal.size() + " horizontal." );
// Solve the crossword, horizontal first then vertical
final boolean solved = solveHorizontal();
// Show board, either fully filled or totally empty.
for ( int i = 0 ; i < board.length ; i++ ) {
if ( i % width == 0 ) System.out.println();
System.out.print( board[i] );
}
System.out.println( solved ? "\n" : "\nNo solution found\n" );
}
// Helper functions to check or set board cell
private char get ( int x, int y ) { return board[ y * width + x ]; }
private void set ( int x, int y, char character ) { board[ y * width + x ] = character; }
private boolean isSpace ( int x, int y ) { return get( x, y ) == '_'; }
// Fit all horizontal slots, when success move to solve vertical.
private boolean solveHorizontal () {
return solve( horizontal, this::fitHorizontal, "horizontally", this::solveVertical );
}
// Fit all vertical slots, report success when done
private boolean solveVertical () {
return solve( vertical, this::fitVertical, "vertically", () -> true );
}
// Recur each slot, try every word in a loop. When all slots of this kind are filled successfully, run next stage.
private boolean solve ( Map<Point, Integer> slot, BiFunction<Point, String, Boolean> fill, String dir, Supplier<Boolean> next ) {
if ( slot.isEmpty() ) return next.get(); // If finished, move to next stage.
final Point pos = slot.keySet().iterator().next();
final int size = slot.remove( pos );
final char[] state = board.clone();
/* Try each word */ indent += " ";
for ( String word : words ) {
if ( word.length() != size ) continue;
/* If the word fit, recur. If recur success, done! */ log( "Trying %s %s at %d,%d", word, dir, pos.x, pos.y );
if ( fill.apply( pos, word ) && solve( slot, fill, dir, next ) )
return true;
/* Doesn't match. Restore board and try next word */ log( "%s failed %s at %d,%d", word, dir, pos.x, pos.y );
System.arraycopy( state, 0, board, 0, board.length );
}
/* No match. Restore slot and report failure */ indent = indent.substring( 0, indent.length() - 2 );
slot.put( pos, size );
return false;
}
// Try fit a word to a slot. Return false if there is a conflict.
private boolean fitHorizontal ( Point pos, String word ) {
final int x = pos.x, y = pos.y;
for ( int i = 0 ; i < word.length() ; i++ ) {
if ( ! isSpace( x+i, y ) && get( x+i, y ) != word.charAt( i ) ) return false; // Conflict
set( x+i, y, word.charAt( i ) );
}
return true;
}
private boolean fitVertical ( Point pos, String word ) {
final int x = pos.x, y = pos.y;
for ( int i = 0 ; i < word.length() ; i++ ) {
if ( ! isSpace( x, y+i ) && get( x, y+i ) != word.charAt( i ) ) return false; // Conflict
set( x, y+i, word.charAt( i ) );
}
return true;
}
}
Exercise: You can rewrite recursion to iteration; faster and can support bigger boards. Once that's done it can be converted to multi-thread and run even faster.
我刚刚在 Scala 中实现了一个代码来解决这些难题。我只是使用递归来解决问题。简而言之，对于每个单词，我找到所有可能的位置，然后选择一个位置并用该单词填充它，并尝试用递归解决部分难题。如果拼图不能用剩下的单词填满，它会尝试另一个插槽，等等。如果没有，拼图就解决了。
这是我的代码的 link： https://github.com/mysilver/AMP/blob/master/Crossword.scala