(Luận văn) nghiên cứu phương pháp quay lui và ứng dụng giải bài toán sudoku

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.31 MB, 53 trang )

ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TIN
----------

PHẠM THỊ THANH HIỀN

a
lu
n
n

va
p
ie
gh

tn
to

NGHIÊN CỨU PHƯƠNG PHÁP QUAY LUI VÀ
ỨNG DỤNG GIẢI BÀI TỐN SUDOKU

d

oa
nl
w

do
a

nv

a
lu

KHĨA LUẬN TỐT NGHIỆP

ll

u
nf
m
tz
ha

n
oi
z
m

co

l.
ai

gm

@
an

Lu
n
va
ac

th
si

Mục lục
MỞ ĐẦU ......................................................................................................1
I. LÝ DO CHỌN ĐỀ TÀI:.....................................................................1
II. MỤC TIÊU, NHIỆM VỤ: .................................................................2
III. PHƯƠNG PHÁP NGHIÊN CỨU: ..................................................2
IV. BỐ CỤC CỦA ĐỀ TÀI: ...................................................................2
Chương I:

CƠ SỞ LÝ THUYẾT .................................3

I. CƠ SỞ LÝ THUYẾT: .........................................................................3

a
lu
n

1. Mảng:................................................................................................3

va
n

1.1. Mơ hình quan niệm: .................................................................3

p
ie
gh

tn
to

1.2. Các đặc trưng cơ bản: .............................................................3
1.3. Cấu trúc lưu trữ: ......................................................................3
1.4. Các phép toán cơ bản: .............................................................3

do

oa
nl
w

2. Hàm đệ quy:.....................................................................................4
2.1. Đệ quy là gì? .............................................................................4

d

a
lu

2.2. Cấu trúc chính của một chương trình đệ quy: ......................4

a

nv

2.3. Đặc điểm: ..................................................................................5

u
nf

2.4. Ví dụ: .........................................................................................5

ll

3. Khử đệ quy: .....................................................................................6

m

n
oi

3.1. Khái niệm:.................................................................................7

tz
ha

3.2. Cách thực hiện : .......................................................................7

z

II. NGƠN NGỮ LẬP TRÌNH: ...............................................................7

@

gm

1. Vài nét về Visual C#:.......................................................................7
PHƯƠNG PHÁP QUAY LUI .......................10

m

Chương II:

co

l.
ai

2. Đặc điểm của ngôn ngữ C#: ...........................................................8

an

Lu

I. KHÁI NIỆM QUAY LUI: ................................................................10

n
va
ac

th
si

* Tư tưởng của thuật tốn: ..............................................................11
II. MƠ HÌNH CỦA BÀI TOÁN: .........................................................11
III. ỨNG DỤNG: ...................................................................................12
1. Phương pháp : ...............................................................................12
2. Giải thuật tổng quát :....................................................................13
Chương III:

BÀI TOÁN SUDOKU .................................15

I. GIỚI THIỆU BÀI TOÁN: ................................................................15
1. Lịch sử ra đời: ...............................................................................15

a
lu

2. Luật chơi: .......................................................................................16

n

3. Các biến thể: ..................................................................................17

va
n

II. XÂY DỰNG CẤU TRÚC DỮ LIỆU CHO BÀI TOÁN:..............18

p
ie
gh

tn
to

III. THUẬT TOÁN: ..............................................................................23
1. Tổng quan: .....................................................................................23

do

1.1. Xác định bài tốn: ..................................................................23

oa
nl
w

1.1.1. Thơng tin vào:..................................................................23
1.1.2. Thơng tin ra: ....................................................................23

d

a
nv

a
lu

1.2. Cách xác định mỗi ô số bất kỳ: .............................................23
1.2.1. Xác định các ô theo số thứ tự từ 1 đến 81:....................23

u

nf

1.2.2. Xác định bằng [hàng, cột]: .............................................24

ll
m

1.2.3. Xác định bằng [vùng, số thứ tự trong vùng]: ...............24

n
oi

tz
ha

2. Vấn đề đặt ra: ................................................................................25
3. Giải quyết vấn đề: .........................................................................26

z

3.1. Vấn đề 1: .................................................................................26

@

l.
ai

gm

3.2. Vấn đề 2: .................................................................................30

co

4. Giải thuật chính: ...........................................................................31

m

5. Các phương thức sử dụng trong chương trình: .........................32

Lu

an

6. Xây dựng các hàm:........................................................................33

n
va
ac

th
si

6.1. Hàm kiểm tra cột: ..................................................................33
6.2. Hàm kiểm tra hàng: ...............................................................34
6.3. Hàm kiểm tra vùng: ...............................................................35
6.4. Hàm giải chương trình thủ cơng: .........................................36
6.5. Hàm giải chương trình bằng phương pháp quay lui:.........36
6.6. Hàm giải đến đáp án cần chọn: ............................................38
6.7. Hàm đếm số đáp án: ..............................................................38

IV. GIỚI THIỆU CHƯƠNG TRÌNH GIẢI: ......................................38

a
lu

1. Tổng quan: .....................................................................................38

n

2. Chức năng chính: ..........................................................................43

va
n

3. Bảng phím tắt: ...............................................................................44

p
ie
gh

tn
to

V. THỬ NGHIỆM: ...............................................................................45

KẾT LUẬN ................................................................................................48

d

oa

nl
w

do

TÀI LIỆU THAM KHẢO ........................................................................49

a
nv

a
lu
ll

u
nf
m
tz
ha

n
oi
z
m

co

l.
ai

gm

@
an

Lu
n
va
ac

