在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中解决数独

回答

相关问题