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

huangapple go评论94阅读模式
英文:

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

问题

我正在使用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()
			}
		}
	}
}

你会注意到我从一个名为test2.json的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

除非我添加以下变量:

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开始,直到to,例如在下面的情况下,它将给出3个结果

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

我在这里缺少了什么事实?

英文:

I'm using the Golang gofd package, to provide a constraints satisfaction solution to solve the Sudoku problem. I create the following

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

You'll notice I'm loading from a JSON file 'test2.json'. This files contents are as follows

{"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}}

This program doesn't work, coming up wi the following.

consistent: false 
solutionFound: false

Unless I add the following var

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

In which case I do get an answer. Why do I need to do this? As far as I can see the other constraints should be enough. You're after all wanting the row to have all different values within the domain of 1 to 9, same with columns, and units (which I label as squares here). There should be only one answer to any sudoku problem, and I shouldn't need to add

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

It doesn't matter what value you give it, as you'll get as many answers as the allowed by this var. So if I set it like this

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

I'll get 2 results, of the same numbers. Also another thing that puzzles me is if I set the to value to below 10

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

it fails to be consistent and no solution is found, but if I set the to value to 10 or above it comes up with an answer as many times starting from from, up to to, in the following case it will give 3 results

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

What fact am I missing here?

答案1

得分: 1

首先,我必须承认我不是Go程序员,但我可能会更深入地了解Go和gofd包(我之前不知道,谢谢你的提示)。

我不知道为什么“total”会导致模型的行为如此,但是为什么你将一些单元格命名为“!”而不是“1”,例如“A!”、“D!”和“G!”?

当我将“!”替换为“1”时,正确且唯一的解决方案(不使用“total”变量)显示如下:

一致性:true
找到解决方案: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("数独问题有", len(query2.GetResultSet()), "个解决方案。")
}
英文:

First, I have to confess that I'm not a Go programmer, but I might look more into Go and the gofd package (which I didn't know about; thanks for the tip).

I don't know why "total" make the model behaves as it does, but why are you naming some of the cells with an "!" instead of "1", e.g. "A!", "D!", and "G!"?

When I replace "!" with "1", the correct and unique solution (without the "total" variable) is shown:

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 

I added the following to check for the unicity of the solution:

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

huangapple
  • 本文由 发表于 2015年9月13日 20:48:42
  • 转载请务必保留本文链接:https://go.coder-hub.com/32549840.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定