当前位置： 文江博客话题详情

这个循环回溯时实现了什么？ （数独求解器）

发布于 2025-01-10 05:44:15 字数 5696 浏览 0 评论 0原文

我编写了一个生成有效随机数独板的函数。尽管如此，我对为什么需要 i 循环感到困惑。

如果我删除这个循环，我的程序将不再正确运行。一旦到达无效位置（回溯），它就会一起结束。

在大多数实现中，会检查i以查看它是否可以位于空闲方块处。虽然，我使用的是随机数，而不是使用这个 i var。

那么为什么我需要这个循环呢？我的程序在回溯时是否会返回到迭代？

去游乐场演示

// Creates a valid random BoardArray
func (board *Board) GenerateBoard(row int, col int) bool {
  // get the next available pos on board
  freePos := board.FreePos()
  if freePos == nil {
    // no more positions, done
    return true
  }

  freeRow := freePos[0]
  freeCol := freePos[1]

  // generate random number
  randNum := rand.Intn(10-1) + 1
  rand.Seed(time.Now().UnixNano())

  // this i loop is the confusion?
  for i := 0; i <= 8; i++ {

    // check if we can place at freePos
    if board.ValidPos(randNum, freeRow, freeCol) {
      // valid, place
      board.BoardArray[freeRow][freeCol] = randNum

      // recursion
      if board.GenerateBoard(freeRow, freeCol + 1) {
        return true
      } else {
        // backtrack, set back to 0
        board.BoardArray[freeRow][freeCol] = 0
      }
    }
  }
  return false
}

board/board.go

package board

import (
    "fmt"
    "math/rand"
    "time"
)

type Board struct {
    BoardArray [9][9]int
}

// Creates a valid random BoardArray
func (board *Board) GenerateBoard(row int, col int) bool {
    // get the next available pos on board
    freePos := board.FreePos()
    if freePos == nil {
        // no more positions, done
        return true
    }

    freeRow := freePos[0]
    freeCol := freePos[1]

    // generate random number
    randNum := rand.Intn(10-1) + 1
    rand.Seed(time.Now().UnixNano())

    for i := 0; i <= 8; i++ {
        if board.ValidPos(randNum, freeRow, freeCol) {
            board.BoardArray[freeRow][freeCol] = randNum

            if board.GenerateBoard(freeRow, freeCol + 1) {
                return true
      } else {
        board.BoardArray[freeRow][freeCol] = 0
      }
        }
    }
    return false
}

// Solves BoardArray (existing board)
func (board *Board) SolveBoard(cellVal int, row int, col int) bool {
    // get the next available pos on board
    freePos := board.FreePos()
    if freePos == nil {
        // no more positions, done
        return true
    }

    freeRow := freePos[0]
    freeCol := freePos[1]

    for i := 1; i <= 9; i++ {
        // board.PrintBoard()
        // fmt.Printf("Checking: row:%d,col:%d,val:%d \n", freeRow, freeCol, i)
        if board.ValidPos(i, freeRow, freeCol) {
            // fmt.Printf("Valid! row:%d, col:%d, val:%d \n", freeRow, freeCol, i)
            board.BoardArray[freeRow][freeCol] = i
            if board.SolveBoard(i, freeRow, freeCol + 1) {
                return true
            }
            board.BoardArray[freeRow][freeCol] = 0
        }
    }
    return false
}

// Checks all valid pos funcs
// Returns true if valid
func (board *Board) ValidPos(cellVal int, row int, col int) bool {
    isValidInRow := board.ValidPosInRow(cellVal, row)
    isValidInCol := board.ValidPosInCol(cellVal, col)
    isValidInSubGrid := board.ValidPosInSubGrid(cellVal, col, row)

    if isValidInRow && isValidInCol && isValidInSubGrid {
        return true
    }
    return false
}

// Checks next free pos on board
// Returns [row,col] of free pos
func (board *Board) FreePos() []int {
    for row := 0; row < len(board.BoardArray); row++ {
        for col := 0; col < len(board.BoardArray[row]); col++ {
            if board.BoardArray[row][col] == 0 {
                validPos := []int{row, col}
                return validPos
            }
        }
    }
    return nil
}

