有效地解决填字游戏 [已关闭]

2022-09-04 22:29:45

我有一个填字游戏和一个单词列表,可以用来解决它(单词可以放置多次,甚至不能放置一次)。对于给定的填字游戏和单词列表,总有一个解决方案。

我搜索了如何解决这个问题的线索,发现它是NP-Complete。我的最大填字游戏大小是250×250,列表的最大长度(可以用来解决它的单词量)是200。我的目标是通过蛮力/回溯来解决这种规模的填字游戏,这应该在几秒钟内实现(这是我的粗略估计,如果我错了,请纠正我)。

例如:

可用于解决填字游戏的给定单词列表:

  • 音乐
  • 金枪鱼
  • 你好

给定的空填字游戏(X是无法填写的字段,空字段需要填充):

An empty crossword which needs to be solved

解决方案:

The solution of the problem above

现在,我目前的方法是将填字游戏表示为2-D数组并搜索空白空间(填字游戏的2次迭代)。然后,我根据单词的长度将单词与空格匹配,然后尝试将所有单词组合到具有相同长度的空白空间。这种方法变得非常混乱,非常快,我迷路了试图实现这一点,有没有更优雅的解决方案?


答案 1

你的基本想法是非常明智的:

  1. 识别主板上的插槽。
  2. 尝试每个插槽,每个单词都适合。
  3. 如果每个插槽都可以在没有冲突的情况下填充,那么它就解决了。

这是一个很好的计划。下一步是将其转化为设计。对于像这样的小程序,我们可以直接进入伪代码。正如其他答案所解释的那样,它的要点是递归

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 合并到一个填充循环中。

要点:

  • 使用格式化程序使代码适合您的样式。
  • 2D 板按行主顺序存储在线性字符数组中。
  • 这允许电路板由阵列复制保存和恢复。clone()
  • 创建时,将扫描电路板,以查找来自两个方向的两个刀路的槽。
  • 两个插槽列表由同一循环求解,主要区别在于插槽的填充方式。
  • 将显示重复过程,因此您可以看到它的工作原理。
  • 我们做出了许多假设。没有单个字母插槽,所有单词都在同一种情况下,板是正确的等。
  • 要有耐心。学习任何新事物,并给自己时间吸收它。

源:

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;
   }
}

练习:你可以重写递归到迭代;速度更快,可以支持更大的板。完成后,它可以转换为多线程并运行得更快。


答案 2

你是对的,问题是 -完全的。所以你最好的机会是通过蛮力来解决它(如果你找到一个多项式算法,请告诉我,我们都可以很富有=))。NP

我建议你看看回溯。它将允许您为填字游戏问题编写一个优雅(但考虑到您的输入大小而缓慢)的解决方案。

如果您需要更多鼓舞人心的材料,请查看此求解器,它使用回溯作为导航求解树的方法。

请注意,有些算法在实践中可能比纯粹的蛮力表现得更好(即使仍然具有指数级复杂性)。此外,快速搜索学者会发现大量关于您可能想要查看的主题的论文,例如以下内容: