Post

Matlab 练习

Posted Updated
By Jo Cruise 5 min read

该blog记录了我做“基于枚举搜索算法的数独问题求解”习题时对课程组给的代码的梳理

This blog is incomplete, and might be revoked soon.

使用到的变量

Order

数独游戏阶数，在init_data中初始化，在此次练习题目中赋值为6

cur_mark

三维数组，下标分别表示行坐标，列坐标，数项 ，在init_data中初始化，初始值为6x6x6内容全部为1的数组

diff_mark

四维数组。记录搜索过程中关键步骤的标注变化，在发生回退搜索操作时需要这些记录来恢复标注场景。第四维下标，对应记录发生时正在开始处理的格子编号。前三维下标分别对应行坐标、列坐标、数项

groups

三维数组，用于指定哪几格属于一宫。下标分别表示行坐标，列坐标，宫。在init_data中初始化，初始值为6x2x6内容全部为0的数组

例如在输入下列代码后

1
2

groups=zeros(Order,2,6); 
groups(:,:,1)=[1 1; 1 2; 1 3; 2 1; 2 2; 2 3];

groups中内容变为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

val(:,:,1) =

     1     1
     1     2
     1     3
     2     1
     2     2
     2     3


val(:,:,2) =

     1     4
     1     5
     1     6
     2     4
     2     5
     2     6


val(:,:,3) =

     3     1
     3     2
     3     3
     4     1
     4     2
     4     3


val(:,:,4) =

     3     4
     3     5
     3     6
     4     4
     4     5
     4     6


val(:,:,5) =

     5     1
     5     2
     5     3
     6     1
     6     2
     6     3


val(:,:,6) =

     5     4
     5     5
     5     6
     6     4
     6     5
     6     6

init_digit

题目最初已给的数字，下标分别表示行坐标，列坐标，格中数字。在本题中已给出：

4 1 2 3 5 3 4 5 5 1 4 6

则

1
2
3
4
5
6
7
8
9
10
11
12
13
14

init_digit=[
  1 1 4; 
  1 6 1; 
  2 3 2; 
  2 4 3; 
  3 2 5; 
  3 5 3;
  4 2 6; 
  4 5 4; 
  5 3 5; 
  5 4 4; 
  6 1 1; 
  6 6 5
];

cell

当前正在处理的格子的编号

cell_record_ptr

ptrs

一维数组。记录每格中指针所对位置。

cell_record

cell_record_ptr

xcell

ycell

goto_nextcell

next_mark

初值与cur_mark相同，是一个更新后的cur_mark

output

check_mark函数返回值，0代表某一格可填数字全为0，则此路不通，1代表可通

使用到的函数

check_mark

待检查的 mark 表格，当发现某一格子的所有数项的 mark 均为零，说明此路行不通，输出返回值零

返回output

mark指某一格中可填数字

refresh_mark

定义

当指定格子选定数项后，依据数独游戏规则对全图标注进行修改，并返回修改结果。

接受参数groups、cur_mark、x、y、ptr

返回next_mark

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

function next_mark = refresh_mark(groups,cur_mark,x,y,ptr)
% MARKING 输入参数含义:组的定义，cur_mark，行坐标，列坐标，数项 
% 当行、列坐标指定的格子内填写数项 ptr 后，对 mark 表格进行更新 
Order=size(cur_mark,1);
next_mark =cur_mark;

next_mark(x,y,:)=0; % 同一格各项 mark 清零
next_mark(x,:,ptr)=0; % 同一行同项 mark 清零
next_mark(:,y,ptr)=0; % 同一列同项 mark 清零

% 同一组的同项 mark 清零 
for g=1:size(groups,3)
    found=0;
    for i=1:Order
        if groups(i,:,g)==[x,y] 
            found=1;
        end 
    end
    if found==1
        for i=1:Order
            next_mark(groups(i,1,g),groups(i,2,g),ptr)=0; 
        end
    end 
end

next_mark(x,y,ptr)=1; 
end

使用到的.m文件

go

顶层程序

init_data

用于初始化变量，初始化的变量cur_mark，diff_mark，ptrs，groups，init_digit，cell_record，cell_record_ptr

oneround

一轮处理。按照既定算法步骤，对当前格进行处理， 根据处理情况决定前进一格还是回退一格。

Notes, Matlab
matlab incomplete
This post is licensed under CC BY 4.0 by the author.