解决填字游戏
Ann*_*eta 9 java algorithm brute-force backtracking
我有一个填字游戏和一个可用于解决它的单词列表(单词可以放置多次或甚至不放一次).对于给定的填字游戏和单词列表,始终存在解决方案.
我搜索了如何解决这个问题的线索,发现它是NP-Complete.我的最大填字游戏大小是250乘250,列表的最大长度(可以用来解决它的单词数量)是200.我的目标是通过强力/回溯来解决这个大小的填字游戏,这应该是可能的几秒钟(这是我的粗略估计,如果我错了,请纠正我).
例:
可用于解决填字游戏的给定单词列表:
- 能够
- 音乐
- 金枪鱼
- 嗨
给定的空填字游戏(X是无法填写的字段,需要填充空字段):
解决方案:
现在我的方法是将填字游戏表示为二维数组并搜索空格(填字游戏上的2次迭代).然后我根据它们的长度将单词与空格匹配,然后我尝试所有单词组合来清空具有相同长度的空格.这种方法变得非常混乱非常快,我迷失了尝试实现这一点,是否有更优雅的解决方案？
您的基本想法非常明智：
- 识别板上的插槽。
- 用适合的每个单词尝试每个插槽。
- 如果每个槽都可以填充而不会发生冲突，则解决。
这是一个很棒的计划。下一步是将其转化为设计。对于这样的小程序，我们可以直接使用伪代码。正如其他答案所解释的，它的要点是递归：
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.
下面是我根据您的要求编写的一个简短但完整的示例。
给猫剥皮的方法不止一种。我的代码交换了第 1 步和第 2 步，并将第 4 步到第 6 步合并到一个填充循环中。
关键点：
- 使用格式化程序使代码适合您的风格。
- 二维板以行优先顺序存储在线性字符数组中。
- 这允许板
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;
}
}