[立即注册] 登录
教程网 返回首页

dqxxx的个人空间 http://my.jcwcn.com/?1048617 [收藏] [复制] [分享] [RSS]

日志

ai求解之数独⑴@张志晨as3系列教程94

已有 143 次阅读2018-3-14 16:14 |个人分类:张志晨as3教程t系列|系统分类:WEB前端| 数独, 张志晨, as3, 教程, 交流

因最强大脑节目中的盲填数独,而使数独游戏升温。标准的数独,一题一解。

下面,我用as3写一个电脑求解的类,借助这个类,探索一下as3的相关技巧。

package {

public class ai {

//r[9][9],c[9][9],p[9][9],map_state[9][9],flag_write[9][9];

var r: Array = []; //二维数组,记录行row已用数字n,用n-1作第二维的下标,用r[0][5]=true表示第一行已经填写了数字6,在这里,行号和数字都被减去1了。

var c: Array = []; //二维数组,记录列column已用数字n,用n-1作第二维的下标,//同上,c[2][8]=true,表示第三列已经有数字9了。

var p: Array = []; //二维数组,记录宫palace已用数字n,用n-1作第二维的下标,//下图为九宫示意图在0号宫里,无论哪个格里填入了6,就记录为p[0][5]=true

/*如果在第一行第二列放下数字9,将有如下记录:

r[0][8]=true;

c[1][8]=true;

p[0][8]=true;*/


var map_state: Array = []; //二维,模拟网格,初始化时填入固定数字,也就是题目中的已知数,不可改。空格可改,因为要在其中填入数字。

var flag_write: Array = []; //二维,初始化时布尔值,之后不变。true=可写。与上面的数组相辅相承,互为呼应。描述格子初始化时的读写属性,题目中给定的数,只读,不可改。

const NO: Boolean = false; //辅助静态变量,不是必须的,只是为了方便识别意义

const YES: Boolean = true;

const EMPTY: int = 0; //空格的值,用0表示空格

public var methods: String=""; //存放解,对外输出,因解是唯一的,所以,设为字符串型。若是多解,可设为数组。


public function ai(map: String) {//map: String,题目样式,如:

                            //"916004072800620050500008930060000200000207000005000090097800003080076009450100687",


//初始化数组:

for (var i: int = 0; i < 9; i++) {

map_state[i] = [];//定义二维数组

flag_write[i] = [];//定义二维数组

r[i] = [];//行

c[i] = [];//列

p[i] = [];//宫

for (var j: int = 0; j < 9; j++) {

r[i][j] = this.NO; //在加载题目条件==地图数据之前,设默认值:没占用

c[i][j] = this.NO;

p[i][j] = this.NO;

}

}

//初始化格子状态:

for (i = 0; i < 9; i++) {

for (j = 0; j < 9; j++) {

var k: int = i * 9 + j; //二维下标对应的一维下标,因为地图是个字符串,相当于一维数组

var n: String = map.charAt(k); //从外部给定的参数==地图数据中,提取每一个格的数据,进行布局

if (n == "0") {//如果是0,是空格,需要玩家在此格中填数

map_state[i][j] = this.EMPTY; //记忆为空格

flag_write[i][j] = this.YES; //记忆为可写

//change_rule(i, j,this.NO); //默认没占用,故省略,就是上面初始化数组时,我随手给了默认值,就是初始值,

                                               //往上看,上面的这句话:r[i][j] = this.NO; //默认值:没占用

} else {

map_state[i][j] = Number(n); //把数字变成0-8,方便计算

flag_write[i][j] = this.NO; //此格为已知数,不可改写,只读

change_rule(i, j); //标记[i,j]位已占用,对应相应的行、列和宫

}

}

}

solve(0, 0); //从左上角开始求解

trace("解法总计:", methods.length);

}


//约束机制,默认已占用,已占用和可不可写,不是一回事,可不可写由flag_write决定,已占用不等于正确,可能在回溯时重新填入数字

function change_rule(y: int, x: int, write_over: Boolean = true) {

//标记[y,x]位是否被占用:

var n: int = map_state[y][x] - 1;//数字n对应下标n-1即n=n-1,【当前格子里填入的数字是谁(n=  map_state[y][x] 的值)】

var id: int = get_palace(y, x);//获取当前格子所在宫的id

                        //在填数字n成功时,下面三行记录为真;填入不成功时,再改记录为假。

                       //为假时,map_state[y][x]有一个值n,但因无用而被忽略,就像“快速格式化”了,可以用新的数值覆盖

r[y][n] = write_over;//y行有or没有n【实际是比n大1 的数】

c[x][n] = write_over;//x列有or没有n

p[id][n] = write_over;//p宫有or没有n

}

//当前格所在的宫的id颁规律:其实上边已经有图示了

//012

//345

//678


//获得当前格子所在的宫的id号的方法:是数学问题,每三行为一组,每三列为一组,所以要除以3,取整后再调整,不细述

function get_palace(y: int, x: int): int {

//<<是位运算,向左移动0位,就是不动,但奇妙的是可以快速取整,(y / 3) << 0相当于int(y / 3)

return ((y / 3) << 0) * 3 + (x / 3) << 0;

}

//获取下一个可用的数字,无则返回空值

function get_next(y: int, x: int, start: int): int {

for (var i: int = start; i <= 9; i++) { //从格子当前的数字开始,一直取到数字9

var id: int = get_palace(y, x);//当前格处于哪个宫,取得所在宫的id号

//如果此格所在的行、列、宫中都没有i这个数字的记录,此数暂时可填入格子里:

if (r[y][i - 1] == this.NO && c[x][i - 1] == this.NO && p[id][i - 1] == this.NO) {

//数组下标从0开始,为减少空间占用,把数字减少1来存贮,下标[i-1]对应数字i,三个数组的第二维[5]=true,表示6已填入

return i; //返回可用数字

}

}

return this.EMPTY; //否则,无可用数字

}


//输出一个解:

function show() {

var s: String = ""

for (var i: int = 0; i < 9; i++) {

//按行把数组转换为字符串,加回车符,以形成方阵,看上去直观清楚

s += map_state[i].join("") + "\n";

}

this.methods=s; 

trace(methods);

}


//核心算法:

function solve(y: int, x: int) {

if (x >8) { //超出当前行的列,则转到下一行首列

y++; //下一行

x = 0; //首列

if (y > 8) { //超出最后一行,就成功了

show(); //保存解到数组,向外部输出

return;

}

}

//如果当前格子不可写,且没探索到最后一行的末尾:

while (!flag_write[y][x] && y <= 8) { //那就从当前行探索下一个格子,就是下一列,

x++; //下一列

if (x == 9) { //超出一行,则转到下一行首列

y++; //下一行

x = 0;//首列

if (y > 8) { //超出最后一行,就成功了

show(); //保存解到数组,向外部输出

return;

}

}

}

//对当前格子求解,从map_state[y][x]自身数字从0起,递增1,所以,空格为0,必须为0,0加上1为1,从1起探试的

while ((map_state[y][x] = get_next(y, x, map_state[y][x] + 1)) != this.EMPTY) { trace(y, x,map_state[y][x])


//上面的赋值,必须写在条件中,条件要变才行!

//如果填入map_state[y][x]不符合条件,就试下一个数map_state[y][x] + 1)行不行,如果行,就

//已经给map_state[y][x]赋值了,就是比它多1的数:map_state[y][x] = map_state[y][x] + 1等价于 n++

//如果都不行,无可用数字,就是之前的数字填错了,要回头重填,此是地,map_state[y][x] = get_next(y, x, map_state[y][x] + 1)),就是map_state[y][x] = 0,很妙!!!自动恢复到空格状态

change_rule(y, x); //记录这个数字已经占用

solve(y, x + 1); //到下一列探试继续填数

if (methods.length) {

return; //只求一个解,加上这句

}

change_rule(y, x, this.NO);//探索失败,则改写格子没占用,再回溯,跃回上一步

}

}

}

}



