扫雷就像在Haskell中生成的板 - 想法

Question

首先,我想描述一个问题(它与Minesweeper非常相似).我们给出了一个n × m的板和一个特殊点列表(x,y,z).每个点都说在场(x,y)周围我们需要准确放置z矿.

你也可以在这里找到更好的问题描述:Prolog:从哪里开始解决扫雷般的问题？ (它是在prolog但不关心编程语言)

我们的任务是生成满足任务条件的所有可能的板.例如:设n = 3,m = 3并L = [(2,2,1)]具有特殊的点列表,所以可能的解决方案是:

[[' ', ' ', ' '], [' ', 1, ' '], [' ', ' ', *]]

其中''是空格,'*'是我的.

我想在Haskell中找到一些有用的想法来编写这个问题.我唯一的想法是生成所有可能的设置地雷组合或使用回溯,但我发现很难在haskell中实现.

有什么想法怎么做？

Answer 1

使用list monad在Haskell中回溯非常简单.这是一个例子:

import Control.Monad (guard)

pairs :: [(Int,Int)]
pairs = do
    x <- [1..10]
    y <- [1..x]
    guard (even (x + y))
    return (x,y)

会给你所有对(x,y)这样y <= x和x + y是偶数.

所以你会想要类似的东西

type Board = ...

insertMine :: (Int,Int) -> Board -> [Board]
-- return all ways of inserting a mine adjacent to the given coordinate

insertMines :: (Int,Int) -> Board -> [Board]
insertMines p board = do
    b1 <- insertMine p board
    b2 <- insertMine p b1
    b3 <- insertMine p b2
    return b3

有很多方法可以使这更简单,更抽象,但我试图在我认为你的水平附近举一个例子.通过列表monad回溯是一个很好的方式来舒适monad!