スドク解法の最適化

Question

スムクトソルバーを代入すると、私はスドクの空白セルを解く際に問題に遭遇しました。私は独特のソリューションで細胞を簡単に解決することができますが、複数のソリューション（現在の状態では複数のソリューション）があるセルに出会うと、次の空白に移動して、できるだけ多くのそれに応じて私のソリューションを価値あるものにすることができます。

私の問題は、自分がどの空白値を保持しているかを把握する方法がわからないことです。ここで

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」を見つける無限ループにはまります数独。

この機能を正しく実装する方法はありますか？

Answer 1

まず私は、いくつかの定型でコードをラップしてみましょう、私たちは簡単に 何かを実行することができます。

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" 

ここにいくつかの問題があります。

1. 文字列から十分な文字を削除しません。その位置で指定された空白も削除する必要があります。
2. nextBlankでは、空白で指定されたインデックスにドロップされた文字列の長さを追加する必要があります。そうしないと、最後の空白の位置を基準にしていくらかのゴミの位置が取得されます。私はインデックスを文字列表現に使用し、別の関数の最後のステップとして位置を計算することをお勧めします。