Судоку рекурсивный возврат в Go - PullRequest
Новая
       71

Судоку рекурсивный возврат в Go

0 голосов
/ 18 февраля 2020

Я пытаюсь решить головоломку судоку в 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
}

Она вносит изменения в игровую доску, проверяет, возможна ли она, и сохраняет это значение в переменной. Он меняет доску обратно на то, что было, затем возвращает бул. Эта функция вызывается из следующей функции 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 игровую площадку, содержащую все мой код Go Детская площадка

Следующее видео демонстрирует то, что я пытаюсь выполнить sh в python.

Computerphile Video

Решение головоломки: Решение головоломки

Ответы [ 2 ]

1 голос
/ 18 февраля 2020

Ваша программа работает отлично. Дважды проверьте вторую последнюю строку вашей матрицы:

У вас есть: 

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

Но это должно быть 

{0, 0, 0, 4, 1, 9, 0, 0, 5},
0 голосов
/ 18 февраля 2020

Окончательный рабочий код: 

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)
}
...