th
si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI:
Ngày nay với sự phát triển không ngừng của khoa học kỹ thuật, đặc biệt trong
các ngành mũi nhọn như: Điện Tử - Tin Học - Viễn Thông .v.v. Nếu chúng ta
không thường xun cập nhật thơng tin thì chúng ta khơng bắt kịp đà phát triển của
thế giới. Đất nước ngày càng tiến bộ, khoa học kĩ thuật ngày càng phát triển địi hỏi
con người ngày nay phải có năng lực thật sự, phải có khả năng tư duy logic tốt...để
tiếp cận với cơng nghệ hiện đại một cách nhanh chóng nhất. Vấn đề đặt ra là làm

a
lu

sao để phát triển khả năng tư duy của con người, đôi khi chúng khơng nhận ra rằng

n
n

va

chính những trị chơi trí tuệ, trị chơi với những con số có thể giúp chúng ta rèn

Và SuDoKu là một trị chơi trí tuệ nổi tiếng, một trị chơi khơng ồn ào nhưng nó

p
ie
gh

tn
to

luyện trí não, tư duy logic.

vẫn âm thầm phát triển bởi nó khơng đơn thuần là một trị chơi mà nó giúp kích

oa
nl
w

do

thích tư duy, suy nghĩ logic của chúng ta thông qua những con số. Ngoài những vấn
đề trên, SuDoKu hấp dẫn giới trẻ bởi một lý do nữa là có thể chơi được mọi lúc mọi

d

nơi, có thể chơi trên xe buýt, trong giờ ra chơi, thậm chí khi đi dã ngoại, du lịch...

a
nv

a
lu

Luật chơi SuDoKu cực kỳ đơn giản, nhưng đáp án đơi khi lại cực kỳ khó giải, do
khơng cần dùng đến kiến thức số học hay tính tốn, SuDoKu thích ứng cho mọi

u
nf

người, trẻ em cũng có cơ hội giải được SuDoKu thành công như người lớn.

ll
m

Trong khi đó thuật tốn quay lui là một thuật tốn điển hình để giải lớp bài tốn

n
oi

tz
ha

liệt kê hay bài tốn tối ưu như: bài toán người giao hàng, bài toán con mã đi tuần,
bài tốn 8 hậu, bài tốn tìm đường đi trong mê cung...Bằng việc liệt kê các tình

z

huống, thử các khả năng có thể cho đến khi tìm thấy một lời giải đúng, thuật toán

@

m

co

l.
ai

theo chiều sâu của tập hợp các bài toán phần tử.

gm

quay lui chia nhỏ bài toán, lời giải của bài toán lớn sẽ là kết quả của việc tìm kiếm

an

Lu
n
va
ac

-1-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

Nhận thấy tư tưởng của thuật toán rất phù hợp với cách giải của trò chơi, nên đề
tài ”Nghiên cứu phương pháp quay lui và ứng dụng giải bài tốn SuDoku” được
thực hiện nhằm tìm hiểu về thuật tốn quay lui và ứng dụng của nó.
II. MỤC TIÊU, NHIỆM VỤ:
Đề tài này được thực hiện nhằm đạt được mục tiêu là hiểu rõ, hiểu sâu sắc hơn về
thuật tốn quay lui. Xây dựng thành cơng chương trình giải SuDoKu với nhiều đáp án
và với một thời gian nhanh nhất.
III. PHƯƠNG PHÁP NGHIÊN CỨU:

a
lu

- Tìm hiểu thơng tin trên mạng internet, sách, báo, tạp chí…

n
n

va

- Thu thập ý kiến chuyên gia (giáo viên hướng dẫn, các giáo viên trong và ngoài

- Kết hợp nghiên cứu lý thuyết với thực hành, rèn luyện kỹ năng phân tích chương

p
ie
gh

tn
to

khoa, ý kiến của bạn bè,…).

trình và kỹ năng lập trình.

do

oa
nl
w

IV. BỐ CỤC CỦA ĐỀ TÀI:
Nội dung của đề tài được trình bày như sau:

d
a
nv

a
lu

MỞ ĐẦU.

u
nf

Chương I: CƠ SỞ LÝ THUYẾT

ll

Chương II: PHƯƠNG PHÁP QUAY LUI.

m
n
oi

Chương III: BÀI TOÁN SUDOKU.

tz
ha

KẾT LUẬN.

z
m

co

l.
ai

gm

@

TÀI LIỆU THAM KHẢO.

an

Lu
n
va
ac

-2-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

CƠ SỞ LÝ THUYẾT

Chương I:
I. CƠ SỞ LÝ THUYẾT:
1. Mảng:
1.1. Mơ hình quan niệm:

Mảng là một dãy có thứ tự (về mặt vị trí) các phần tử với hai đặc điểm sau :

+ Số lượng phần tử cố định.
+ Mọi phần tử đều có cùng kiểu dữ liệu (dữ liệu cơ sở của mảng).

a
lu

1.2. Các đặc trưng cơ bản:

n
n

va

- Cho phép truy cập ngẫu nhiên đến từng phần tử. Thời gian truy cập đến mọi

- Số lượng phần tử của mảng là cố định.

p
ie
gh

tn
to

phần tử đều bằng nhau.

do

1.3. Cấu trúc lưu trữ:

oa
nl
w

- Cấu trúc lưu trữ đơn giản nhất là dùng địa chỉ được tính để thực hiện lưu trữ
và tìm kiếm các phần tử, là mảng một chiều hay vectơ.

d
a
lu

- Các phần tử được bố trí sát nhau trong bộ nhớ và theo thứ tự tăng dần của các

a
nv