// Check if cellVal can be placed in the row rowN
// Returns true if valid pos
func (board *Board) ValidPosInRow(cellVal int, row int) bool {
    for i := 0; i < len(board.BoardArray[row]); i++ {
        currentValue := board.BoardArray[row][i]
        if currentValue == cellVal {
            return false
        }
    }
    return true
}

// Check if cellVal can be placed in the column colN
// Returns true if valid pos
func (board *Board) ValidPosInCol(cellVal int, col int) bool {
    for i := 0; i < len(board.BoardArray[col]); i++ {
        currentValue := board.BoardArray[i][col]
        if currentValue == cellVal {
            return false
        }
    }
    return true
}

// Check if cellVal can be placed in the 3x3 subgrid
// Returns true if valid pos
func (board *Board) ValidPosInSubGrid(cellVal int, colN int, rowN int) bool {
    rowStart := (rowN / 3) * 3
    colStart := (colN / 3) * 3

    // Go through the subgrid,
    // check if any values are equal to cellVal
    for row := rowStart; row < rowStart+3; row++ {
        for col := colStart; col < colStart+3; col++ {
            subGridCell := board.BoardArray[row][col]
            if subGridCell == cellVal {
                return false
            }
        }
    }
    return true

}

// Helper Method:
// Prints board nicely
func (board *Board) PrintBoard() {
  for row := 0; row < len(board.BoardArray); row++{
    fmt.Printf("row:%d \t", row)
    for col := 0; col < len(board.BoardArray[row]); col++{
      fmt.Printf("%d|", board.BoardArray[row][col])
    }
    fmt.Println()
  }
}

main.去

package main

import (
    "board"
)

func main() {
    grid := [9][9]int{}

  board := board.Board{BoardArray: grid}
  board.GenerateBoard(0, 0)

  board.PrintBoard()

}
原文

I have written a function that generates a valid random sudoku board. Although, I am confused on why I need the i loop.

If I remove this loop my program no longer runs correctly. Once it hits an invalid position (backtracks) it ends all together.

In most implementations, the i is checked to see if it can be positioned at the free square. Although, I am using random numbers and not using this i var.

Therefore why do I need this loop? Does my program return back to the iteration when backtracking?

go playground demo

// Creates a valid random BoardArray
func (board *Board) GenerateBoard(row int, col int) bool {
  // get the next available pos on board
  freePos := board.FreePos()
  if freePos == nil {
    // no more positions, done
    return true
  }

  freeRow := freePos[0]
  freeCol := freePos[1]

  // generate random number
  randNum := rand.Intn(10-1) + 1
  rand.Seed(time.Now().UnixNano())

  // this i loop is the confusion?
  for i := 0; i <= 8; i++ {

    // check if we can place at freePos
    if board.ValidPos(randNum, freeRow, freeCol) {
      // valid, place
      board.BoardArray[freeRow][freeCol] = randNum

      // recursion
      if board.GenerateBoard(freeRow, freeCol + 1) {
        return true
      } else {
        // backtrack, set back to 0
        board.BoardArray[freeRow][freeCol] = 0
      }
    }
  }
  return false
}

board/board.go

package board

import (
    "fmt"
    "math/rand"
    "time"
)

type Board struct {
    BoardArray [9][9]int
}

// Creates a valid random BoardArray
func (board *Board) GenerateBoard(row int, col int) bool {
    // get the next available pos on board
    freePos := board.FreePos()
    if freePos == nil {
        // no more positions, done
        return true
    }

    freeRow := freePos[0]
    freeCol := freePos[1]

    // generate random number
    randNum := rand.Intn(10-1) + 1
    rand.Seed(time.Now().UnixNano())

    for i := 0; i <= 8; i++ {
        if board.ValidPos(randNum, freeRow, freeCol) {
            board.BoardArray[freeRow][freeCol] = randNum

            if board.GenerateBoard(freeRow, freeCol + 1) {
                return true
      } else {
        board.BoardArray[freeRow][freeCol] = 0
      }
        }
    }
    return false
}

