优化数独求解方法

为一个任务制作一个数独求解器，我遇到了解决数独的空白单元格的问题。我可以很容易地解决具有独特解决方案的细胞，但是当我遇到具有多种解决方案的单元格（在数独的当前状态下）时，我想转到下一个空白处，尝试填充尽可能多的数独，然后“尝试“价值观并相应地分出我的解决方案。优化数独求解方法

我的问题是，我不知道如何跟踪我所处的空白值。

blank :: Sudoku -> Pos 
blank sudoku 
    | elem '.' $ toString sudoku = ((positInRow `div` 9), (positInRow `mod` 9)) 
    | otherwise = error "no blanks" 
    where 
     positInRow = fromJust $ elemIndex '.' $ toString sudoku 

nextBlank :: Sudoku -> Pos -> Pos 
nextBlank sudoku (x, y) 
    | elem '.' $ drop (x*9+y) $ toString sudoku = blank (fromString $ drop (x*9+y) $ toString sudoku) 
    | otherwise = error "no blanks"

这是我尝试的解决方案，但如果我尝试递归解决数独，它会陷入无限循环寻找相同的“nextBlank”如果原来的一个空白不更新的价值数独。

有没有办法正确实现这个功能？

来源

2017-05-25 420fedoras

首先让我包你的代码在一些样板，所以我们可以运行东西容易：

module RandomNoise where 

import Data.Maybe 
import Data.List 

type Pos = (Int, Int) 
type Sudoku = String 

toString :: Sudoku -> String 
toString = id 

fromString :: String -> Sudoku 
fromString = id 

blank :: Sudoku -> Pos 
blank sudoku 
    | elem '.' $ toString sudoku = (positInRow `div` 9, positInRow `mod` 9) 
    | otherwise = error "no blanks" 
    where 
    positInRow = fromJust $ elemIndex '.' $ toString sudoku 

nextBlank :: Sudoku -> Pos -> Pos 
nextBlank sudoku (x, y) 
    | elem '.' $ drop (x*9+y) $ toString sudoku = blank (fromString $ drop (x*9+y) $ toString sudoku) 
    | otherwise = error "no blanks" 

testSudoku = "uiae.uiae.uiae.uiae" 

firstBlank = blank testSudoku 
secondBlankOrNot = nextBlank testSudoku firstBlank

如果你打开ghci中并加载一个文件的内容，你可以看到，

firstBlank = (0,4) 
secondBlank = (0,0)

和

drop (0*9+4) testSudoku

收率

".uiae.uiae.uiae"

所以这里有几个问题。

您不会从字符串中删除足够多的字母。您还需要删除该位置指定的空白。
在nextBlank中，您需要将拖动的字符串的长度添加到空白处确定的索引中，然后再将它们转换为位置，否则您将获得某种相对于最后一个空白位置的垃圾位置。我建议在字符串表示中使用索引，并将其作为单独函数的最后一步来计算位置。

来源

2017-05-25 07:29:40 Krom

优化数独求解方法

回答

相关问题