chỉ số nên dễ dàng tìm được địa chỉ của một phần tử bất kỳ nếu biết chỉ số.
…..

…..

ai

m

a2

ll

u

nf

a1

an

tz
ha

n
oi
1.4. Các phép tốn cơ bản:

z

- Thường chỉ có các phép tạo lập (create) mảng, tìm kiếm (retrieve) một phần tử

@

gm

của mảng, cập nhật (update) một phần tử của mảng …Ngoài giá trị, một phần tử của

l.
ai

mảng còn được đặc trưng bởi chỉ số (index) thể hiện thứ tự của phần tử đó trong

m

co

mảng. Vectơ là mảng một chiều, mỗi phần tử ai của nó ứng với một chỉ số i. Ma trận

an

mở rộng ra mảng hai chiều , mảng ba chiều, …, mảng n chiều.

Lu

là mảng hai chiều, mỗi phần tử aij ứng với hai chỉ số i và j. Tương tự người ta cũng

n
va
ac

-3-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

2. Hàm đệ quy:
2.1. Đệ quy là gì?
Ta nói:

- Một đối tượng là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc nó
được định nghĩa dưới dạng của chính nó.

- Một thủ tục được gọi là đệ quy nếu trong quá trình thực hiện nó phải gọi đến
chính nó nhưng với kích thước nhỏ hơn của tham số.

- Trong thân của một hàm, nếu nó gọi tới chính hàm đó để xử lý bài tốn thì gọi
là hàm đệ quy.

a
lu

Ví dụ:

n
n

va

1) Định nghĩa số tự nhiên:

tn
to

- là một số tự nhiên.
- n là số tự nhiên nếu n-1 là số tự nhiên.

p
ie
gh

2) Định nghĩa hàm giai thừa:

oa
nl
w

do

- 0! = 1

- Nếu n > 0 thì n! = n(n-1)!

2.2. Cấu trúc chính của một chương trình đệ quy:

d

- Phần cơ sở :

a
nv

a
lu

Một chương trình đệ quy về căn bản gồm 2 phần:

ll

u

nf

Trong đó, chứa các tác động của hàm hoặc thủ tục với một số giá trị cụ thể

m

ban đầu của tham số (hay gọi trường hợp dừng).

tz
ha

- Phần đệ quy:

n
oi

Ví dụ : if n=1 then gt:=1;

z

Trong đó, tác động cần được thực hiện cho giá trị hiện thời của các tham

@

nhỏ hơn của tham số.

m

co

Ví dụ: if n>1 then gt:=n*gt(n-1);

l.
ai

gm

số được định nghĩa bằng các tác động đã được định nghĩa trước đấy với kích thước

an

Lu
n
va
ac

-4-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

2.3. Đặc điểm:
- Mỗi một lần hàm tự gọi đệ quy đến nó thì máy tính sẽ tự tạo ra một biến cục
bộ mới.

- Có bao nhiêu lần hàm gọi đệ quy thì sẽ có bấy nhiêu lần thoát ra khỏi hàm
(kiểu như lặp hàm).
- Khi thoát ra ngồi hàm đệ quy thì một loạt các biến cục bộ tạo ra do dùng đệ
quy lúc này mới được giải phóng, và chúng sẽ giải phóng trước các biến cục bộ
(sinh ra do đệ quy) tạo ra sau.
- Sử dụng đệ quy là một phương pháp làm cho chương trình ngắn gọn, dễ hiểu

a
lu

nhưng nó sẽ làm tốn bộ nhớ và thời gian.

n
n

va

2.4. Ví dụ:

Function giaithua(n:word):integer;

p
ie
gh

tn
to

Hàm tính giai thừa của n (tính n!):

begin

do

if n=0 then giaithua:=1

oa
nl
w

else giaithua:=giaithua(n-1)*n;

end;

d

a
lu

Ví dụ: Tính n! =3

a
nv

Ta có giá trị truyền vào hàm gt qua biến n.

ll

u
nf

Trong ví dụ này, qui trình thực hiện như sau:

m

- Khi có lệnh gọi hàm, chẳng hạn:

- Thì máy sẽ ghi nhớ là:

tz
ha

n
oi

n := gt(3);

z

- Kế tiếp máy lại ghi nhớ:

m
an

Lu

- Theo định nghĩa của hàm thì:

co

gt(2) := 2 * gt(1); và đi tính gt(1)

l.
ai

gm

@

gt(3) := 3 * gt(2); và đi tính gt(2)

n
va
ac

-5-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

gt(1) := 1;
- Máy sẽ quay ngược lại:
gt(2) := 2 * 1; cho kết quả là 2
- Tiếp tục:

- gt(3) := 3 * 2; cho kết quả là 6
- Như vậy kết quả cuối cùng trả về là 6. Ta có: 3! = 6.
Nhận xét

a
lu

 Ưu điểm:

n

- Điểm mạnh lớn nhất: chương trình, code trở nên ngắn gọn, dễ hiểu,

n

va

thuận lợi cho việc chỉnh sửa.

 Nhược điểm:

p
ie
gh

tn
to

- Dễ chuyển thành chương trình trên các ngơn ngữ lập trình.
- Nhược điểm lớn nhất là tốn bộ nhớ.

do

oa
nl
w

- Mất nhiều thời gian xử lý, làm giảm tốc độ chạy chương trình.
- Khơng áp dụng cho mọi ngơn ngữ lập trình.

d

a
lu

Đệ quy khơng những là một phương pháp lập trình quan trọng mà còn là một

a
nv

phương pháp suy nghĩ để giải quyết vấn đề một cách tổng quát dựa trên ý tưởng:

u
nf

