解决填字游戏 [英] Solving crosswords

问题描述

我有一个填字游戏和一个可以用来解决它的单词列表（单词可以多次或不一次）。给定的填字游戏和单词列表总是有一个解决方案。

我搜索了如何解决这个问题的线索，发现它是NP-Complete。我的最大填字游戏大小是250乘250，列表的最大长度（可以用来解决它的单词数量）是200.我的目标是通过强力/回溯来解决这个大小的填字游戏，这应该是可能的几秒钟（这是我的粗略估计，如果我错了，请纠正我。）

示例：

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

• 可以


• 音乐


• tuna


• hi

给定空填字游戏（X是无法填写的字段，需要填写空字段）：

解决方案：

现在我的方法是将填字游戏表示为二维数组并搜索空格（填字游戏上的2次迭代）。然后我根据它们的长度将单词与空格匹配，然后我尝试所有单词组合来清空具有相同长度的空格。这种方法非常混乱非常快，我迷失了试图实现这个，有更优雅的解决方案吗？

解决方案

基本你有这个想法是非常明智的：

1. 识别黑板上的插槽。


2. 尝试每个插槽每个单词都适合。


3. 如果每个插槽都可以填充而没有冲突，它就会被解决。

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

  1从插槽池中绘制一个插槽。 
 2如果插槽池为空（所有插槽已填满），请停止解决。 
 3对于每个具有正确长度的单词：
 4如果插槽的一部分已填满，请检查冲突。 
 5如果单词不合适，继续循环到下一个单词。 
 //无冲突
 6用插槽填写插槽。 
 //尝试下一个插槽（下一个级别）
 7从步骤1开始重复。
 8如果recur找不到解决方案，请恢复（取回单词）并尝试下一步。 
 //它们都不起作用
 9如果没有单词产生解决方案，则上一级需要尝试另一个单词。 
 Revert（把插槽放回去）然后回去。 
  

以下是我根据您的要求制作的简短但完整的示例。

皮肤猫的方法不止一种。
我的代码交换了第1步和第2步，并在一个填充循环中结合了第4步到第6步。

关键点：

• 使用格式化程序使代码符合您的风格。


• 2D纸板存储在行主要订单中的线性字符数组。


• 这允许通过 clone（）保存电路板并通过 arraycopy 。


• 创建时，会从两个方向扫描两个插槽中的插槽。


• 两个插槽列表由同一个循环解决，主要区别在于如何插槽已被填充。


• 显示重复过程，因此您可以看到它是如何工作的。


• 进行了许多假设。没有单个字母的插槽，相同的所有单词，电路板都是正确的等等。


• 要耐心等待。学习新的东西并给自己时间吸收它。

资料来源：

< pre class =lang-java prettyprint-override> import java.awt.Point;
import java.util。*;
import java.util.function.BiFunction;
import java.util.function.Supplier;
import java.util.stream.Stream;

公共类填字游戏{

public static void main（String [] args）{
new Crossword（Arrays.asList（5 4 4 \ n＃ _＃_＃\ n _____ \ n＃_ ## _ \ n＃_ ## _ \ nununa \ nmusic \\\
can\\\
hi.split（\ n）））;
new Crossword（Arrays.asList（6 6 4 \ n ## _ ### \ n＃____＃\ n ___＃__ \ n＃_ ## _＃\ n＃____＃ \ n ## _ ### \ nnice \ npain\\\
pal \ nid.split（\ n）））;
}

private final int height，width; //董事会规模
私人最终char []董事会; //当前的董事会状态。 _未填充。 ＃被阻止了。其他字符已填充。
private final Set< String>话; //单词列表
private final Map< Point，Integer> vertical = new HashMap<>（），horizo​​ntal = new HashMap<>（）; //垂直和水平槽

private String indent =; //用于格式化日志
private void log（String message，Object ... args）{System.out.println（indent + String.format（message，args））; }

私人填字游戏（List< String> lines）{
//解析输入数据
final int [] sizes = Stream.of（lines.get（0）.split （\\\\ +））。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（）））;
//找到水平槽然后垂直槽
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 ++）; //查找插槽大小
horizo​​ntal.put（new Point（x，y），size）;
x + = size; //跳过这个水平位置
}
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 ++）; //查找插槽大小
vertical.put（new Point（x，y），size）;
y + = size; //跳过这个垂直位置
}
log（A+宽度+x+高度+板，+ vertical.size（）+垂直，+ horizo​​ntal.size（ ）+水平。）;
//解决填字游戏，水平首先然后垂直
final boolean solve = solveHorizo​​ntal（）;
//显示完全填充或完全空的板。
for（int i = 0; i< board.length; i ++）{
if（i％width == 0）System.out.println（）;
System.out.print（board [i]）;
}
System.out.println（已解决？\ n：\ nnNo solution found\\\
）;
}

