为什么我必须使用 core.CreateIntVarFromTo 才能让这个数独解算器工作？

Question

我正在使用 Golang gofd 包，提供约束满足解决方案来解决数独问题。我创建以下内容

package main

import (
    "bitbucket.org/gofd/gofd/core"
    "bitbucket.org/gofd/gofd/propagator"
    "bitbucket.org/gofd/gofd/labeling"
    "encoding/json"
    "io/ioutil"
    "fmt"
)

var ROWS = []string{"A", "B", "C", "D", "E", "F", "G", "H", "I"}
var COLS = []int{1,2,3,4,5,6,7,8,9}


var SQUARE1 = []string{
    "A!", "A2", "A3",
    "B1", "B2", "B3",
    "C1", "C2", "C3"}

var SQUARE2 = []string{
    "A4", "A5", "A6",
    "B4", "B5", "B6",
    "C4", "C5", "C6"}

var SQUARE3 = []string{
    "A7", "A8", "A9",
    "B7", "B8", "B9",
    "C7", "C8", "C9"}

var SQUARE4 = []string{
    "D!", "D2", "D3",
    "E1", "E2", "E3",
    "F1", "F2", "F3"}

var SQUARE5 = []string{
    "D4", "D5", "D6",
    "E4", "E5", "E6",
    "F4", "F5", "F6"}

var SQUARE6 = []string{
    "D7", "D8", "D9",
    "E7", "E8", "E9",
    "F7", "F8", "F9"}

var SQUARE7 = []string{
    "G!", "G2", "G3",
    "H1", "H2", "H3",
    "I1", "I2", "I3"}

var SQUARE8 = []string{
    "G4", "G5", "G6",
    "H4", "H5", "H6",
    "I4", "I5", "I6"}

var SQUARE9 = []string{
    "G7", "G8", "G9",
    "H7", "H8", "H9",
    "I7", "I8", "I9"}

var SQUARES = [][]string{
    SQUARE1, SQUARE2, SQUARE3,
    SQUARE4, SQUARE5, SQUARE6,
    SQUARE7, SQUARE8, SQUARE9}

type Grid struct {
    Grid map[string]int
}

func create() Grid {
    grid := map[string]int{}
    return Grid{grid}
}

func (g *Grid) load(filename string) {
    body, _ := ioutil.ReadFile(filename)
    err := json.Unmarshal(body, g)
    if err != nil {
        fmt.Println(err)
    }
}


func main() {
    store := core.CreateStore()
    n := 9

    sudoku := map[string]core.VarId{}

    for _, row := range ROWS {
        for _, col := range COLS {
            varname := fmt.Sprintf("%s%d", row, col)
            sudoku[varname] = core.CreateIntVarFromTo(varname, store, 1, n)
        }
    }

    for _, square := range SQUARES {
        area := make([]core.VarId, len(square))
        for i, key := range square {
            area[i] = sudoku[key]
        }

        prop := propagator.CreateAlldifferent(area...)
        store.AddPropagators(prop)
    }

    for _, row := range ROWS {
        area := make([]core.VarId, len(COLS))
        for i, col := range COLS {
            varname := fmt.Sprintf("%s%d", row, col)
            area[i] = sudoku[varname]
        }
        prop := propagator.CreateAlldifferent(area...)
        store.AddPropagators(prop)
    }

    for _, col := range COLS {
        area := make([]core.VarId, len(COLS))
        for i, row := range ROWS {
            varname := fmt.Sprintf("%s%d", row, col)
            area[i] = sudoku[varname]
        }
        prop := propagator.CreateAlldifferent(area...)
        store.AddPropagators(prop)
    }

    grid := create()
    grid.load("test2.json")

    for k,v := range grid.Grid {
        prop := propagator.CreateXeqC(sudoku[k], v)
        store.AddPropagators(prop)
    }

    consistent := store.IsConsistent()
    fmt.Printf("consistent: %v \n", consistent)

    query := labeling.CreateSearchAllQuery()
    solutionFound := labeling.Labeling(store, query,labeling.SmallestDomainFirst, labeling.InDomainMin)
    fmt.Printf("solutionFound: %v \n", solutionFound)
    if solutionFound {
        resultSet := query.GetResultSet()
        for _, result := range resultSet {
            values := map[string]int{}

            for k,v := range result {
                id := store.GetName(k)
                values[string(id)] = v
            }

            for _, row := range ROWS {
                for _, col := range COLS {
                    key := fmt.Sprintf("%s%d", row, col)
                    fmt.Print(values[key], " ")
                }
                fmt.Println()
            }


        }
    }
}