+ Đơn giản hố cơng việc

ll

+ Phân vùng để xử lý.

m

n
oi

3. Khử đệ quy: Đệ quy là quả tim trong các nghiên cứu lý thuyết cũng như thực

tz
ha

hành tính tốn, đã thể hiện rất nhiều sức mạnh và có ưu điểm trong nhiều bài tốn.

z

Nhưng có đơi khi, sự hạn hẹp của bộ nhớ dành cho chương trình con khơng cho

@

gm

phép chúng ta làm điều đó.Vì vậy vấn đề khử đệ quy lại cần được quan tâm, xem

m

co

l.
ai

xét.

an

Lu
n
va
ac

-6-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

3.1. Khái niệm:
Là quá trình chuyển đổi một giải thuật đệ quy thành một giải thuật không đệ quy
bằng cách chúng ta sử dụng vòng lặp hoặc bộ nhớ Stack tự tạo.
3.2. Cách thực hiện :
- Sử dụng vòng lặp: Với ý tưởng là chúng ta lưu lại các giá trị của lần tính tốn
trước làm dữ liệu cho việc tính tốn của lần sau.
Ví dụ: Khử đệ quy trong bài toán giai thừa bằng cách sử dụng vòng lặp
int giaithua (int n)

a

lu
n

{

int k=1;

va
n

For (i=2; i<=n;i++) k=k*i;

tn
to

return(k);

p
ie
gh

}

do

oa
nl
w

- Sử dụng bộ nhớ Stack: Đặt tất cả các giá trị của các biến cục bộ và địa chỉ của

chỉ thị kế tiếp vào ngăn xếp (Stack), quy định các giá trị tham số cho thủ tục và

d

chuyển tới vị trí bắt đầu thủ tục, thực hiện lần lượt từng câu lệnh. Sau khi thủ tục

a
lu

a
nv

hồn tất thì nó phải lấy ra khỏi ngăn xếp địa chỉ trả về và các giá trị của các biến cục

u
nf

bộ, khôi phục các biến và chuyển tới địa chỉ trả về.

ll

II. NGÔN NGỮ LẬP TRÌNH:

m
tz
ha

n
oi

1. Vài nét về Visual C#:

C# là một ngơn ngữ lập trình hướng đối tượng được phát triển bởi Microsoft, là

z

phần đầu cho kế hoạch .NET của họ. Microsoft phát triển C# dựa trên C++ và Java.

@

gm

C# được thiết kể bởi Anders Hejlsberg kiến trúc sư phần mềm nổi tiếng với các sản

l.
ai

phẩm Turbo Pascal. Và ông là người đứng đầu nhóm thiết kế Borland Delphi, một

m

co

trong những thành cơng đầu tiên của việc xây dựng môi trường phát triển tích hợp

an

Lu

(IDE) cho lập trình Client/Server.

n
va
ac

-7-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

C# cũng là ngơn ngữ lập trình điều khiển sự kiện, các chương trình được tạo ra sẽ
sử dụng IDE (Integrated Developmen Environment). Với IDE, người lập trình có
thể tạo, chạy, kiểm tra và debug các chương trình C#. Bên cạnh đó, nền .NET cho
phép các thành phần của một phần mềm được viết từ các ngôn ngữ lập trình khác
nhau có thể tương tác được với nhau, thậm chí người phát triển ứng dụng có thể
đóng gói các phần mềm cũ để nó hoạt động với chương trình C# mới.
Giống như các ngơn ngữ lập trình khác, C# cũng hỗ trợ các kiểu dữ liệu cơ bản
như integer, float, boolean, string, array... và các câu lệnh điều khiển (if, while, for,
switch, do…while…). Tuy nhiên, như đã trình bày ở trên, C# cũng có những đặc

a
lu
n

điểm riêng của nó.

n

va

2. Đặc điểm của ngơn ngữ C#:

tn
to

C#, theo một hướng nào đó, là ngơn ngữ lập trình phản ánh trực tiếp nhất

p
ie
gh

đến .NET Framework mà tất cả các chương trình .NET chạy và nó phụ thuộc mạnh
mẽ vào Framework này.

do

oa
nl
w

- Khơng có khái niệm biến tồn cục (global variables) và hàm (functions).

Tất cả các hàm, phương thức trong một chương trình viết bằng ngơn ngữ C# đều

d

a
lu

được khai báo dưới dạng một lớp. Mọi kiểu biến, kể cả các kiểu giá trị đơn giản đều

a
nv

được xem như các đối tượng. Tuy nhiên, ta có thể dùng thuộc tính static đối với các

m

hàm.

ll

u
nf

hàm và biến trong một lớp được khai báo public thay vì sử dụng biến tồn cục và

n
oi

- C# yêu cầu rất chặt chẽ đối với kiểu Boolean (bool), các câu lệnh có điều

tz
ha

kiện như while và if đều địi hỏi biểu thức điều kiện phải có kiểu bool. Nếu trong

z

C++ ta có phát biểu if(a) statement, biểu thức trong điều kiện if có thể được chuyển

@

gm

thành giá trị kiểu bool, cho dù a có thể được khai báo kiểu int hay pointer, C# thì

l.
ai

khác, nó khơng có khái niệm “a nguyên là đúng hay sai”. Điều này buộc người lập

an

Lu

hữu ích trong việc giảm những lổi lập trình hay mắc phải.

m

co

trình phải sử dụng những biểu thức có kiểu trả về chính xác là bool. Đặc tính này rất

n
va
ac

-8-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

