Go 中的数独递归回溯

从现在开始，我们要努力学习啦！今天我给大家带来《Go 中的数独递归回溯》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

我正在尝试使用递归回溯算法解决 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 中。它将棋盘更改回原来的样子，然后返回布尔值。该函数是从以下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)
}

这是包含我所有代码的 go 演示的链接。 去演示

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

电脑爱好者视频

谜题解答： 谜题解答

解决方案

你的程序运行得很好。仔细检查矩阵的倒数第二行：

你有：

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

但应该是

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

最终的工作代码是。

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 中的数独递归回溯》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！