// Solves BoardArray (existing board)
func (board *Board) SolveBoard(cellVal int, row int, col int) bool {
    // get the next available pos on board
    freePos := board.FreePos()
    if freePos == nil {
        // no more positions, done
        return true
    }

    freeRow := freePos[0]
    freeCol := freePos[1]

    for i := 1; i <= 9; i++ {
        // board.PrintBoard()
        // fmt.Printf("Checking: row:%d,col:%d,val:%d \n", freeRow, freeCol, i)
        if board.ValidPos(i, freeRow, freeCol) {
            // fmt.Printf("Valid! row:%d, col:%d, val:%d \n", freeRow, freeCol, i)
            board.BoardArray[freeRow][freeCol] = i
            if board.SolveBoard(i, freeRow, freeCol + 1) {
                return true
            }
            board.BoardArray[freeRow][freeCol] = 0
        }
    }
    return false
}

// Checks all valid pos funcs
// Returns true if valid
func (board *Board) ValidPos(cellVal int, row int, col int) bool {
    isValidInRow := board.ValidPosInRow(cellVal, row)
    isValidInCol := board.ValidPosInCol(cellVal, col)
    isValidInSubGrid := board.ValidPosInSubGrid(cellVal, col, row)

    if isValidInRow && isValidInCol && isValidInSubGrid {
        return true
    }
    return false
}

// Checks next free pos on board
// Returns [row,col] of free pos
func (board *Board) FreePos() []int {
    for row := 0; row < len(board.BoardArray); row++ {
        for col := 0; col < len(board.BoardArray[row]); col++ {
            if board.BoardArray[row][col] == 0 {
                validPos := []int{row, col}
                return validPos
            }
        }
    }
    return nil
}

// Check if cellVal can be placed in the row rowN
// Returns true if valid pos
func (board *Board) ValidPosInRow(cellVal int, row int) bool {
    for i := 0; i < len(board.BoardArray[row]); i++ {
        currentValue := board.BoardArray[row][i]
        if currentValue == cellVal {
            return false
        }
    }
    return true
}

// Check if cellVal can be placed in the column colN
// Returns true if valid pos
func (board *Board) ValidPosInCol(cellVal int, col int) bool {
    for i := 0; i < len(board.BoardArray[col]); i++ {
        currentValue := board.BoardArray[i][col]
        if currentValue == cellVal {
            return false
        }
    }
    return true
}

// Check if cellVal can be placed in the 3x3 subgrid
// Returns true if valid pos
func (board *Board) ValidPosInSubGrid(cellVal int, colN int, rowN int) bool {
    rowStart := (rowN / 3) * 3
    colStart := (colN / 3) * 3

    // Go through the subgrid,
    // check if any values are equal to cellVal
    for row := rowStart; row < rowStart+3; row++ {
        for col := colStart; col < colStart+3; col++ {
            subGridCell := board.BoardArray[row][col]
            if subGridCell == cellVal {
                return false
            }
        }
    }
    return true

}

// Helper Method:
// Prints board nicely
func (board *Board) PrintBoard() {
  for row := 0; row < len(board.BoardArray); row++{
    fmt.Printf("row:%d \t", row)
    for col := 0; col < len(board.BoardArray[row]); col++{
      fmt.Printf("%d|", board.BoardArray[row][col])
    }
    fmt.Println()
  }
}

main.go

package main

import (
    "board"
)

func main() {
    grid := [9][9]int{}

  board := board.Board{BoardArray: grid}
  board.GenerateBoard(0, 0)

  board.PrintBoard()

}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（1）

夢归不見 2025-01-17 05:44:15

让我们输出每次尝试（使用 此应用 - 请注意，为了节省空间，我已经进行了多次尝试每行）：