- C++ cho phép đa thừa kế (multiple interitances) và nếu được sử dụng đúng
cách, đây thực sự là điểm rất mạnh. Tuy nhiên, đa thừa kế rất khó quản lý và như
vậy cũng rất khó áp dụng. Đây là một trong những lý do C# chỉ phát triển thừa kế
đơn (single inheritance).
- Namespaces trong C#: Khái niệm Namespaces được hiểu một cách đơn
giản là tập các lớp có mối liên hệ lẫn nhau. Ví dụ như ta gom các lớp có liên quan
đến hoạt động của cơ sở dữ liệu lại và đặt cho chúng một không gian tên
(namespace) chung gọi là DataActivity. Vì C# khơng cho phép có hai lớp cùng tên
trong cùng một chương trình, việc dùng namespace sẽ giúp ta tránh được những

a
lu
n

đụng độ trong vấn đề đặt tên. Sẽ hồn tồn có thể xảy ra sự đụng độ trên nếu chúng

n

va

ta có nhiều lớp được khai báo trong cùng một chương trình, chẳng hạn lớp

tn
to

Connection trong DataActivity sẽ xung đột với lớp Connection trong

p
ie
gh

InternetActivity. Để tránh sự đụng độ này, C# quy định tên lớp phải bao gồm
namespace của lớp đó. Vì thế tên thích hợp của 2 lớp Connection trong trường hợp

oa
nl
w

do

trên là DataActivity. Connection và InternetActivity.Connection. Điểm nổi bật của
C# Namespace là không ánh xạ một cách vật lý như đối với Java. Các lớp với cùng

d

một namespace có thể ở nhiều thư mục khác nhau. Và namespace có thể bao gồm

a
nv

a
lu

các lớp, các sự kiện, các exception và thậm chí là các namespace khác.

ll

u
nf
m
tz
ha

n
oi
z
m

co

l.
ai

gm

@
an

Lu
n
va
ac

-9-

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

PHƯƠNG PHÁP QUAY LUI

Chương II:

I. KHÁI NIỆM QUAY LUI:
Kĩ thuật quay lui (backtracking) như tên gọi của nó, là một q trình phân tích đi
xuống và quay lui trở lại theo con đường đã đi qua. Bằng việc liệt kê các tình huống,
thử các khả năng có thể có cho đến khi tìm thấy một lời giải đúng, thuật toán quay
lui chia nhỏ bài toán, lời giải của bài tốn lớn sẽ là kết quả của việc tìm kiếm theo
chiều sâu của các bài toán phần tử. Trong suốt quá trình tìm kiếm nếu gặp phải một
hướng nào đó mà biết chắc khơng thể tìm thấy đáp án thì quay lại bước trước đó và

a
lu

tìm hướng khác kế tiếp hướng vừa tìm đó. Trong trường hợp khơng cịn một hướng

n

nào khác nữa thì thuật tốn kết thúc.

n

va
tn
to

Thuật tốn quay lui có thể được thể hiện theo sơ đồ cây tìm kiếm theo chiều sâu

như hình dưới:

p
ie
gh

Gốc

oa
nl
w

do
X1

Khả năng x 1

d
a
lu

Khả năng x 2 với
x 1 đã chọn

a
nv

X2

u
nf

Khả năng x 3 với
x 1 và x 2 đã chọn

ll
m

X3

tz
ha

n
oi
z

X4

Khả năng x 4 với
x 1 , x 2 và x 3 đã
chọn

gm

@

m

co

l.
ai

Một
đáp án

an

Lu
n
va

ac

- 10 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

Từ hình vẽ, dẽ dàng nhận thấy:
- Ở một bài tốn hiện tại (mỗi nốt), ta đi tìm lời giải cho bài tốn đó. Ứng với
lời giải, ta đi giải bài toán kế tiếp cho đến khi bài toán gốc trở nên đầy đủ.
- Lời giải của bài toán gốc thường là một lối đi từ gốc đến nốt cuối cùng
(khơng có nốt con).
* Tư tưởng của thuật toán:
- Nét đặc trưng của kĩ thuật quay lui là các bước hướng tới lời giải cuối cùng
của bài toán hồn tồn được làm thử.

a
lu
n

- Tại mỗi bước, nếu có một lựa chọn được chấp nhận thì ghi nhận lại lựa chọn

n

va

này và tiến hành các bước thử tiếp theo. Cịn ngược lại khơng có lựa chọn nào thích

tn
to

hợp thì làm lại bước trước, xóa bỏ sự ghi nhận và quay về chu trình thử các lựa

p
ie
gh

chọn cịn lại.
- Điểm quan trọng của thuật toán là phải ghi nhớ tại mỗi bước đi qua để tránh

do

trùng lặp khi quay lui. Các thông tin này cần được lưu trữ vào một ngăn xếp-Stack

oa
nl
w

(vào sau ra trước), nên thuật toán thể hiện ý thiết kế một cách đệ quy.

d

- Thuật toán quay lui thường được cài đặt theo lối đệ quy, mỗi lần gọi hàm đệ

a
lu

a
nv

quy, hàm đệ quy được truyền một tham số (trong các tham số) là chỉ số của bài tốn

u
nf

con, trong hàm sẽ cố gắng tìm lời giải cho bài tốn con đó, nếu tìm thấy thì gọi hàm

ll

đệ quy để giải bài toán con tiếp theo hoặc là đưa ra đáp án bài toán lớn nếu đã đầy

m

n
oi

đủ lời giải, nếu khơng tìm thấy thì chương trình sẽ trở về điểm gọi hàm đó. Mục

tz
ha

đích của việc sử dụng hàm đệ quy là để thuật toán được rỏ ràng, dễ viết, dễ hiểu hơn
và cũng để bảo tồn các biến, các trạng thái lúc giải bài tốn con.

