Go语言实现的最简单数独解法

soduku.go

代码如下:

package main
import (
    "fmt"
)
type node []int
var sudokuMay [9][9]node
var Sudoku = [9][9]int{
    {0, 0, 0, 0, 0, 0, 8, 0, 0},
    {0, 8, 2, 4, 0, 0, 0, 0, 0},
    {1, 9, 0, 0, 6, 3, 0, 0, 0},
    {0, 5, 0, 0, 8, 0, 7, 0, 0},
    {6, 7, 8, 2, 0, 9, 1, 4, 3},
    {0, 0, 3, 0, 4, 0, 0, 8, 0},
    {0, 0, 0, 6, 2, 0, 0, 9, 4},
    {0, 0, 0, 0, 0, 5, 6, 1, 0},
    {0, 0, 0, 6, 0, 0, 0, 0, 0}}
func main() {
    n := inited(Sudoku)
    SudokuSure, _ := sure(sudokuMay)
    for n > 0 {
        n = Subinit(SudokuSure)
        // Output(sudokuMay)
        // fmt.Println(n)
        SudokuSure, _ = sure(sudokuMay)
    }
    Output(sudokuMay)
    fmt.Println(isEnable(sudokuMay))
    // test()
}
func isEnable(tn [9][9]node) bool {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if len(tn[i][j]) == 0 {
                return false
            }
        }
    }
    return true
}
func sure(may [9][9]node) (sure [9][9]int, n int) {
    n = 0
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if len(may[i][j]) == 1 {
                sure[i][j] = may[i][j][0]
                n++
            } else {
                sure[i][j] = 0
            }
        }
    }
    return
}
func test() {
    i, j := 1, 3
    fmt.Println(Sudoku[i][j])
    for k := ((i / 3) * 3); k < ((i/3)*3)+3; k++ {
        for l := ((j / 3) * 3); l < ((j/3)*3)+3; l++ {
            fmt.Print(Sudoku[k][l])
        }
        fmt.Println(" ")
    }
}
func inited(Sud [9][9]int) (changeCount int) {
    tmp := 0
    changeCount = 0
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if Sud[i][j] != 0 {
                sudokuMay[i][j] = append(sudokuMay[i][j], Sud[i][j])
            } else {
                for k := 0; k < 9; k++ {
                    sudokuMay[i][j] = append(sudokuMay[i][j], k+1)
                }
                sudokuMay[i][j], tmp = excludeMay(i, j, sudokuMay[i][j], Sud)
                changeCount += tmp
            }
        }
    }
    return
}
func Subinit(Sud [9][9]int) (changeCount int) {
    tmp := 0
    changeCount = 0
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if Sud[i][j] != 0 {
                sudokuMay[i][j][0] = Sud[i][j]
            } else {
                sudokuMay[i][j], tmp = excludeMay(i, j, sudokuMay[i][j], Sud)
                changeCount += tmp
            }
        }
    }
    return
}
func excludeMay(ti, tj int, t node, S [9][9]int) (rmay node, changeCount int) {
    changeCount = 0
    var tmpChangeCount int
    for i := 0; i < 9; i++ {
        if S[i][tj] != 0 {
            t, tmpChangeCount = exclude(t, S[i][tj])
            changeCount += tmpChangeCount
        }
        if S[ti][i] != 0 {
            t, tmpChangeCount = exclude(t, S[ti][i])
            changeCount += tmpChangeCount
        }
    }
    for k := ((ti / 3) * 3); k < ((ti/3)*3)+3; k++ {
        for l := ((tj / 3) * 3); l < ((tj/3)*3)+3; l++ {
            if S[k][l] != 0 {
                t, tmpChangeCount = exclude(t, S[k][l])
                changeCount += tmpChangeCount
            }
        }
    }
    rmay = t
    return
}
func excludeFirstOne(smay node, n int) (rmay node, changeCount int) {
    changeCount = 0
    rmay = smay
    for i := 0; i < len(smay); i++ {
        if smay[i] == n {
            changeCount++
            rmay = append(smay[:i], smay[i+1:]...)
            return
        }
        if i == len(smay)-1 {
            return
        }
    }
    return
}
func exclude(smay node, n int) (tmp node, changeCount int) {
    var nc int
    changeCount = 0
    tmp, nc = excludeFirstOne(smay, n)
    for nc > 0 {
        tmp, nc = excludeFirstOne(tmp, n)
        changeCount++
    }
    return
}
func Output(sudoku [9][9]node) {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            fmt.Print(sudokuMay[i][j])
        }
        fmt.Println("")
    }
}

以上就是本文给大家分享的代码的全部内容了,希望大家能够喜欢。

(0)

