在Scala中解決數獨

我正在學習Scala（並且是函數式編程的新手）。我已經創建了一個數獨檢查器（稍後會作爲一個遊戲，您可以在數獨中實際設置數字，也可能是一個自動數獨求解器）。在Scala中解決數獨

檢查行和列是否正確可以正常工作，並且功能導向。

雖然檢查3x3方塊是正確的，但我寫了一個非常難看的方法（參見下面的代碼）。

關於我如何才能解決這個更容易和更斯卡拉什的任何提示？我已經找到了方法.slice（from，until），.splitAt（until），.sliding（size，step），並嘗試再次使用'transpose'做某些事情。雖然我不能'想出一個工作（更多）功能的方式來做到這一點。

class Sudoku(){ 
    val sudoku = 
    Array(
     Array(0, 5, 0, 3, 0, 9, 0, 2, 6), 
     Array(3, 8, 9, 4, 2, 0, 1, 5, 7), 
     Array(4, 0, 6, 1, 0, 0, 0, 8, 9), 
     Array(0, 1, 3, 7, 9, 8, 0, 0, 4), 
     Array(0, 0, 8, 0, 0, 0, 5, 0, 0), 
     Array(0, 6, 0, 0, 0, 3, 0, 0, 0), 
     Array(0, 0, 1, 9, 3, 0, 0, 4, 0), 
     Array(9, 3, 5, 6, 4, 0, 8, 0, 1), 
     Array(0, 0, 2, 8, 7, 0, 0, 0, 5) 
) 

    def checkSudoku(): Unit ={ 
    println(check(sudoku)) 
    } 

    private def check(sudoku: Array[Array[Int]]): Boolean = checkRows(sudoku) && checkCols(sudoku) && checkSquars(sudoku) 
    private def checkCols(sudoku: Array[Array[Int]]) = checkRows(sudoku.transpose) 
    private def checkRows(sudoku: Array[Array[Int]]): Boolean = sudoku.forall(row => checkRow(row)) 
    private def checkRow(row: Array[Int]): Boolean = row.distinct.length == row.length 


    private def checkSquars(sudoku: Array[Array[Int]]): Boolean ={ 
    val squared : Array[Array[Int]] = Array.ofDim[Int](1,3) 

    for(i <- 0 to (sudoku.length-1)/3) { 
     for(o <- 0 to (sudoku(i).length-1)/3) { 
     squared((i*3)+o) = sudoku(0+(i*3)).slice(0+(o*3), 3+(o*3)) ++ sudoku(1+(i*3)).slice(0+(o*3), 3+(o*3)) ++ sudoku(2+(i*3)).slice(0+(o*3), 3+(o*3)) 
     } 
    } 
    squared.forall(row => checkRow(row)) 
    } 
} 

val sudoku = new Sudoku() 
sudoku.checkSudoku();

來源

2017-04-06 Kevin

checkRow方法在哪裏？ – nmat

下面的checkRows（）方法 private def checkRow（row：Array [Int]）：Boolean = row.distinct.length == row.length – Kevin

下面是一個（略brainfucky）方式做checkSquares方法：

val rowBlocks = sudoku.grouped(3).toArray 
def splitRow(row: Array[Int]) = row.grouped(3).toArray 

val squares = rowBlocks.map(block => block.map(splitRow).transpose)

你應該說服自己，squares是數獨的平方的一個3x3的陣列。現在你只需要檢查一下條件：

squares.forall(_.forall(sq => sq.flatten.distinct.length == sq.flatten.length))

來源

2017-04-06 22:55:15

這裏有一個替代方法來獲得所有的方塊作爲線。我試圖使其更易於閱讀：

val squareSize = 3 
    val boardSize = sudoku.length 

    val squareLines = for { 
    rowStart <- List.range(0, boardSize, squareSize) 
    colStart <- List.range(0, boardSize, squareSize) 
    } yield { 
    List.range(0, squareSize).flatMap { 
     i => 
     sudoku(rowStart + i).slice(colStart, colStart + squareSize) 
    } 
    }

就可以檢查squareLines與checkRow就像你在你的方法做。

的rowStart和colStart雙也可以在List.range使用combinations(2)產生的，但我想這將是這種情況太冗長。

來源

2017-04-06 23:53:56 nmat

我開始使用列表/數組來管理拼圖，但很久以後，我發現使用地圖更好。

接下來，使用Array [Set [Int]]而不是Array [Array [Int]]來使用Set刪除組中的重複項。

我包含了函數conflict(...)來檢查衝突。您可以使用它作爲參考。隨着我不斷進行修改（即我不再使用此功能，因爲我有其他方法來達到相同的目的，但達到了其目的），並迅速將這個答案放在一起，它們可能無法編譯。如果你需要幫助，我希望你能明白並給我留言。

val digits = ('1' to '9').mkString 
val alphas = ('A' to 'I').mkString 

def cross(rows: String, cols: String) = for { 
    row <- rows 
    col <- cols 
} yield {"" + row + col} 

val verticals = digits.map(d => cross(alphas, d.toString)) 

val horizontals = alphas.map(a => cross(a.toString, digits)) 

val blocks = for { 
    rowBlk <- alphas.grouped(3) 
    colBlk <- digits.grouped(3) 
} yield (cross(rowBlk, colBlk)) 

val all = horizontals ++ verticals ++ blocks 

def everyone = cross(alphas, digits).foldLeft(Map.empty[String, Set[Set[Int]]])((m,a) => m + (a -> (all.filter(_.contains(a)).map(_.toSet).toSet))) 

def conflict(cell: String, solution: Map[String, Set[Int]]) = 
    if (everyone(cell) 
    .map(cells => cells.toList.foldLeft(List.empty[Int])((chars, c) => 
     if (solution(c).size > 1) chars else chars ++ solution(c).toList)) 
     .forall(xs => xs.size == xs.distinct.size)) solution else Map.empty

來源

2017-05-30 07:57:30 thlim

在Scala中解決數獨

回答

相關問題