z
@

II. MƠ HÌNH CỦA BÀI TỐN:

gm

l.
ai

Lời giải của bài tốn thường biểu diễn bằng một véc tơ gồm n thành phần

m

co

phải thỏa mãn các điều kiện nào đó. Để chỉ ra lời giải x, ta phải xây dựng dần các

an

Lu

thành phần lời giải x=(x1,x2,....xn)

n
va
ac

- 11 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

Tại mỗi bước i:
- Đã xây dựng xong các thành phần x=(x1,x2,....xn)
- Xây dựng thành phần xi bằng cách lần lượt thử tất cả các khả năng mà xi có
thể chọn:
+ Nếu một khả năng j nào đó phù hợp cho xi thì xác định xi theo khả năng j.
Thường phải có thêm thao tác ghi nhận trạng thái mới của bài toán để hỗ trợ cho
bước quay lui. Nếu i = n thì ta có được một lời giải, ngược lại thì tiến hành bước i+1
để xác định xi+1

.

a
lu

+ Nếu khơng có một khả năng nào chấp nhận được cho xi thì ta lùi lại bước

n
n

va

trước (bước i-1) để xác định lại thành phần xi-1

Sử dụng thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu

p
ie
gh

tn
to

III. ỨNG DỤNG:

hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng

do

cách thử tất cả các khả năng.

oa
nl
w

1. Phương pháp :

d

a
lu

Giả thiết cấu hình cần liệt kê có dạng (x1 x2 ... xn). Khi đó thuật tốn quay lui

a
nv

được thực hiện qua các bước sau :

u
nf

Bước 1: Xét tất cả các giá trị x1 có thể nhận, thử cho x1 nhận lần lượt các giá

ll

m

trị đó. Với mỗi giá trị thử cho x1 ta sẽ làm tiếp Bước 2.

n
oi

tz
ha

Bước 2: Xét tất cả các giá trị x2 có thể nhận, lại thử cho x2 nhận lần lượt các
giá trị đó. Với mỗi giá trị thử gán cho x2 lại xét tiếp các khả năng chọn x3 ... cứ

z

tiếp tục như vậy đến bước n.

gm

@

Bước n: Xét tất cả các giá trị xn có thể nhận, thử cho xn nhận lần lượt các giá

m

co

l.
ai

trị đó, thơng báo cấu hình tìm được (x1 x2 ... xn).

an

Lu
n
va
ac

- 12 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

2. Giải thuật tổng quát :
Thuật toán quay lui có thể được mơ tả bằng đoạn mã sau (thủ tục này thử cho xi
nhận lần lượt các giá trị mà nó có thể nhận) :
void Try (int i)
{
for <mọi giá trị v có thể gán cho x[i]>
{

a
lu

<Thử cho x[i] bằng giá trị v>

n
n

va

if <x[i] là phần tử cuối cùng trong cấu hình hoặc i=n>

tn
to

<Thơng báo cấu hình tìm được>

p

ie
gh

else
{

do
oa
nl
w

<Ghi nhận việc cho x[i] nhận giá trị v (nếu cần thiết)>
// gọi đệ quy chọn tiếp x[i+1]

Try(i+1);

d
a
lu

<Nếu cần thì bỏ ghi nhận việc thử x[i]=v để thử giá trị khác>

ll
m
tz
ha

n
oi

}

u
nf

}

a
nv

}

(Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1))

z

@

+ Đầu tiên, Try(int i) là hàm đệ quy quay lui trong đó i là biến chạy từ 1  n

l.
ai

gm

tương ứng với số thứ tự của x1, x2, x3, ….., xn theo phương pháp đệ quy

co

+ Tiếp theo vòng lặp for cho các giá trị của từng phần tử x1, x2, x3,….. Tất

m

nhiên, đối với mỗi bài toán riêng thì những giá trị này là khác nhau.

an

Lu
n
va
ac

- 13 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

+ Trạng thái cuối tức là điểm dừng của thuật toán này. Thực chất thuật toán
quay lui cũng là đệ quy nên việc xác định điểm dừng cực kỳ quan trọng và ln
ln phải có.
+ Tiếp theo là phần xuất ra, vì như đã thấy, khi if (phần tử cuối cùng trong cấu
hình) thì đã xuất ra màn hình và khơng chạy bất kỳ hàm đệ quy nào nữa. Tuy nhiên,
khi xuất ra nó lại xuất tới nhiều dãy số (tùy từng bài tập). Lý do, nếu để ý thì chúng
ta sẽ thấy phía trên có 1 vịng for, nó sẽ hoạt động giống như kiểu nhiều vịng lặp

for lồng nhau.

a
lu

for(i =1; i<=n; i++)

n
va