Board is valid? true         Board is valid? true        Board is valid? true      
row:0   6|0|0|0|0|0|0|0|0|   row:0  6|7|0|0|0|0|0|0|0|   row:0  6|7|3|0|0|0|0|0|0|
row:1   0|0|0|0|0|0|0|0|0|   row:1  0|0|0|0|0|0|0|0|0|   row:1  0|0|0|0|0|0|0|0|0|
row:2   0|0|0|0|0|0|0|0|0|   row:2  0|0|0|0|0|0|0|0|0|   row:2  0|0|0|0|0|0|0|0|0|
row:3   0|0|0|0|0|0|0|0|0|   row:3  0|0|0|0|0|0|0|0|0|   row:3  0|0|0|0|0|0|0|0|0|
row:4   0|0|0|0|0|0|0|0|0|   row:4  0|0|0|0|0|0|0|0|0|   row:4  0|0|0|0|0|0|0|0|0|
row:5   0|0|0|0|0|0|0|0|0|   row:5  0|0|0|0|0|0|0|0|0|   row:5  0|0|0|0|0|0|0|0|0|
row:6   0|0|0|0|0|0|0|0|0|   row:6  0|0|0|0|0|0|0|0|0|   row:6  0|0|0|0|0|0|0|0|0|
row:7   0|0|0|0|0|0|0|0|0|   row:7  0|0|0|0|0|0|0|0|0|   row:7  0|0|0|0|0|0|0|0|0|
row:8   0|0|0|0|0|0|0|0|0|   row:8  0|0|0|0|0|0|0|0|0|   row:8  0|0|0|0|0|0|0|0|0|

Board is valid? false        Board is valid? true        Board is valid? false      
row:0   6|7|3|3|0|0|0|0|0|   row:0  6|7|3|5|0|0|0|0|0|   row:0  6|7|3|5|7|0|0|0|0|
row:1   0|0|0|0|0|0|0|0|0|   row:1  0|0|0|0|0|0|0|0|0|   row:1  0|0|0|0|0|0|0|0|0|
row:2   0|0|0|0|0|0|0|0|0|   row:2  0|0|0|0|0|0|0|0|0|   row:2  0|0|0|0|0|0|0|0|0|
row:3   0|0|0|0|0|0|0|0|0|   row:3  0|0|0|0|0|0|0|0|0|   row:3  0|0|0|0|0|0|0|0|0|
row:4   0|0|0|0|0|0|0|0|0|   row:4  0|0|0|0|0|0|0|0|0|   row:4  0|0|0|0|0|0|0|0|0|
row:5   0|0|0|0|0|0|0|0|0|   row:5  0|0|0|0|0|0|0|0|0|   row:5  0|0|0|0|0|0|0|0|0|
row:6   0|0|0|0|0|0|0|0|0|   row:6  0|0|0|0|0|0|0|0|0|   row:6  0|0|0|0|0|0|0|0|0|
row:7   0|0|0|0|0|0|0|0|0|   row:7  0|0|0|0|0|0|0|0|0|   row:7  0|0|0|0|0|0|0|0|0|
row:8   0|0|0|0|0|0|0|0|0|   row:8  0|0|0|0|0|0|0|0|0|   row:8  0|0|0|0|0|0|0|0|0|

正如您将注意到的那样，每次尝试都会尝试不同的数字（伪随机）。如果棋盘有效，则算法会尝试将另一个数字添加到下一个空闲插槽中。需要注意的重要一点是，当棋盘无效 (6|7|3|3​​) 时，会尝试使用不同的值 (6|7|3|5) >) - 如果没有循环，第二次尝试就不会发生。

我认为简单的对代码进行更改将更容易理解为什么循环会产生区别（实际上与您的代码相同 - 它只是删除了一些不必要的工作）：

randNum := rand.Intn(10-1) + 1
if board.ValidPos(randNum, freeRow, freeCol) {
    board.BoardArray[freeRow][freeCol] = randNum
    for i := 0; i <= 8; i++ {
        if board.GenerateBoard() {
            return true
        }
    }
    board.BoardArray[freeRow][freeCol] = 0
}
return false

循环很重要，因为它控制递归调用 board.GenerateBoard() 的频率。每次进行递归调用时，代码都会尝试将另一个伪随机数添加到下一个可用槽中，尝试的次数越多，找到解决方案的可能性就越大。

Lets output each attempt made (using this app - note that to save space I have put multiple attempts on each line):

