解非图（Picross） [英] Solving Nonograms (Picross)

问题描述

今天是星期五下午，让我们解决一个有趣的难题/算法问题。

我最喜欢的Nintendo DS游戏之一是

_{（来源：< a href = http://steam-punk.net/images/picross1.jpg rel = nofollow noreferrer> steam-punk.net ）}

该行可能的解决方案包括：

<sub>（来源：

（来源： steam- punk.net ）</sub>

等。

4 5简单地Ť告诉您，在该行的某个位置，先填充了4个连续的块，然后填充了5个连续的块。这将是唯一填充的块，并且未定义它们之前/之后的空间。

当所有行和列均满足其定义且没有任何矛盾时，难题就解决了。

概念上极其简单的游戏，但是手动解决其中的一些问题可能需要一段时间。 Picross DS的谜题大小逐渐增加到25x20网格，通常需要我花大约半个小时的时间来解决。

但是，在我看来，它总是是一个非常容易编写程序来解决的游戏。我从来没有解决过这个问题，但是也许有些人会喜欢这个挑战。如果发布了很多解决方案，我将在一个大难题上对它们进行基准测试，类似于 Paolo Bergantino在这里用他的Boggle问题进行了。 非图维基百科页面上有很多信息，介绍了解决难题的方法，

这是TylerK的Picross中难题＃1的易于解析的定义，因此您可以为程序提供内容。第1行是拼图尺寸（可能不必要），第2行是行定义，第3行是列定义。这只是想到的第一件事，因此，如果有人可以想到更好的输入格式，请随时评论或编辑此帖子以将其包括在内。

  15 15 
 15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1 ，1 3 2 1,2 2 1 2 1,3 3 2 1,9 
 4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 3,3 3 3,4 1,10 3,10 
  

解决方案

是的，问题是NP完全的，但这仅意味着随着拼图的大小增长，您（相当多）陷入了呈指数增长的运行时间。但是在现实生活中，拼图的大小并没有增长。几乎没有人会费心去制作大于100x100的拼图，而绝大多数拼图都小于50x50。实际上，构建一个求解器可以在几分之一秒内解决95％的书籍和杂志上发布的难题，这并不是特别困难。

不太明显的是，有一小部分难题非常令人讨厌，会导致运行混乱，最简单的求解器爆炸的时间。其中大多数都是设计不好的难题，人类也很难或无法解决，但其中一些难题特别聪明，经验丰富的人类求解者可以使用比大多数AI程序所能解决的更深刻的见解轻松解决。

我已经编写了自己的求解器，可以很快解决大多数难题，并且已经完成了对许多其他求解器进行调查，并比较基准性能。我还将讨论一类有趣的硬难题（多米诺骨牌难题），该难题演示了如何为聪明的人解决一些难题，而这些难题对于大多数程序却非常困难。在调查中将找到指向我的求解器和Domino拼图的链接。

我认为仍有很大的改进空间，并鼓励有新想法的人采取一枪。但是，值得注意的是，显而易见的事情已经完成了，再次进行并没有太大用处。

it's Friday afternoon, let's have a fun puzzle/algorithm problem to solve.

One of my favorite Nintendo DS games is Picross DS. The game is quite simple, it involves solving puzzles called Nonograms. You can try a simple online Picross clone here: TylerK's Picross.

Nonograms are a grid, with sequences of numbers defined for every row and column of the grid. The numbers define blocks of "filled in" squares for that row/column, but the unfilled areas on either sides of the blocks are not defined. For example, if you have a row that looks like this:

_{(source: steam-punk.net)}

Possible solutions for that row would include:

<sub>(source: steam-punk.net)

(source: steam-punk.net)</sub>

etc.

The "4 5" simply tells you that, somewhere in the row, there are 4 sequential blocks filled in, followed by 5 sequential blocks filled in. Those will be the only blocks filled in, and the amount of space before/after them are not defined.

A puzzle is complete when all rows and columns meet their definitions, without any contradictions.

Extremely simple game in concept, but it can take quite a while to solve some of them manually. Picross DS's puzzles gradually increase in size up to 25x20 grids, which would generally take me about half an hour to solve.

However, it always occurs to me that it'd be a pretty easy game to write a program to solve. I've never gotten around to it, but perhaps some people here will enjoy the challenge. If a decent number of solutions are posted, I'll benchmark them on a large puzzle against each other, similar to what Paolo Bergantino did here with his Boggle question. There's quite a bit of information on the Nonogram Wikipedia page about methods of attacking a puzzle, if you want to reference that.

Here's an easy-to-parse definition of Puzzle #1 from TylerK's Picross, so you have something to feed a program. Line 1 is puzzle dimensions (probably unnecessary), line 2 is row definitions, line 3 is column definitions. This is just the first thing that came to mind, so if anyone can think of a better input format, feel free to comment or edit this post to include it.

15 15
15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1,1 3 2 1,2 2 1 2 1,3 3 2 1,9
4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 3,3 3 3,4 1,10 3,10

解决方案

Yes, the problem is NP-complete, but that only means that you are (pretty much) stuck with exponentially growing run-times as the size of the puzzle grows. But in real life puzzle sizes don't grow. Hardly anyone bothers to build puzzles that are bigger than 100x100 and the vast majority are smaller than 50x50. Building a solver that will solve 95% of the puzzles published in books and magazines in a fraction of second is actually not particularly challenging. A fairly straight-forward depth-first search system will do it.

What's less obvious is that there is a small fraction of puzzles that are quite nasty and will cause run-times to explode for most simple solvers. Most of these are badly designed puzzles that are also difficult or impossible for humans to solve, but some are particularly clever puzzles that experienced human solvers can readily solve, using deeper insights than most AI programs can manage.

I've written a solver of my own that will solve most puzzles very quickly, and I've done a survey of many other solvers with benchmark results comparing their performance. I also have a discussion of an interesting class of hard puzzles (the Domino puzzles) that demonstrates how some puzzles that are not hard for a clever human prove very hard for most programs. Links to my solver and the Domino Puzzle will be found in the survey.

I think there is still a lot of room for improvement and would encourage people with fresh ideas to take a shot at it. But it's worth noting that the obvious things have been done and there isn't much use in doing them again.

这篇关于解非图（Picross）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！