//帮助检查或设置单元格的函数
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）=='_'; }

//当成功移动到求解垂直时，适合所有水平槽。
private boolean solveHorizo​​ntal（）{
return solve（horizo​​ntal，this :: fitHorizo​​ntal，horizo​​ntal，this :: solveVertical）;
}
//适合所有垂直位置，完成后报告成功
private boolean solveVertical（）{
return solve（vertical，this :: fitVertical，vertical，（） - > true）;
}

//重复每个插槽，尝试循环中的每个单词。当所有这类插槽成功填充后，运行下一阶段。
private boolean solve（Map< Point，Integer> slot，BiFunction< Point，String，Boolean> fill，String dir，Supplier< Boolean> next）{
if（slot.isEmpty（））return next 。得到（）; //如果完成，请转到下一阶段。
final Point pos = slot.keySet（）。iterator（）。next（）;
final int size = slot.remove（pos）;
final char [] state = board.clone（）;
/ *尝试每个单词* / indent + =;
for（String word：words）{
if（word.length（）！= size）continue;
/ *如果单词适合，重复。如果重复成功，完成！ * / log（在％d，％d处尝试％s％s，word，dir，pos.x，pos.y）;
if（fill.apply（pos，word）&& solve（slot，fill，dir，next））
return true;
/ *不匹配。恢复板并尝试下一个单词* / log（％s在％d，％d处失败％s，word，dir，pos.x，pos.y）;
System.arraycopy（state，0，board，0，board.length）;
}
/ *不匹配。恢复槽和报告失败* / indent = indent.substring（0，indent.length（） - 2）;
slot.put（pos，size）;
返回false;
}

//尝试在插槽中插入一个单词。如果存在冲突，则返回false。
private boolean fitHorizo​​ntal（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））返回false; //冲突
set（x + i，y，word.charAt（i））;
}
返回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））返回false; //冲突
set（x，y + i，word.charAt（i））;
}
返回true;
}
}


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

I have a crossword puzzle and a list of words which can be used to solve it (words can be placed multiple times or not even once). There is always a solution for the given crossword and word list.

I searched for clues on how to solve this problem and found out that it is NP-Complete. My maximal crossword size is 250 by 250, the maximal length of the list (amount of words which can be used to solve it) is 200. My goal is to solve crosswords of this size by brute force/backtracking, which should be possible within a few seconds (this is a rough estimation by me, correct me if I am wrong).

Example:

A list of given words which can be used to solve the crossword:

• can
• music
• tuna
• hi

The given empty crossword (X are fields which cannot be filled out, the empty fields need to be filled):

The solution:

Now my current approach is to represent the crossword as a 2-D array and search for empty spaces (2 iterations over the crossword). Then I match words to empty spaces depending on their length, then I try all combinations of words to empty spaces which have the same length. This approach got very messy very fast, I got lost trying to implement this, is there a more elegant solution?

解决方案

The basic idea you have is pretty sensible:

1. Identify slots on the board.
2. Try each slot with each word that fits.
3. If every slots can be filled without conflict, it is solved.

It's an excellent plan. The next step is to translate it into a design. For small program like this we can go straight to pseudo code. The gist of it, as explained by other answers, is 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.

Below is a short but complete example that I cooked up from your requirements.

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.

Key points:

• Use a formatter to fit the code to your style.
• The 2D board is stored in a linear character array in row-major order.
• This allow the board to be save by clone() and restored by arraycopy.
• On creation, the board is scanned for slots in two passes from two directions.
• The two slot lists are solved by the same loop, differ mainly in how the slots are filled.
• The recur process is displayed, so you can see how it works.
• Many assumptions are made. No single letter slot, all words in same case, board is correct etc.
• Be patient. Learn whatever is new and give yourself time to absorb it.

Source:

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.

这篇关于解决填字游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！