相关推荐

  • php 大数据量及海量数据处理算法总结

    下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题.下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论. 1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k个独立hash函数.将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明

  • php中最简单的字符串匹配算法

    本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)         

  • php数字转汉字代码(算法)

    复制代码 代码如下: //将数字转换为汉字,比如1210转换为一千二百一十 $num = "842105580";//九位数 function del0($num) //去掉数字段前面的0 { return "".intval($num); } function n2c($x) //单个数字变汉字 { $arr_n = array("零","一","二","三","四"

  • PHP实现的数独求解问题示例

    本文实例讲述了PHP实现的数独求解问题.分享给大家供大家参考,具体如下: 一.数独问题描述: 对于给出的数字二维数组,要求每行每列的数字不能重复. 二.实现代码: <?php /* 数独求解程序 * Created on 2017-4-18 * */ class Sudoku { var $matrix; function __construct($arr = null) { if ($arr == null) { $this->clear(); } else { $this->matr

  • PHP实现的方程求解示例分析

    本文实例讲述了PHP实现的方程求解.分享给大家供大家参考,具体如下: 一.需求 1. 给出一个平均值X,反过来求出来,得到这个平均值X的三个数X1 ,X2, X3,最大值与最小值的差值要小于0.4(X1-X3都是保留1位小数的数) 2. 这三个数X1, X2, X3代表了三组数.满足下面的公式: X1 = [(m1 - m2)/(m1 - m0) ] * 100 (@1); m0, m1, m2三个数的边界条件如下: 1)48<m0<51 2)0.45<m1 - m1<0.55 3

  • c++递归解数独方法示例

    复制代码 代码如下: #include<iostream> using namespace std; void init();void function(int m); int canplace(int row,int col,int c); void outputresult(); int a[9][9], maxm = 0; int main() {   init(); function(0);  return 0; } void init(){ int i, j; for(i = 0;

  • PHP经典算法集锦【经典收藏】

    本文实例总结了PHP经典算法.分享给大家供大家参考,具体如下: 1.首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半. 思路:多少行for一次,然后在里面空格和星号for一次. <?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo '<br/>'; } 2.冒泡排序,C里基础算法,从小到大对一组数

  • JavaScript遍历求解数独问题的主要思路小结

    数独规则 数独游戏,经典的为9×9=81个单元格组成的九宫格,同时也形成了3×3=9个小九宫格,要求在81个小单元格中填入数字1~9,并且数字在每行每列及每个小九宫格中都不能重复. 数独技巧 直观法 候选数法 相关二十格:一个数字只与其所在行列及小九宫格的二十格相关 我的思路 精心设计了有效性判定函数,最多一次遍历81个小单元格就能做出方案的有效性判定. 同理设计了相关20格判定,一次0~9的循环就完成有效性判定. 用数组模拟堆栈,为搜索提供回溯信息. 利用对象具有map性质,来辅助判断方案的有

  • 适用于抽奖程序、随机广告的PHP概率算法实例

    那么我们在程序里必然会设计到算法,即按照一定的概率让用户获得奖品.先来看两个概率算法函数. 算法一 复制代码 代码如下: /** * 全概率计算 * * @param array $p array('a'=>0.5,'b'=>0.2,'c'=>0.4) * @return string 返回上面数组的key */function random($ps){    static $arr = array();    $key = md5(serialize($ps)); if (!isset

  • Java实现解数独的小程序

    前言 数独相信很多人都玩过,趣味性很强,十分的耐玩.可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西. 算法如下,需要预先给出几个固定的值,目前解决的一个最难的数独是大概26个已知值的情况,理论上应该能解决任意已知值的数独,不过不知道会不会迭代栈溢出--因为在26个已知值的情况下就迭代了3000多次了,囧~~~ 结果显示如下: 这是已知值: 1 1 2 1 4 8 1 5 5 1 6 1 1 7 7 1 8 3 2 1 1 2 2 6 2 4 4 3 5 9 3 7

  • php编写的抽奖程序中奖概率算法

    们先完成后台PHP的流程,PHP的主要工作是负责配置奖项及对应的中奖概率,当前端页面点击翻动某个方块时会想后台PHP发送ajax请求,那么后台PHP根据配置的概率,通过概率算法给出中奖结果,同时将未中奖的奖项信息一并以JSON数据格式发送给前端页面. 先来看概率计算函数 function get_rand($proArr) { $result = ''; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 foreach ($proArr as

  • python实现数独算法实例

    本文实例讲述了python实现数独算法的方法.分享给大家供大家参考.具体如下: # -*- coding: utf-8 -*- ''' Created on 2012-10-5 @author: Administrator ''' from collections import defaultdict import itertools a = [ [ 0, 7, 0, 0, 0, 0, 0, 0, 0], #0 [ 5, 0, 3, 0, 0, 6, 0, 0, 0], #1 [ 0, 6, 2

  • JQuery开发的数独游戏代码

    用了很多Jquery的插件,支持鼠标滚轮选数字.没有什么高深的技术点.工作原因很长时间没有更新了,具体代码都有些记不清了,欢迎大家来拍砖.截图:演示地址:http://demo.jb51.net/js/jsukudo/index.html下载地址:jsukudo20081110v0.3.0.5.zip 下载列表:http://code.google.com/p/jsukudo/downloads/list 用到的JS文件 文件名 出处 说明 blockUI.js http://malsup.co

随机推荐