一个简单的应用:新建一个Flash文件,在时间轴上写如下代码测试:

import flash.events.Event;

var map: String = "916004072800620050500008930060000200000207000005000090097800003080076009450100687";

var pc: ai = new ai(map);

this.addEventListener(Event.ENTER_FRAME, show)

function show(e) {

if (pc.methods) {

trace(pc.methods);

this.removeEventListener(Event.ENTER_FRAME, show)

}

}

毫秒之间,输出结果:

916354872

873629154

524718936

768935241

149287365

235461798

697842513

381576429

452193687



--------------------------------------------------------------

在核心算法的循环里,加上一句,可监视程度求解的探试过程:

while ((map_state[y][x] = get_next(y, x, map_state[y][x] + 1)) != this.EMPTY) {

trace(y, x,map_state[y][x])//就是这句.......第y行,第x列,填入了谁...........................

change_rule(y, x); 

solve(y, x + 1); 

if (methods.length) {

return; 

}

change_rule(y, x, this.NO);//探索失败,则改写格子没占用,再回溯,跃回上一步

}

监视过程如下:

y行,x列,数字n

0 3 3

0 4 5

0 6 8

1 1 3

1 2 4

.......

4 4 8

4 6 5

4 7 6

4 1 4

4 2 9

4 4 6

4 6 3

4 6 5

4 4 8

4 6 3

4 7 6

4 8 5

.......

8 2 2

8 4 9

8 5 3

//-------------------------------------------------------------------

请你试着求解最前面的图片中的题目,“独”:

500000300

090500400

004000700

051037289

302080604

008052137

035000900

609000823

080023006

请把你的求解,发在评论里。

//-----------------------------------------------------------

待续、

【因为工作岗位变动,已经四五年时间没来这里,非常想念大家,,,张志晨,,,】


发表评论 评论 (2 个评论)

回复 dqxxx 2018-3-14 16:35
ai求解之数独⑴@张志晨as3系列教程94
dqxxx
因最强大脑节目中的盲填数独,而使数独游戏升温。标准的数独,一题一解。 下面,我用as3写一个电脑求解的类,借助这个类,探索一下as3的相关技巧
回复 dqxxx 2018-3-17 17:09 (待审核)
审核未通过

facelist

您需要登录后才可以评论 登录 | [立即注册]

2345