您会注意到我正在从 JSON 文件 'test2.json' 加载。本文件内容如下

{"Grid": {
  "A1": 6, "A2": 3, "A3": 2, "A6": 7, "A7": 1,
  "B3": 7, "B4": 6, "B5": 2, "B7": 8, "B8": 9,
  "C2": 5,
  "D1": 5, "D3": 3, "D6": 9,
  "E2": 2, "E3": 6, "E5": 1, "E7": 9, "E8": 4,
  "F4": 5, "F7": 7, "F9": 2,
  "G8": 8,
  "H2": 6, "H3": 4, "H5": 8, "H6": 3, "H7": 5,
  "I3": 8, "I4": 1, "I7": 3, "I8": 6, "I9": 7}}

这个程序不起作用，接下来会出现。

consistent: false 
solutionFound: false

除非我加上下面的var

core.CreateIntVarFromTo("total", store, 50, 50)

在这种情况下我确实得到了答案。为什么我需要这样做？据我所知，其他约束应该就足够了。毕竟，您希望该行在 1 到 9 的范围内具有所有不同的值，列和单位（我在这里标记为正方形）也是如此。任何数独问题都应该只有一个答案，我不需要添加

core.CreateIntVarFromTo("total", store, 50, 50)

你给它什么值并不重要，因为你会得到这个变量允许的尽可能多的答案。所以如果我这样设置

core.CreateIntVarFromTo("total", store, 10, 11)

我会得到 2 个相同数字的结果。另一件让我困惑的事情是，如果我将 to 值设置为低于 10

core.CreateIntVarFromTo("total", store, 9, 9)

它不一致，没有找到解决方案，但是如果我将 to 值设置为 10 或更高，它会给出一个答案，从 from 开始，直到，在下面的情况下它会给出 3 个结果

core.CreateIntVarFromTo("total", store, 9, 12)

我在这里遗漏了什么事实？

Answer 1

首先，我必须承认我不是 Go 程序员，但我可能会更多地研究 Go 和 gofd 包（我不知道；感谢您的提示）。

我不知道为什么 "total" 使模型的行为如此，但为什么要用“！”命名一些单元格？而不是“1”，例如"A!"、"D!" 和 "G!"？

当我替换“！”使用“1”，显示正确且唯一的解决方案（没有 "total" 变量）：

consistent: true 
solutionFound: true 
6 3 2 8 9 7 1 5 4 
4 1 7 6 2 5 8 9 3 
8 5 9 4 3 1 2 7 6 
5 4 3 2 7 9 6 1 8 
7 2 6 3 1 8 9 4 5 
9 8 1 5 4 6 7 3 2 
3 7 5 9 6 2 4 8 1 
1 6 4 7 8 3 5 2 9 
2 9 8 1 5 4 3 6 7

我添加了以下内容来检查解的唯一性：

query2 := labeling.CreateSearchAllQuery()
solutionFound2 := labeling.Labeling(store, query2, labeling.SmallestDomainFirst, labeling.InDomainMin)
if solutionFound2 {
    println("The Sudoku problem has", len(query2.GetResultSet()), "solutions.")
}

为什么我必须使用 core.CreateIntVarFromTo 才能让这个数独解算器工作？

Why do I have to use core.CreateIntVarFromTo to get this Sudoku solver to work?

go

constraint-programming