Lập trình game sudoku python

PHẦN 1 : SƠ LƯỢC VỀ LỊCH SỬ NGUỒN GỐC Ô SỐ SUDOKU
I. NGUỒN GỐC :
-

Sudoku có lịch sử từ hàng ngàn năm. Năm 990, một danh sách những “Ô số kỳ
ảo” đã xuất hiện và tỏ ra không khác mấy so với bản Sudoku xuất hiện trong Từ
Điển Bách Khoa Ikhwan al-salfa của các học giả người Ả Rập.

-

Abraham Ben ibn Ezra - một nhà triết học kiêm chiêm tinh học người Hispanic
(Tây Ban Nha - Bồ Đào Nha) gốc Do thái - bắt đầu quảng bá khối vuông buduh ở
châu Âu. Ông đi khắp Tây Ban Nha, Ý và các nước khác ở châu Âu để giới thiệu
với công chúng về “những ô số kỳ ảo”.
Ý tưởng tạo nên những ranh giới cho các khối vuông (biến nó thành trò chơi) đã
được Ahmed al-Buni ghi lại vào năm 1225, mặc dù phương pháp này được tin là
có xuất xứ từ Ba Tư.

-

II. SỰ PHÁT TRIỂN CỦA TRÒ CHƠI SUDOKU
-

Sudoku có thêm một bước tiến hóa mới vào năm 1776 khi một nhà toán học kiêm
vật lý học người Thuỵ Sĩ tên Leonhard Euler bắt đầu nghiên cứu và phát triển các
luật chơi mà ngày nay ta gọi là luật chơi Sudoku.

-

Sudoku lần đầu tiên được xuất bản vào cuối thập niên 1970 trong một tờ tạp chí ở
New York. Tờ tạp chí này đã giới thiệu về các ô số kỳ ảo và khuôn nó lại trong

một lưới 9x9, tạo thành từ các khối 3x3. Và như thế, Sudoku đã ra đời.
Năm 1986, trong một chuyến đi Mỹ, một nhà xuất bản Nhật Bản, Nikoli, đã khám
phá ra các ô số. Họ đặt tên cho nó là SuDoku (Su là số, Doku là đơn độc), và làm
cho nó nhanh chóng trở thành một trò chơi phổ biến ở Nhật Bản.

-

-

Năm 2004, niềm đam mê Sudoku đã đưa Wayne Gould đến với London (Anh).
Nhân một chuyến thăm ngẫu nhiên báo The Times, Gould đã thuyết phục tổng
biên tập của báo này cho đăng Sudoku bên cạnh các ô chữ. Độc giả lập tức bị
cuốn hút .Chỉ trong vài tuần lễ, các tờ báo trên khắp nước Anh đã thi nhau đăng
Sudoku. Từ đó, Sudoku bắt đầu lan rộng sang Mỹ, Canada, Úc, Pháp, Nam Phi và
nhiều quốc gia khác.

1

PHẦN 2 : HƯỚNG DẪN LUẬT CHƠI
Điền vào những ô trống những con số thích hợp theo quy luật đơn giản:
- Các ô ở mỗi hàng (ngang) phải có đủ các số từ 1 đến 9, không cần theo thứ tự.
- Các ô ở mỗi cột (dọc) phải có đủ các số từ 1 đến 9, không cần theo thứ tự.
- Mỗi miền 3x3, được viền đậm, phải có đủ các số từ 1 đến 9.

-

Trò chơi bắt đầu với một lưới Sudoku, trong đó một số ô đã cho sẵn các con số
đúng, phải suy luận để tìm ra những con số trong các ô trống còn lại.

-

Các đề sudoku mức dễ thường bắt đầu với nhiều con số đã được điền sẵn, do đó
sẽ dễ tìm ra đáp án hơn. Càng tìm ra nhiều con số, sẽ càng dễ tìm ra các con số
khác.
2

PHẦN 3 : PHÂN TÍCH THUẬT GIẢI GAME SUDOKU 2010
I.

HÌNH ẢNH PHẦN MỀM GAME

3

II.

HỖ TRỢ THỰC HIỆN :
1. Tài liệu tham khảo :
1.1 Đoạn code tham khảo :
- Đọan code lập trình chơi và giải ô số sudoku viết bằng ngôn ngữ
PASCAL chạy trên DOS
- Đọan code lập trình chơi và giải ô số sudoku viết bằng ngôn ngữ C#
trên Win
- Đoạn code lập trình giải game sudoku viết bằng ngôn ngữ C++ chạy trên
DOS.
1.2 Sách tham khảo ;
- Hướng dẫn viết chương trình bằng VISUAL C++.
- Lập trình windown bằng C++

- Phân tích thiết kế thuật giải.
- www.google.com.vn
2. Môi trường cài đặt :
- Viết bằng ngôn ngữ Visual C++ lập trình WIN với chương trình MFC.

III.