Board is valid? true         Board is valid? true        Board is valid? true      
row:0   6|0|0|0|0|0|0|0|0|   row:0  6|7|0|0|0|0|0|0|0|   row:0  6|7|3|0|0|0|0|0|0|
row:1   0|0|0|0|0|0|0|0|0|   row:1  0|0|0|0|0|0|0|0|0|   row:1  0|0|0|0|0|0|0|0|0|
row:2   0|0|0|0|0|0|0|0|0|   row:2  0|0|0|0|0|0|0|0|0|   row:2  0|0|0|0|0|0|0|0|0|
row:3   0|0|0|0|0|0|0|0|0|   row:3  0|0|0|0|0|0|0|0|0|   row:3  0|0|0|0|0|0|0|0|0|
row:4   0|0|0|0|0|0|0|0|0|   row:4  0|0|0|0|0|0|0|0|0|   row:4  0|0|0|0|0|0|0|0|0|
row:5   0|0|0|0|0|0|0|0|0|   row:5  0|0|0|0|0|0|0|0|0|   row:5  0|0|0|0|0|0|0|0|0|
row:6   0|0|0|0|0|0|0|0|0|   row:6  0|0|0|0|0|0|0|0|0|   row:6  0|0|0|0|0|0|0|0|0|
row:7   0|0|0|0|0|0|0|0|0|   row:7  0|0|0|0|0|0|0|0|0|   row:7  0|0|0|0|0|0|0|0|0|
row:8   0|0|0|0|0|0|0|0|0|   row:8  0|0|0|0|0|0|0|0|0|   row:8  0|0|0|0|0|0|0|0|0|

Board is valid? false        Board is valid? true        Board is valid? false      
row:0   6|7|3|3|0|0|0|0|0|   row:0  6|7|3|5|0|0|0|0|0|   row:0  6|7|3|5|7|0|0|0|0|
row:1   0|0|0|0|0|0|0|0|0|   row:1  0|0|0|0|0|0|0|0|0|   row:1  0|0|0|0|0|0|0|0|0|
row:2   0|0|0|0|0|0|0|0|0|   row:2  0|0|0|0|0|0|0|0|0|   row:2  0|0|0|0|0|0|0|0|0|
row:3   0|0|0|0|0|0|0|0|0|   row:3  0|0|0|0|0|0|0|0|0|   row:3  0|0|0|0|0|0|0|0|0|
row:4   0|0|0|0|0|0|0|0|0|   row:4  0|0|0|0|0|0|0|0|0|   row:4  0|0|0|0|0|0|0|0|0|
row:5   0|0|0|0|0|0|0|0|0|   row:5  0|0|0|0|0|0|0|0|0|   row:5  0|0|0|0|0|0|0|0|0|
row:6   0|0|0|0|0|0|0|0|0|   row:6  0|0|0|0|0|0|0|0|0|   row:6  0|0|0|0|0|0|0|0|0|
row:7   0|0|0|0|0|0|0|0|0|   row:7  0|0|0|0|0|0|0|0|0|   row:7  0|0|0|0|0|0|0|0|0|
row:8   0|0|0|0|0|0|0|0|0|   row:8  0|0|0|0|0|0|0|0|0|   row:8  0|0|0|0|0|0|0|0|0|

As you will note with each attempt a different number (pseudo random) is being tried. If the board is valid then the algorithm attempts to add another number into the next free slot. The important bit to note is that where the board is invalid (6|7|3|3) an attempt is made with a different value (6|7|3|5) - without the loop that second attempt would not happen.

I think that a simple change to your code will make it easier to see why the loop makes a difference (the is effectively the same as your code - it just removes some unnecessary work):

randNum := rand.Intn(10-1) + 1
if board.ValidPos(randNum, freeRow, freeCol) {
    board.BoardArray[freeRow][freeCol] = randNum
    for i := 0; i <= 8; i++ {
        if board.GenerateBoard() {
            return true
        }
    }
    board.BoardArray[freeRow][freeCol] = 0
}
return false

The loop is important because it controls how often board.GenerateBoard() is called recursively. Each time a recursive call is made the code attempts to add another pseudo random number into the next available slot and the more attempts that are made the more likely it is that a solution will be found.

回复 原文
~没有更多了~

关于作者

注定孤独终老

暂无简介

文章
评论
26 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

紫罗兰の梦幻

文章 0 评论 0

-2134

文章 0 评论 0

liuxuanli

文章 0 评论 0

意中人

文章 0 评论 0

○愚か者の日

文章 0 评论 0

xxhui

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文