for(j=1; i
n

…..

tn
to
p
ie
gh

for(z=1; zxuat()

do

oa
nl
w

Với m vòng for lồng nhau như vậy sẽ xuất ra n^m lần.
Như vậy nếu khơng đặt điều kiện nào thì vòng for đầu tiên sẽ là m lần, tiếp

d

a
nv

a
lu

theo trong mỗi lần đó lại có m lần for khác
Tóm lại, trong thủ tục mô tả trên, điều quan trọng nhất là đưa ra được một danh

u
nf

sách các khả năng đề cử và xác định được giá trị của biểu thức logic [ chấp nhận

ll

m

x[i] ]. Dễ thấy rằng bài toán vô nghiệm khi ta đã duyệt hết mọi khả năng mà khơng

n
oi

có khả năng nào thoả mãn u cầu. Chú ý rằng là đến một lúc nào đó thuật tốn

tz
ha

phải lùi liên tiếp nhiều lần. Từ đó suy ra rằng, thơng thường bài tốn vơ nghiệm khi

z

khơng thể lùi được nữa.

m

co

l.
ai

gm

@
an

Lu
n
va
ac

- 14 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

Chương III:

BÀI TOÁN SUDOKU

I. GIỚI THIỆU BÀI TOÁN:
1. Lịch sử ra đời:
Trò chơi này được kiến trúc sư Howard Garns ở New York thiết kế và được giới
thiệu lần đầu tiên vào năm 1979 trên tạp chí Dell (Mỹ) với tên gọi là "Number
Place". Tháng 4/1984, Number Place lần đầu tiên được giới thiệu tại Nhật trên báo
Monthly Nikolist với tên gọi "Suuji wa dokusinh ni kagiru", dịch sang tiếng Anh có
nghĩa là "những con số phải độc nhất" hoặc "những con số tìm thấy chỉ một lần" và

a
lu

được "rút gọn" thành SuDoKu (su = number, doku = single).

n
n

va

Nhưng trò chơi này chỉ trở nên phổ biến khi người Anh nhập cuộc. Báo Times số

tn
to

ngày 12/11/2004 đã giới thiệu nó với tên gọi “SuDoKu” dựa trên kết quả phát triển

p
ie
gh

chương trình trị chơi trên máy vi tính của một quan tòa về hưu người New Zealand
sống ở Hongkong tên là Wayne Gould. Sau đó, SuDoKu lần lượt xuất hiện trên hầu

oa
nl
w

do

hết các tờ báo hàng đầu của Anh và được "đưa" đến Australia nhờ tập đồn báo chí
Telegarph.

d

Từ ngày 2/8/2005, chương trình Radio Times của đài BBC (Anh) có một chuyên

a
lu

đề hằng tuần về SuDoKu mang tên Super SuDoKu. SuDoKu đã xuất hiện trên tivi

a
nv

lần đầu tiên vào ngày 1/7/2005 trong chương trình SuDoKu Live trên kênh Sky One.

u
nf

ll

Đây là một cuộc thi gồm 9 đội (mỗi đội 8 người cùng với một nhân vật nổi tiếng)

m

n
oi

tranh tài với nhau, tạo nên bảng SuDoKu lớn nhất thế giới (rộng 84 m với 1905 giải

tz
ha

pháp đúng), câu đố được khắc trên một sườn đồi ở Chipping Sodbury nước Anh.
Hiện nay, SuDoKu đã có mặt trên các báo, tạp chí hàng đầu và trở thành trò chơi

z

gây sốt tại hơn 40 quốc gia và vùng lãnh thổ trên thế giới, trong đó có Việt Nam.

gm

@

SuDoKu xuất hiện tại Việt Nam sớm nhất là trên tạp chí Khám Phá (Trực thuộc

l.
ai

Sở Khoa học và Cơng nghệ Thành phố Hồ Chí Minh), sau đó đến Thanh Niên, Hoa

co

m

Học Trị, được xem như là một hình thức giải trí đầy trí tuệ của giới trẻ. Đặc biệt,

an

Lu
n
va
ac

- 15 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

mục Vua trò chơi trên báo Hoa Học Trị với "món chủ lực" là SuDoKu thu hút rất
đơng học sinh tham gia (theo kết quả công bố của báo).
2. Luật chơi: Quy luật của trò chơi tương đối đơn giãn.Cho một bàn hình vng
được chia thành một lưới 81 ô nhỏ gồm 9 hàng và 9 cột, 81 ô nhỏ đó lại được chia
thành 9 vùng, mỗi vùng có 9 ơ. Đề bài SuDoKu là một bàn hình vng như thế, trên
đó tại một số ơ người ta đã điền sẵn một số giá trị. Cách chơi như sau:
 Phải điền các số từ 1 đến 9 vào mỗi hàng dọc, ngang không được trùng lặp.
 Ở mỗi hàng dọc, mỗi hàng ngang và mỗi ô vuông 3*3 được phân cách rõ ràng

a
lu

( bằng gạch đen đậm) luôn phải đảm bảo có đủ các số từ 1 đến 9.

n
n

va

 Ở mỗi hàng dọc, mỗi hàng ngang và mỗi ô vuông 3*3 được phân cách rõ ràng

Ví dụ: Cho đề bài như sau, yêu cầu dùng các số từ 1 dến 9 để điền vào các ô

p

ie
gh

tn
to

(bằng gạch đen đậm) các số chỉ được sử dụng một lần và khơng lặp lại.

cịn lại.

d

oa
nl
w

do
a
nv

a
lu
ll

u
nf
m
tz
ha

n
oi
z
m

co

l.
ai

gm

@
an

Lu
n
va
ac

- 16 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

Đáp án sẽ là:

a
lu
n
n

va
tn
to

p
ie
gh

3. Các biến thể:
Ngồi khn dạng chuẩn có kích thước 9x9 ơ, chia làm 3x3 vùng, SuDoKu cịn

do

oa
nl
w

có rất nhiều biến thể khác. Một số biến thể phổ biến như:
- Kích thước 4x4 ơ chia làm 2x2 vùng

d
a

nv

a
lu

- Kích thước 6x6 ơ chia làm 2x3 vùng
- Kích thước 5x5 ơ chia vùng theo pentomino (được phát hành với tên goi

ll

u
nf

Logi-5)

m

n
oi

- Kích thước 7x7 ơ chia vùng theo heptomino

tz
ha

- Kích thước 8x8 ơ chia vùng theo qui tắc (4x2):(4x2). Đây là cách chia thành

z

4 vùng chính, mỗi vùng 16 ơ. Trong mỗi vùng chính lại chia thành 2 vùng 8x8 dựa

gm

@

vào màu nền của từng ô. Tuy theo cách bố trí các ơ khác màu này, sẽ phát sinh thêm

l.
ai

một biến thể con khác. Cách bố trí đơn giản nhất là các ơ khác màu nằm xen kẽ

m

co

nhau – trông rất giống bàn cờ quốc tế (Game Sudoku do người Việt Phạm Văn Hải
phát triển: Sudoku Plus 8x8)

an

Lu
n
va
ac

- 17 -

th

tn
to
d

oa
nl
w

do
a
nv

a
lu

Hàng

ll

u
nf
m
tz
ha

n
oi
z
l.

ai

gm

@
m

co

2. Dữ liệu sử dụng trong chương trình là dữ liệu kiểu mảng:

Lu

- int [,] row = new int[10, 10]; là mảng 2 chiều dùng để đánh dấu hàng có thể

an

điền một số nào đó hay khơng.

n
va
ac

- 18 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

Trong đó giá trị row[i,j] nhận 2 giá trị quy ước là 0 và 1.
 row[i,j]=0 tức là hàng i không thể điền thêm giá trị j vào bất cứ ơ nào nữa
vì giá trị j đã tồn tại trong hàng i.
Ví dụ: Giả sử đề bài có hàng thứ 2 được cho như sau:

Khi đó row[2,2]=0, row[2,8]=0
 row[i,j]=1 tức là hàng i có thể điền thêm giá trị j vào bất cứ ô nào chưa

a
lu

được điền của hàng i.

n
n

va

Ví dụ: Với ví dụ trên thì row[2,9]=1

tn
to

- int [,] column=new int[10,10]; là mảng 2 chiều dùng để đánh dấu cột có thể

p

ie
gh

điền một số nào đó hay khơng.
Trong đó column[i,j] nhận 2 giá trị là 0 và 1

do

oa
nl
w

 column[i,j]=0 cột i không thể điền giá trị j vào.
 column[i,j]=1 cột i có thể điền giá trị j vào.

d
a
nv

a
lu

Ví dụ: Đề bài có cột thứ 2 được cho như sau:

ll

u
nf

Khi đó column[2,2]=0

m

column[2,9]=1

n
oi

Chỉ những giá trị chưa được điền trong

tz
ha

cột mới có thể được điền vào. Những giá

z

trị đó sẽ có giá trị trả về là 1.

m

co

l.
ai

gm

@
an

Lu
n
va
ac

- 19 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

- int [,] area=new int[10,10]; tương tự như đối với mảng row[i,j] và column[i,j]
mảng area[i,j] cũng là mảng 2 chiều dùng để đánh dấu vùng có thể đánh một số
nào đó vào hay khơng area[i,j] cũng nhận 2 giá trị là 0 và 1. Nếu area[i,j]=0 thì
vùng i không thể điền giá trị j vào. Ngược lại nếu area[i,j]=1 thì vùng i có thể điền
giá trị j vào.
Ví dụ: Giả sử đề bài cho vùng thứ 2 có các giá trị sau:
Khi đó area[2,7]=0
area[2,1]=0

a
lu

Tức là vùng 2 chỉ được điền các giá trị chưa

n
va

có trong vùng đó và giá trị 1 là có thể điền

n

được

tn
to

- int [,] AREA=new int[10,10]; là mảng cố định, dùng để thiết lập giá trị mặc định

p
ie
gh

của chỉ số vùng.

oa
nl
w

do

Trong đó AREA[i,j] nhận các giá trị từ 1 đến 9.
i: chỉ số hàng

j: chỉ số cột

d

Giá trị trả về của AREA là chỉ số vùng.

a
nv

a
lu
ll

u
nf
m
tz
ha

n
oi
z
m

co

l.
ai

gm

@
an

Lu
n
va
ac

- 20 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

C.vT.Bg.Jy.Lj.Tai lieu. Luan vT.Bg.Jy.Lj. van. Luan an.vT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.LjvT.Bg.Jy.Lj. Do an.Tai lieu. Luan van. Luan an. Do an.Tai lieu. Luan van. Luan an. Do an

Ví dụ: AREA[4,5] sẽ trả về giá trị là 5. Tức là hàng 4 cột 5 là thuộc vùng 5.

a
lu
n
n

va
p
ie

gh

tn
to
do

oa
nl
w

- int[, ,] agree = new int[10, 10, 11]; là mảng 3 chiều dùng để đánh dấu trên
từng ô trống một có bao nhiêu giá trị có thể điền được và đó là những giá trị nào.

d

a
nv

a
lu

Trong đó, giá trị agree[i,j,k] nhận các giá trị từ 1 đến 9.
i, j: Ô hàng i, cột j nhận giá trị từ 1 đến 9.

u
nf

ll

k: Nhận giá trị từ 0 đến 9.

m

h khả năng điền.

tz
ha

n
oi

 Với k=0 và giá trị trả về của agree[i,j,0] là h: nghĩa là ô hàng i cột j có

z

 Với k:1 9 thì các giá trị agree[i,j,1], agree[i,j,2], agree[i,j,3]… agree[i,j,k]

@
m

co

l.
ai

gm

là các khả năng điền đó.

an

Lu
n
va
ac

- 21 -

th

@edu.gmail.com.vn.bkc19134.hmu.edu.vn

si

(Luận văn) nghiên cứu phương pháp quay lui và ứng dụng giải bài toán sudoku

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về