GIỚI THIỆU TỔNG QUÁT VỀ CÁC HÀM CỦA GAME

1. Phần hàm thực thi.
1. Hàm quét theo hàng ngang.
2. Hàm duyết theo hàng dọc.
3. Hàm duyệt theo khung ô chỉ định.
Chia 81 ô thành 9 ô gồm 3 ô ngang + 3 ô dọc.
4. Hàm tìm kiếm.
5. Hàm lưu các số có thể điền vào ô trống.
6. Hàm đếm số lượng các số có thể điền vào ô trống.
7. Hàm điền số.
8. Hàm kiểm tra.
9. Hàm xuất dữ liệu.
10. Hàm xử lý ( rất quan trọng).

-

2. Phần hàm nút diều khiển :
1.
2.
3.
4.
5.

6.

Hàm cho nút LEVEL
Hàm cho nút CHECK
Hàm cho nút ANSWER
Hàm cho nút HELP
Hàm cho nút INPUT
Hàm cho nút EXIT

4

IV.
Ý TƯỞNG GIẢI Ô CHỮ SUDOKU
Ta sẽ duyệt hết đường ngang từ trái sang phải, theo hàng dọc từ trên xuống, và
khung phạm vi 3 x 3, sau đó tìm ô trống thích hợp nhất và tìm số thích hợp điền vào.
Có hai trường hợp xảy ra đối với ô trống này .
- Trường hợp 1 : Chỉ có thể điền chính xác một con số duy nhất vào ô
đó, nhờ kết quả này xem thử ô trống thích hợp kế tiếp có thể rơi vào
trường hợp này hay không, nếu không thì ta có trường hợp hai.
- Trường hợp 2 : Ô trống đó có khả năng nhận nhiều giá trị khác nhau.
Ví dụ : Ô 8 có thể điền vào con số 3 hoặc con số 5.
o Ta lần lượt thay giá trị thứ 1 là con số 3 vào kiểm tra, tới ô trống kế tiếp
nhận con số đúng nhờ con số 3 này. Nếu đúng thì tiếp tục, nếu sai thì quay
lại ô trước đó là Ô 8 thay con số 3 bằng con số 5, lúc này số 5 là con số
chính xác của ô 8. Đây chính là thuật toán quay lui vét cạn.
- Cứ như thế cho các ô số còn lại.
V. GIẢI THÍCH QUI TRÌNH THỰC THI CỦA CÁC HÀM

Đây là phần khai báo ban đầu gồm các biến, và các mảng 2 chiều, 3 chiều .

1. Phần hàm thực thi.
1. Hàm duyệt theo hàng ngang

-

Chức năng : Kiểm tra duyệt theo hàng ngang từ trái sang phải với
vòng lặp biến i chạy từ 1 đến 9. Mảng A cố định x cho i chạy, nếu
A[x][i] có giá trị tức là có số thì trả về 0 ngược lại trả về 1.

5

2. Hàm duyệt theo hàng dọc

-

-

Chức năng : Kiểm tra quét ô theo hàng dọc từ trên xuống dưới với
vòng lặp biến i chạy từ 1 đến 9. Mảng A cố định y cho i chạy, nếu
A[i][y] có giá trị tức là có số thì trả về 0 ngược lại trả về 1.

3. Hàm duyệt theo khung ô chỉ định
Chia 81 ô thành 9 ô gồm 3 ô ngang + 3 ô dọc.
Hàm này sẽ quét theo thứ tự từ 1 đến 9 như theo hình vẽ.

6

4. Hàm tìm kiếm: có 2 nhiệm vụ

7

Chức năng :
- Nhiệm vụ 1 : Với hai vòng lặp for hàm FIND sẽ quét hết 81 ô bằng mảng hai
chiều A[k][h] = = 0 tức tìm ô chưa có số.
- Nhiệm vụ 2 : Xác định vị trí tọa độ chính xác của ô trống đó.
Minh họa : Giả sử xét tại ô 1 và ô thứ 17, các ô trống khác tương tự.

5. Hàm lưu các số có thể điền vào ô trống.

Minh họa:

6. Hàm đếm số lượng các số có thể điền vào ô trống.

8

7. Hàm diền số.

8. Hàm kiểm tra

9. Hàm xuất dữ liệu

9

10. Hàm xử lý ( rất quan trọng).

B[i][m][n]=A[m][n] : lưu tất cả 81 ô số ban đầu vào mảng ba chiều. Tại sao vậy ?
Bây giờ xem hàm PROCESS làm việc .

A[m][n]

B[i][m][n]

BAC
K
UP

10

-

Vẫn xử lý ô số của mảng A[m][n]
Gọi hàm FIND (i) => gọi hàm NUMS_CAN_FILL và hàm COUT_NUM(i)
Xử lý ô 4 = A[4][1]
A[m][n]

-

THỬ THAY SỐ 4 < => GỌI hàm AUTO_NUM ( lúc này vẫn đang xử lý số
chưa xuất ra màn hình)

