Go 中的数独递归回溯

Question

我正在尝试使用递归回溯算法解决 Go 中的数独难题。我创建了检查特定行、列或块是否有效（即没有重复值）的辅助函数，以及打印出当前状态的函数。我已经对所有这些进行了多次测试，所以我认为它们不是导致问题的原因。我创建了以下函数来测试是否可以使用潜在的游戏板。

func cellValid(gameBoard *[9][9]int, value int, y int, x int) bool {
    oldVal := gameBoard[y-1][x-1]
    gameBoard[y-1][x-1] = value
    row := getRow(gameBoard, y)
    col := getCol(gameBoard, x)
    block := getBlock(gameBoard, x, y)
    possible := unitValid(row) && unitValid(col) && unitValid(block)
    gameBoard[y-1][x-1] = oldVal
    return possible
}

它对游戏板进行了更改，检查是否可行并将该布尔值存储在变量 possible 中。它将棋盘变回原来的样子 returns 布尔值。从以下 solveBoard 函数调用此函数。

func solveBoard(gameBoard *[9][9]int) {
    for row := 1; row <= 9; row++ {
        for col := 1; col <= 9; col++ {
            if gameBoard[row-1][col-1] == 0 {
                for value := 1; value <= 9; value++ {
                    if cellValid(gameBoard, value, row, col) {
                        gameBoard[row-1][col-1] = value
                        solveBoard(gameBoard)
                        gameBoard[row-1][col-1] = 0
                    }
                }
                return
            }
        }
    }
    printBoard(gameBoard)
    return
}

在运行文件上我没有输出。

func main() {
    var gameBoard = [9][9]int{
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}}

    solveBoard(&gameBoard)
}

这是一个包含我所有代码的围棋游乐场 link。 Go Playground

以下视频演示了我在 python 中试图完成的工作。

Computerphile Video

谜题解法： Puzzle solution

Answer 1

您的程序运行良好。仔细检查矩阵的倒数第二行：

你有：

{0, 0, 0, 4, 1, 7, 0, 0, 5},

但应该是

{0, 0, 0, 4, 1, 9, 0, 0, 5},

Answer 2

最终的工作代码是。

package main

import (
    "fmt"
)

func printBoard(gameBoard *[9][9]int) {
    for y := 0; y < 9; y++ {
        if y == 3 || y == 6 {
            fmt.Println("\n---------")
        } else {
            fmt.Println("")
        }
        for x := 0; x < 9; x++ {
            if x == 3 || x == 6 {
                fmt.Print("|", gameBoard[y][x])
            } else {
                fmt.Print("", gameBoard[y][x])
            }
        }
    }
    fmt.Println("")
}

func unitValid(unit [9]int) bool {
    for value := 1; value <= 9; value++ {
        count := 0
        for index := 0; index < 9; index++ {
            if unit[index] == value {
                count++
            }
        }
        if count > 1 {
            return false
        }
    }
    return true
}

func getRow(gameBoard *[9][9]int, row int) [9]int {
    return gameBoard[row-1]
}

func getCol(gameBoard *[9][9]int, col int) [9]int {
    var column [9]int
    for row := 0; row < 9; row++ {
        column[row] = gameBoard[row][col-1]
    }
    return column
}

func getBlock(gameBoard *[9][9]int, row, col int) [9]int {
    i := whatBlock(col)*3 - 2
    j := whatBlock(row)*3 - 2
    var block [9]int
    block[0] = gameBoard[j-1][i-1]
    block[1] = gameBoard[j-1][i]
    block[2] = gameBoard[j-1][i+1]
    block[3] = gameBoard[j][i-1]
    block[4] = gameBoard[j][i]
    block[5] = gameBoard[j][i+1]
    block[6] = gameBoard[j+1][i-1]
    block[7] = gameBoard[j+1][i]
    block[8] = gameBoard[j+1][i+1]
    return block
}

func whatBlock(val int) int {
    if val >= 1 && val <= 3 {
        return 1
    } else if val >= 4 && val <= 6 {
        return 2
    } else if val >= 7 && val <= 9 {
        return 3
    }
    return 0
}

func cellValid(gameBoard *[9][9]int, value int, y int, x int) bool {
    oldVal := gameBoard[y-1][x-1]
    gameBoard[y-1][x-1] = value
    row := getRow(gameBoard, y)
    col := getCol(gameBoard, x)
    block := getBlock(gameBoard, y, x)
    possible := unitValid(row) && unitValid(col) && unitValid(block)
    gameBoard[y-1][x-1] = oldVal
    return possible
}

func solveBoard(gameBoard *[9][9]int) {
    for row := 1; row <= 9; row++ {
        for col := 1; col <= 9; col++ {
            if gameBoard[row-1][col-1] == 0 {
                for value := 1; value <= 9; value++ {
                    if cellValid(gameBoard, value, row, col) {
                        gameBoard[row-1][col-1] = value
                        solveBoard(gameBoard)
                        gameBoard[row-1][col-1] = 0
                    }
                }
                return
            }
        }
    }
    printBoard(gameBoard)
    return
}

func main() {
    var gameBoard = [9][9]int{
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}}

    solveBoard(&gameBoard)
}

Go 中的数独递归回溯

Sudoku Recursive Backtracking in Go

sudoku

backtracking

go

recursive-backtracking