-

Lúc gặp sự cố trên mảng 3 chiều B[i][m][n] sẽ gán ngược trở lại cho A[m][n]

Hàm AUTO_NUM thay số 4 thành số 8.
Cuối cùng là hàm CHECK() xem còn ô trống nào nữa không ? Còn thì gọi đệ
quy quay lại xử lý, cứ như thế. Nếu xử lý xong thì xuất ra màn hình kết quả.

11

2. Phần nút diều khiển :
1. Hàm cho nút LEVEL ( cung cấp dữ liệu ô số khác từng màn )

2. Hàm cho nút CHECK ( kiểm tra ô số có đúng với luật chơi hay không?

12

3. Hàm cho nút ANSWER ( Đáp án của trò chơi )

4. Hàm cho nút HELP ( Xem hướng sử dụng các nút như thế nào )

5. Hàm cho nút INPUT ( Đưa các ô số trả về trạng thái ban đầu)
13

6. Hàm cho nút EXIT ( Thoát khỏi trò chơi )

PHẦN 4 : HƯỚNG DẪN THỰC HIỆN LẬP TRÌNH SUDOKU 2010
I. KHỞI ĐỘNG VISUAL C++ :
- Click vào biểu tượng Visual C++
- Nhấn ENTER
Khi thực hiện xong , sẽ xuất hiện giao diện của Developer Studio như sau :

14

II. THỰC HIỆN TẠO GIAO DIỆN
- Vào Menu File, chọn New. Hộp thoại New hiện ra

-

Chọn Tab có tên Project nếu như chưa được chọn.
Click chọn MFC AppWizad(exe)
Nhập tên “ GAME SUDOKU” vào Project name ( tên này sẽ thấy ở phần
ID của Dialog)
Click nút OK. Hộp thoại MFC AppWizard Step1 hiện ra, chọn mục Dialog
based như hình sau :
Click nút Next liên tục chon đến khi chọn nút Finish, cuối cùng là OK

15

16

-

Bên cạnh sẽ xuất hiện hộp công cụ.
Trước khi thiết kế , xóa tất tất cả các nút điều khiển hiện có sẵn trong
Dialog( Click chọn điều khiển, nhấn nút Delete).

-

Click nút phải chuột tại bất kỳ trong Dialog.
Chọn Properties trong menu hiện ra. Hộp thoại hiện ra để xác lập các thông tin
cho Dialog. Chọn tab có tên General, click chọn nút Font…để chọn kiều chữ
…, size 16 hoặc 18 tùy theo mục đích thiết kế. Ở ô Caption, nhập “ GAME
SUDOKU”. Ở TAB Styles , click chọn Minimize box, maximize box để hiện
nút thu nhỏ và phóng to Dialog. Chọn Horizontal, Vertical scroll có thanh cuốn
ngang và thanh cuốn dọc.

17

18

III. VIẾT CODE CHO CÁC NÚT ĐIỀU KHIỂN
Trước hết xác lập tên biến, giá trị, kiểu biến cho các điều khiển cần thiết cho
chương trình. Các Edit Box thường phải xác lập vì chúng sẽ là các điều khiển thường
dùng để nhận hoặc thông báo các thông tin cần thiết cho người sử dụng biết.
Bảng xác định biến của các điều khiển.
Bí danh điều khiển
Tên biến
Loại
IDC_EDIT1
M1
Value
Tương tự cho EDIT còn lại ….
….
IDC_BUTTON1Answer
m-Answer

Control
Tương tự cho các IDC_BUTTON còn lại
-

-

-

Kiểu của biến
int
…
CString

Chọn ClassWizard ..từ menu hiện ra., sẽ thấy một hộp thoại có tên MFC
ClassWiZard, chọn Tab có tên Member Variables. Lúc này các thông tin về
bí danh ID của các điều khiển sẽ hiện ra trong List box, Click chọn
IDC_EDIT1.
Click vào nút có tên Add Variable trên hộp thoại.

Sau khi khai xong 83 EDIT BOX và 6 BUTTON cửa sổ MFC ClassWiZard

- Chọn tab Message Maps, trong List box chọn ID cần thực hiện, xem hình :

19

- Thực hiện cho các 6 nút BUTTON còn lại.
- Đoạn code đã trình bày bên trên.
Giải thích :
- Hàm UpdateData(TRUE) để đưa giá trị nhập trên các điều khiển vào các biến

tương ứng.
- Hàm UpdateData(FALSE) sẽ đưa giá trị từ biến vào trong các điều khiển, nhờ
hàm này, mới thấy được kết quả.
- Message box : hiện bản thông báo.
-

Cuối cùng nhán F7 để kiểm tra lỗi.
Ctrl +F5 : để chạy chương trình sẽ cho giao diện như sau.
Nhấn HELP để được hướng dẫn trước khi sử dụng phần mềm.

20