Giải Sudoku bằng VBA

tuhocvba

Administrator
Thành viên BQT
Diễn đàn giới thiệu bài viết này không phải để chỉ ra đây là thuật toán hay, mà ở đây muốn các bạn tham khảo làm thế nào để tạo ra một chương trình VBA. Trên quan điểm đó, chúng tôi mong muốn diễn đạt để ngay cả người mới học cũng cảm thấy dễ hiểu nhất.
Bài toán đặt ra:
Chúng ta biết rằng Sudoku là trò chơi rất nổi tiếng, gồm một bảng ô vuông 9x9 ô. Trong đó lại chia thành các khối vuông nhỏ 3x3. Nhiệm vụ của người chơi là đặt các số từ 1 đến 9 vào các khối vuông nhỏ 3x3, mỗi số sử dụng một lần. Kết quả mong muốn là trong cả ô vuông lớn 9x9, trong cùng một hàng hay cùng một cột không có hai số nào trùng nhau.
Ta ví dụ đề bài như sau:
Bạn cần đăng nhập để thấy đính kèm

Kết quả mong muốn là:
Bạn cần đăng nhập để thấy đính kèm


Không thể nói rằng, ai cũng có thể học và sử dụng tốt VBA, nhưng thực tế là VBA rất thú vị. Diễn đàn muốn giới thiệu với các bạn rằng, VBA cũng có thể làm được những thứ thú vị như thế này.

Trước hết, giải bài toán này không phải là máy tính, mà trước hết là cách nghĩ của con người hình thành nên thuật toán rồi từ đó ra lệnh cho máy tính thực thi theo ý mình.

Khái quát cách giải:
Trong chủ đề này, diễn đàn sẽ giới thiệu ba cách giải.
Phương án giải số 1: Tìm số
Bạn cần đăng nhập để thấy đính kèm

Ta có ví dụ dưới đây:
Bạn cần đăng nhập để thấy đính kèm

Trong khu vực 3x3 ở góc trên bên trái ta thấy rằng ở góc trên cùng bên trái chỉ có thể điền vào đó là 5. Bởi vì ngoài số 5 ra thì trong hàng và trong cột và trong chính khu vưc 3x3 đó thì các số khác đều đã tồn tại.
 

tuhocvba

Administrator
Thành viên BQT
Phương án giải số 2: Tìm cells
Bạn cần đăng nhập để thấy đính kèm


Ta ví dụ ở khu vực ô vuông 3x3 được bao quanh bởi màu đỏ dưới đây, còn 4 ô còn trống, tương ứng là các số 2,5,7,8 phải điền vào.
A2,C2 cùng hàng và trong hàng đó đã tồn tại số 5.
B3: Nằm trong cột đã có số 5.
Như vậy 5 chỉ có thể điền vào A1.
Bạn cần đăng nhập để thấy đính kèm
 

tuhocvba

Administrator
Thành viên BQT
Phương án giải số 3: Tìm cells trong hàng và cột
Ở phương án giải số 2, ta tìm cách lấp đầy cells trong khối 3x3.
Ở phương án giải số 3 đòi hỏi phải rộng hơn, các ô cần lấp đầy không nằm chung trong một khối 3x3 nữa, mà là trong cùng hàng, hoặc cùng cột.
Bạn cần đăng nhập để thấy đính kèm

Lấy ví dụ: Ở hàng thứ 1 còn 4 vị trí trống, và ta cần đặt vào đó các số 1,4,6,7.
Ô D1, F1 ở trong cùng khối vuông nhỏ 3x3 và trong đó đã có số 1 do đó 1 không thể đặt vào D1, F1.
G1 cũng không thể đặt 1 vào đó. Vì trong cột chứa G1 đã có số 1.
Vì vậy 1 chỉ có thể đặt vào A1.

Cách nghĩ cũng tương tự với cột.
Bạn cần đăng nhập để thấy đính kèm


Trên đây tôi đã trình bày ba phương án giải. Các quản trị viên sẽ tiếp tục cập nhật bài viết trong chủ đề này.
Cho tới lúc chưa có thông báo rằng chúng tôi đã trình bày xong, đề nghị thành viên không post bài trong topic này.
(Dự kiến cần 3 tháng).
 

vbano1

SMod
Thành viên BQT
Xử lý tổng thể:
Cũng giống như xây một ngôi nhà, chúng ta cần tạo ra bộ khung cho chương trình.
Một cách tổng thể, chương trình sẽ xử lý những gì, đó là những gì chúng ta sẽ làm rõ ở bước này.
Bạn cần đăng nhập để thấy đính kèm


Thể hiện bằng mô hình:

-Xây dựng hình ảnh cho chương trình
-Ngôn ngữ thuyết minh vào hình ảnh
-Xây dựng code

Việc thể hiện bằng hình ảnh trong đầu ra ngôn ngữ cho người khác hiểu là việc cực kỳ quan trọng. Hãy chú ý điều này.

1. Chúng ta xây dựng ô vuông 9x9
Trên Excel, chúng ta xây dựng ô vuông 9x9 trong phạm vi từ ô A1 tới ô I9.
Bạn cần đăng nhập để thấy đính kèm


2. Từ A1~I9, chúng ta nhìn từ trái qua phải, từ trên xuống dưới xem cell nào rỗng, và suy nghĩ xem có thể điền số nào từ 1~9 vào cell rỗng đó.
Bạn cần đăng nhập để thấy đính kèm

3. Chúng ta lặp lại việc điền các số vào cell rỗng cho tới khi không còn cell rỗng nào nữa.
Sau một vòng kiểm tra và điền các số có thể điền được vào A1~I9, ta kiểm tra còn cell nào rỗng nữa hay không, nếu không còn thì kết thúc.
Nếu còn thì quá trình trên tiếp tục lặp lại.
Bạn cần đăng nhập để thấy đính kèm

Sau ba bốn lần chạy đi chạy lại như vậy, bài toán sẽ được giải quyết khi không còn cell rỗng nào nữa.
Bạn cần đăng nhập để thấy đính kèm

Nhưng cũng có những bài toán khó, chương trình không thể chạy vô tận, vì vậy lúc này chúng ta sẽ ra thông báo “Em xin đầu hàng”.
Bạn cần đăng nhập để thấy đính kèm
 

giaiphapvba

Administrator
Thành viên BQT
Như vậy từ đầu đến giờ ta đã làm rõ những gì chương trình sẽ làm, sau đây sẽ là flowchart.
Đây là bước tuy mất thời gian nhưng nếu xong thì code rất nhanh. Phần lớn mọi người bỏ qua flowchart và đi thẳng vào code, khi code sẽ có những rắc rối phiền toái phát sinh.
Bạn cần đăng nhập để thấy đính kèm


Point (điểm mấu chốt) ở đây là chúng ta có thể phán đoán đầu hàng không thể làm được.
Nếu số cell rỗng ở ① và ở ② bằng nhau, chúng ta đi tới phán đoán là không thể làm được.
Trong đó: cell rỗng ① có nghĩa là số cell rỗng trước khi Loop 2 bắt đầu.
cell rỗng ② là số cell rỗng sau khi Loop 2 kết thúc.

Về thiết kế Module, chúng ta sẽ sử dụng 4 Module theo như dưới đây:

Bạn cần đăng nhập để thấy đính kèm
 

Euler

Administrator
Thành viên BQT
Biến số:
Từ bây giờ sẽ có rất nhiều biến số xuất hiện. Trước hết ta hãy làm rõ những suy nghĩ trong đầu. Chúng ta sẽ định nghĩa các biến số càn thiết ngay từ bây giờ.
Hình ảnh:
Bạn cần đăng nhập để thấy đính kèm

Bạn cần đăng nhập để thấy đính kèm


Loop 1: Vòng lặp 1 sẽ tìm cách lấp đầy các cell trống trong ô vuông 9x9 cho tới khi nào không còn ô trống thì kết thúc.
Code xử lý tổng thể cho ô vuông 9x9
Mã:
Dim PuzzleArea As Range
Set PuzzleArea = Range("A1:I9")

Do
    '~Xử lý~
Loop Until WorksheetFunction.CountBlank(PuzzleArea) = 0
Ta định nghĩa PuzzleArea là ô vuông 9x9 trong phạm vi A1:I9.
Và ta sẽ sử dụng hàm của worksheet là CountBlank để đếm số cell rỗng. Quá trình xử lý lặp đi lặp lại cho tới khi số cell rỗng = 0.
Nếu = 0 thì kết thúc.
Nếu chưa = 0 thì quá trình xử lý được lặp lại.
Bạn cần đăng nhập để thấy đính kèm

Đếm số cell rỗng trong khu vực 9x9 ①
Mã:
Dim BlankCnt1 As Long 'Trước khi Loop 2 bắt đầu thì đếm số cell rỗng
BlankCnt1 = WorksheetFunction.CountBlank(PuzzleArea)
Nói một cách đơn giản, điều kiện vòng lặp này nếu là cho tới khi nào không còn ô trống thì vòng lặp sẽ là vô hạn.
Để phòng tránh điều này, ta sẽ tạo xử lý phán đoán để đầu hàng nếu gặp bài toán khó quá.
Trước khi vòng lặp Loop 2 bắt đầu ta sẽ đếm số cell rỗng và cất nó vào một biến số.
Vòng lặp Loop 2 : Xử lý tuần tự các cell rỗng trong ô 9x9
Mã:
For r = 1 To 9 'Dòng
    For c = 1 To 9 'Cột
        '~Xử lý giải mã các ô trống xem nên điền số gì~
    Next c
Next r
Vòng lặp trên sẽ đi tuần tự từ ô A1 đến ô I9 để kiểm tra xem cell nào trống và có thể điền vào đó số gì.
Đếm số cell rỗng ②
Mã:
Dim BlankCnt2 As Long 'Sau khi vòng lặp Loop 2 kết thúc, ta đếm số cell rỗng
BlankCnt2 = WorksheetFunction.CountBlank(PuzzleArea)
Sau khi vòng lặp Loop 2 kết thúc, ta lại đếm số cell trống và cất nó vào biến số.
Tiếp theo ta đi tới phán đoán xem có nên tiếp tục giải hay là đầu hàng.
Số cell rỗng ① và số cell rỗng ② có bằng nhau hay không?
Mã:
If BlankCnt1 = BlankCnt2 Then
    MsgBox "Em xin dau hang, bai toan nay kho qua"
    Exit Sub
End If
Trước khi vòng lặp Loop 2 bắt đầu, số cell rỗng là bao nhiêu? Và sau khi vòng lặp Loop 2 kết thúc, số cell rỗng là bao nhiêu? Nếu hai số cell rỗng này bằng nhau tức là công việc không có tiến triển gì, ta sẽ đi tới phán đoán là kết thúc, đầu hàng bài toán này.
Tóm lại, cho tới bây giờ, ta có code cho Module chung như sau:
Mã:
' ------------------------
' * Module chung
' ------------------------
Public r As Long, c As Long 'Vị trí dòng và cột hiện tại
Public num As Long 'Số từ 1~9

Sub main() 'Xử lý tổng thể

    Dim PuzzleArea As Range
    Set PuzzleArea = Range("A1:I9")
    
    Do 'Bắt đầu vòng lặp Loop 1
    
        Dim BlankCnt1 As Long 'Số cell rỗng trước vòng lặp Loop 2
        BlankCnt1 = WorksheetFunction.CountBlank(PuzzleArea)

        For r = 1 To 9 'Loop 2 bắt đầu
            For c = 1 To 9

            '--------------------------------------
            'Ta sử dụng các phương án giải 1~3 để tìm đáp án
            '--------------------------------------
            
            Next c
        Next r
        
        Dim BlankCnt2 As Long 'Số cell rỗng sau khi vòng lặp Loop 2 kết thúc
        BlankCnt2 = WorksheetFunction.CountBlank(PuzzleArea)
        
        If BlankCnt1 = BlankCnt2 Then
            MsgBox "Em xin dau hang, bai toan nay kho qua"
            Exit Sub
        End If
    
    Loop Until WorksheetFunction.CountBlank(PuzzleArea) = 0 '【Loop 1】
    
End Sub
 

tuhocvba

Administrator
Thành viên BQT
==========
PHẦN 2
==========
Ở các phần trước, chúng ta đã được các quản trị viên mô hình hóa chương trình theo cái nhìn tổng thể. Bây giờ tôi và các bạn sẽ đi vào cụ thể hơn.
Bạn cần đăng nhập để thấy đính kèm

Cụ thể là ở phần dùng chung này, chúng ta sẽ xây dựng các hàm dùng chung để có thể gọi và sử dụng nhiều lần.
Phần dùng chung 1:
Bạn cần đăng nhập để thấy đính kèm

Khối ô vuông 9x9 sẽ được ta chia ra làm các khối vuông nhỏ kích thước 3x3. Ta đặt tên chung cho chúng là BlockArea.
1. Phương pháp xác định khối BlockArea:
Với khối BlockArea ta sẽ định nghĩa cell bắt đầu, trong đó chú ý dòng của cell bắt đầu và cột của cell bắt đầu là hai tham số quan trọng.
Tên biến sốKiểuĐịnh nghĩa
r1LongDòng của cell bắt đầu trong khối 3x3
c1LongCột của cell bắt đầu trong khối 3x3
Ta sẽ có thêm hai biến số mới là r1 và c1 được định nghĩa theo như bảng trên.
Nào, bây giờ thì hãy nhìn xuống hình dưới đây để hình dung cell bắt đầu được định nghĩa như thế nào nhé.
Bạn cần đăng nhập để thấy đính kèm

Như vậy giả sử bạn đang đứng ở cells(5,5) thì chúng ta phải xác định được:
  • Cells bắt đầu là cells(4,4)
  • Cells kết thúc là cells(4+2,4+2) tức là cells(6,6)
  • BlockArea = Range(Cells(4, 4),Cells(4 + 2, 4 + 2))
Point: Chúng ta không cần thiết định điểm cuối, mà nó được tính trung gian thông qua điểm đầu.
Vì phạm vi của ta là ô 3x3 cho nên nếu biết điểm đầu thì sẽ biết được điểm cuối theo như công thức tôi đang minh họa cho các bạn thấy ở hình vẽ trên.
Như vậy với khối ô vuông 9x9 thì chúng ta có danh sách các điểm đầu được liệt kê dưới đây:
Bạn cần đăng nhập để thấy đính kèm

Dòng của cell hiện tại(r)Dòng của cell bắt đầu là(r1)
1,2,31
4,5,64
7,8,97
Trong danh sách trên tôi đã liệt kê các tình huống nếu cell hiện tại có dòng nằm trong một trong ba trường hợp nói trên thì lập tức ta sẽ xác định được dòng của cell bắt đầu của khối 3x3 chứa cell hiện tại.
Đến đây các bạn không có thắc mắc gì nữa chứ? Hoàn toàn tương tự, các bạn cũng có thể tự liệt kê các tình huống để thể hiện được cột của cell bắt đầu.
2. Các xử lý với khối BlockArea:
2.1 Tên Function: SearchBlockArea
2.2 Nội dung: Từ dòng và cột của cells hiện tại, hàm sẽ xác định cells bắt đầu của khối 3x3 chứa cell hiện tại.
2.3 Tham số đầu vào: x (Kiểu: Long)
2.4 Giá trị trả về :
Kiểu: Long
Bạn cần đăng nhập để thấy đính kèm


Mã:
Function SearchBlockArea(x As Long) As Long
'-------------------------------------------------------------------
' * Chức năng:Thông báo cell bắt đầu của khối BlockArea(3×3)
' * Tham số đầu vào:Dòng r hoặc cột c của PuzzleArea
' * Giá trị trả về:Dòng r1 hoặc cột c1 của khối BlockArea
'-------------------------------------------------------------------

    Select Case x
        
        Case 1, 4, 7
            SearchBlockArea = x
        Case 2, 5, 8
            SearchBlockArea = x - 1
        Case 3, 6, 9
            SearchBlockArea = x - 2

    End Select

End Function
 

Euler

Administrator
Thành viên BQT
3. Nơi gọi SearchBlockArea
Từ cái nhìn tổng thể, vậy thì ở đâu mà ta gọi hàm SearchBlockArea này nhỉ?
Trong xử lý tổng thể, chúng ta đi từ ô A1 tới ô I9, ở cell bất kỳ có dòng r và cột c, nếu ta gọi hàm này, ta sẽ nhận về:
  • Tôi trao cho anh tham số r (dòng hiện tại của tôi), anh trả cho tôi r1(dòng của cell bắt đầu)
  • Tôi trao cho anh tham số c (cột hiện tại của tôi), anh trả cho tôi c1 (cột của cell bắt đầu)
Bạn cần đăng nhập để thấy đính kèm

Code trong phần [Xử lý tổng thể] trong hình vẽ minh họa trên sẽ là:
Mã:
For r = 1 To 9 'Bắt đầu Loop 2
    For c = 1 To 9

        r1 = SearchBlockArea(r)
        c1 = SearchBlockArea(c)

        '-------------------------------
        'Ở đây là xử lý các phương án giải số 1~3
        '-------------------------------
            
    Next c
Next r
Bạn cần đăng nhập để thấy đính kèm

Sau khi đã tìm được khối BlockArea rồi, ta sẽ lần lượt gọi các thủ tục phương án giải số 1~3 để giải quyết.
 

giaiphapvba

Administrator
Thành viên BQT
Như vậy chúng ta đã xong Phần dùng chung 1 rồi, bây giờ ở cells bất kỳ bạn có thể xác định được mình đang đứng ở khối BlockArear (3x3) nào.
Bây giờ tôi giới thiệu Phần dùng chung 2 nhé.
Phần dùng chung 2: Xử lý tìm số.
Từ phạm vi mà bạn muốn tìm kiếm xem số num đã tồn tại trong đó hay chưa, hàm này sẽ trả về kết quả /Không.
Chú ý: num là biến public, là các số 1~9.
[Khái quát]
Tên Function: isExistNum
Nội dung xủ lý:
Trả kết quả tìm kiếm Có/Không khi kiểm tra xem num có tồn tại trong phạm vi Range được chỉ định.
Tham số đầu vào :
Kiểu :Long
y1, x1, y2, x2
Giá trị trả về là Boolean.
Nếu tồn tại, giá trị trả về là:True
Nếu không tồn tại, giá trị trả về là:False
Bốn tham số đầu vào để xác định phạm vi tìm kiếm:
Range(Cells(y1, x1), Cells(y2, x2))
Bạn cần đăng nhập để thấy đính kèm


Mã:
Function isExistNum _
    (ByVal y1 As Long, x1 As Long, y2 As Long, x2 As Long) As Boolean
' --------------------------------------------------------------------------
' * Chức năng:Tìm kiếm num trong vùng chỉ định xem tồn tại hay không
' * Tham số:Cells bắt đầu (dòng và cột) và cells kết thúc (dòng và cột)
' * Giá trị trả về:Nếu tìm thấy num thì trả về giá trị là True
' --------------------------------------------------------------------------

    Dim result As Range
    Set result = Range(Cells(y1, x1), Cells(y2, x2)). _
                            Find(what:=num, LookAt:=xlWhole)
    
    'Nếu tìm thấy num thì giá trị trả về là True
    If Not result Is Nothing Then isExistNum = True

End Function
 

tuhocvba

Administrator
Thành viên BQT
Phần dùng chung 3: Tìm ra đáp án thì điền và tô đậm, để màu đỏ.
Tên thủ tục :AnswerSet
Nội dung: Điền đáp án vào ô và tô đậm, để màu đỏ.
Tham số đầu vào: y,x
Giá trị trả về: không có
Bạn cần đăng nhập để thấy đính kèm


Mã:
Sub AnswerSet(ByVal y As Long, x As Long, answer As Long)
' ------------------------------------------------------------------
' * Chức năng:Điền đáp án vào cells được chỉ định
' * Tham số đầu vào:Dòng và cột của cells cần điền, giá trị điền vào là gì
' ------------------------------------------------------------------

    With Cells(y, x)
        .Value = answer
        .Font.Bold = True 'Tô đậm chữ
        .Font.ColorIndex = 3 'Để chữ màu đỏ
    End With
    
End Sub
Kết quả được thể hiện trong thực tế có dạng như thế này:
Bạn cần đăng nhập để thấy đính kèm

Như vậy phần dùng chung trong Module tổng thể (Module chung) đã được diễn đàn giới thiệu xong.
Phần tiếp theo, diễn đàn sẽ lần lượt giới thiệu cụ thể các phương án giải. Các bạn đón chờ nhé.
 

tuhocvba

Administrator
Thành viên BQT
==========
PHẦN 3: Các phương án giải
==========
Bạn cần đăng nhập để thấy đính kèm


Ta đã xong code phần tổng thể và xử lý chung, bây giờ ta sẽ bàn về phương án giải số 1.
Phương án giải số 1 sẽ viết code trên một module riêng.
Ta nhắc lại các biến số đã thảo luận cho đến nay:
Biến sốKiểuĐịnh nghĩa
PuzzleAreaRangeÔ vuông lớn 9x9
BlockAreaRangeÔ vuông nhỏ 3x3
rLongDòng trong ô vuông 9x9
cLongCột trong ô vuông 9x9
r1LongDòng của ô bắt đầu trong khối BlockArea
c1LongCột của ô bắt đầu trong khối BlockArea
numLongSố nguyên từ 1 đến 9
Phương án giải số 1: Tìm số
Ví dụ: Ta cần xác định xem số nào sẽ được điền vào ô A1.
Bạn cần đăng nhập để thấy đính kèm

Trước khi viết code, ta cần làm rõ những việc phải làm, đây là điều cực kỳ quan trọng.
Dưới đây là trình tự xử lý:
Từ phần xử lý tổng thể trong Module chung, ta gọi moldule phương án giải số 1.
Đầu tiên, cần quyết định thời điểm nào gọi phương án giải số 1.
Phương án giải số 1 là cách giải mà chúng ta đi tới từng cells trống trong ô vuông lớn 9x9 và tìm xem số nào sẽ được điền vào ô trống đó.
Như vậy, khi phát hiện ra cells trống, thì ta sẽ gọi phương án giải số 1 ra giải quyết.
Tìm số
Từ 1 đến 9, ta xem trong vùng được chỉ định đã tồn tại hay chưa, nếu chưa tồn tại thì số đó là ứng cử viên để điền vào ô trống đó.
Gồm có:
Trong ô 3x3 chứa ô trống đó đã tồn tại số nào rồi (1)
Trong hàng chứa ô trống đó đã tồn tại số nào rồi (2)
Trong cột chứa ô trống đó đã tồn tại số nào rồi (3)

Nếu như từ 1 đến 9, chỉ có số 1 là chưa tồn tại, thì ta có thể đưa ra đáp án, số 1 là số cần điền vào ô trống đó.
Ở đây, point (điểm mấu chốt) của phương án giải 1 là đưa ra những số là ứng cử viên để điền vào ô trống bằng cách xét tồn tại như đã nói ở trên. Nếu là con người, chúng ta không thể nào nhớ được số nào đã tồn tại hay chưa, chúng ta phải ghi chú ra giấy. Đương nhiên, chương trình cũng phải ghi chú kết quả xét duyệt tồn tại/ không tồn tại giống như cách con người làm.
Các số từ 1 đến 9 sẽ được gắn các lá cờ.
Bạn cần đăng nhập để thấy đính kèm

Biến sốKiểuĐịnh nghĩa
CheckFlag(9)BooleanBảo lưu kết quả số num đã có hay chưa?
CheckFlag(9) là mảng gồm 9 phần tử, chỉ số bắt đầu từ 1.
Bạn cần đăng nhập để thấy đính kèm

Ví dụ:
Bạn cần đăng nhập để thấy đính kèm


Giá trị khởi tạo ban đầu cho các cờ, trước khi việc tìm kiếm diễn ra sẽ là False.
Bạn cần đăng nhập để thấy đính kèm

Ta thực hiện tìm kiếm trong phạm vi liên quan tới ô trống theo ba phương án (1),(2),(3).
Giả sử tìm theo phương ngang (dòng), chúng ta phát hiện ra một số nào đó đã tồn tại, ta cho cờ của số đó là True.
Bạn cần đăng nhập để thấy đính kèm

Giả sử như kết quả tìm kiếm là: 1,2,3,4,6,7,8,9 đã tồn tại, chỉ có số 5 là chưa có. Vậy thì khi đó trạng thái cờ sẽ là:
Bạn cần đăng nhập để thấy đính kèm

Phán đoán đáp án
Phần này diễn đàn sẽ trình bày ở bài viết sau. Các bạn đón chờ nhé.
 

giaiphapvba

Administrator
Thành viên BQT
Phán đoán đáp án
Từ các cờ CheckFlag1~9 ta sẽ phán đoán đáp án là gì.
Ở đây ta cần hai biến số mới.
Biến sốKiểuĐịnh nghĩa
cntLongĐếm số lượng cờ CheckFlag(num) có giá trị False
answerLongCất các ứng cử viên đáp án vào biến này
Nếu có cờ là False mà không bị chuyển thành True khi đó ta tiến hành hai bước xử lý như sau:
Xử lý 1: Biến cnt tăng lên 1 đơn vị.
Xử lý 2: Cất ứng cử viên đáp án này để xét duyệt sau cùng.
Bạn cần đăng nhập để thấy đính kèm


Từ cờ của số 1, ta sẽ đi tuần tự đến số 9.
Bạn cần đăng nhập để thấy đính kèm


...Kiểm tra 2 đến 4...
Bạn cần đăng nhập để thấy đính kèm


Nếu tìm thấy cờ False thì tăng cnt và cất số của cờ ấy vào hộp chứa ứng cử viên đáp án.
Bạn cần đăng nhập để thấy đính kèm


...Kiểm tra tiếp các số từ 6 đến 9...

Cuối cùng xảy ra các trường hợp sau:
-Nếu cnt = 1, ta có thể quyết định đáp án là gì. Ghi đáp án vào ô trống và kết thúc.
-Nếu cnt>1 thì chưa xác định được đáp án.
Bạn cần đăng nhập để thấy đính kèm

Đến đây diễn đàn đã trình bày xong phương án giải số 1. Bài viết tiếp theo chúng ta sẽ xây dựng flowchart và code cụ thể nhé.
 

tuhocvba

Administrator
Thành viên BQT
Giải thuật cho phương án giải số 1:
flowchart:
Bạn cần đăng nhập để thấy đính kèm
 

vbano1

SMod
Thành viên BQT
Xây dựng chương trình:
Bây giờ chúng ta sẽ xây dựng cụ thể dựa vào bản thiết kế flowchart ở trên.
Gọi chương trình:
Mã:
If Cells(r, c).Value = "" Then Call Solution1
Ở phương án giải số 1, tên thủ tục là Solution1.
Trong ô vuông lớn 9x9 ta đang đứng ở ô có tọa độ là Cells(r,c), trường hợp cells đó là rỗng, ta sẽ tiến hành gọi phương án giải 1 ra để điền đáp án.
Bạn cần đăng nhập để thấy đính kèm


Các xử lý của phương án giải 1:
Chuẩn bị cờ cho các số từ 1 đến 9:
Mã:
Dim CheckFlag(9) As Boolean
Thông thường chỉ số index của mảng bắt đầu từ 0, nhưng chúng ta sẽ chỉ định bắt đầu từ 1.
Loop 1: Xét các số num=1~9
Mã:
For num = 1 To 9
    '~xử lý~
Next num
Trong các phạm vi chứa cells chỉ định, các phương án tìm kiếm 1~3 xác nhận xem số num đã tồn tại hay chưa?
Mã:
Dim check1 As Boolean, check2 As Boolean, check3 As Boolean

check1 = isExistNum(r1, c1, r1 + 2, c1 + 2) '① Tìm kiếm trong BlockArea
check2 = isExistNum(r, 1, r, 9) '② Tìm kiếm trong hàng
check3 = isExistNum(1, c, 9, c) '③ Tìm kiếm trong cột
Ở đây ta sử dụng hàm dùng chung isExistNum, và truyền tham số đầu vào cho nó để tiến hành kiểm tra.
isExistNum( Hàng chứa cells bắt đầu, Cột chứa cells bắt đầu, Hàng chứa cells kết thúc, Cột chứa cells kết thúc)
Ví dụ 1: Tìm kiếm trong khối BlockArea 3x3
Bạn cần đăng nhập để thấy đính kèm

Cells bắt đầu(1, 4): Hàm dùng chung SearchBlockArea sẽ cho giá trị trả về là r1,c1
Cells kết thúc(3, 6):= Tọa độ của cells bắt đầu + 2
Do đó ta sẽ có đầu vào cho hàm isExistNum là (r1, c1, r1 + 2, c1 + 2)

Ví dụ 2:
Bạn cần đăng nhập để thấy đính kèm


Cells bắt đầu=(2, 1)
Cells kết thúc=(2, 9)
Dòng chứ cells hiện tại là r
Do đó ta sẽ có đầu vào cho hàm isExistNum là(r, 1, r, 9)

Giá trị tìm kiếm tồn tại hay không sẽ trả lưu vào ba biến số check1~3
Trường hợp num tồn tại thì ta được True
Trường hợp num chưa tồn tại thì ta được False

Tóm lại num tồn tại hay chưa thì code sẽ là:
Mã:
If check1 = True Or check2 = True Or check3 = True Then
    '~Xử lý~
End If
Nếu như tồn tại rồi thì ta ghi vào cờ:
Mã:
CheckFlag(num) = True
 

Euler

Administrator
Thành viên BQT
Loop 2: Xét duyệt các số num= 1~9
<Giản lược, không thuyết minh lại nữa nhé>
CheckFlag(nu) = False thì xử lý...
Mã:
If CheckFlag(num) = False Then

    Dim cnt As Long 'Đếm số lượng False
    cnt = cnt + 1
    
    Dim answer As Long 'Các ứng cử viên đáp án
    answer = num

End If
Điểm chính:
Giả sử trong các cờ của các số 1=9 có 3 cờ false là 3,5,7
Mỗi khi thấy False thì cnt lại +1 và chúng ta ghi đè đáp án vào answer theo thứ tự 3=>5=>7.
Như vậy với kết quả cnt =3 thì answer là không cần thiết.
Khi chương trình kết thúc thì các giá trị cũng được reset cho nên chúng ta không cần lo lắng về biến answer.
Trường hợp cnt = 1:
Mã:
If cnt = 1 Then 'Nếu xác định được đáp án thì ghi đáp án vào ô trống
    Call AnswerSet(r, c, answer)
End If
Trong trường hợp chỉ có một cờ false (cnt =1) thì ta sẽ xác định được đáp án. Thủ tục dùng chung AnswerSet sẽ được gọi.
Bạn cần đăng nhập để thấy đính kèm

Tóm lại là:
Với module chung, phần xử lý sẽ là:
Mã:
For r = 1 To 9
    For c = 1 To 9

        r1 = SearchBlockArea(r)
        c1 = SearchBlockArea(c)

        'Gọi phương án giải 1 ra tìm đáp án
        If Cells(r, c).Value = "" Then Call Solution1

        '~phương án giải 2~

        '~phương án giải 3~
            
    Next c
Next r
Module phương án giải 1 sẽ là:
Mã:
Option Base 1 'Mảng sẽ bắt đầu từ chỉ số là 1'
' ------------------------
' * Module phương án giải 1
' ------------------------

Sub Solution1()

    Dim CheckFlag(9) As Boolean

    For num = 1 To 9 'Loop1
        
        Dim check1 As Boolean, check2 As Boolean, check3 As Boolean
        
        check1 = isExistNum(r1, c1, r1 + 2, c1 + 2) '① Tìm trong BlockArea
        check2 = isExistNum(r, 1, r, 9) '② Tìm trong hàng
        check3 = isExistNum(1, c, 9, c) '③ Tìm trong cột
        
        '①②③ mà tìm thấy num thì sẽ chuyển Flag = True
        If check1 = True Or check2 = True Or check3 = True Then
            CheckFlag(num) = True
        End If
    
    Next num

    For num = 1 To 9 'Loop 2
    
        If CheckFlag(num) = False Then
        
            Dim cnt As Long 'Số lượng cờ False
            cnt = cnt + 1
            
            Dim answer As Long 'Ứng cử viên đáp án
            answer = num
        
        End If
    
    Next num
    
    If cnt = 1 Then 'Xác định được đáp án thì ghi vào ô trống
        Call AnswerSet(r, c, answer)
    End If
    
End Sub
 

vbano1

SMod
Thành viên BQT
==========
PHẦN 3: Các phương án giải (tiếp theo)
==========
Phương án giải số 2:
Các biến số dưới đây tiếp tục được sử dụng:
Tên biến sốKiểu biếnĐịnh nghĩa
PuzzleAreaRangeÔ vuông lớn 9x9
BlockAreaRangePuzzleArea: Ô vuông nhỏ 3x3
rLongDòng của ô vuông 9x9
cLongCột của ô vuông 9x9
r1LongDòng của ô bắt đầu trong khối BlockArea
c1LongCột của ô bắt đầu trong khối BlockArea
numLongCác số từ 1 đến 9

Phương án giải số 2 là chúng ta sẽ đi tìm cells.
Bạn cần đăng nhập để thấy đính kèm

Ví dụ:
Đối với ô vuông 3x3 được bao quanh bởi đường viền đỏ ở trên, thì ta bắt đầu từ ô A1.
Ở khu vực này có bốn ô trống. Các số chưa được điền là 2,5,7,8.
Các ô A2,C2 cùng hàng và có số 5 nằm ở trên hàng đó.
Ô B3: Có số 5 nằm trên cột chứa ô B3.
Nhu vậy: Số 5 chỉ có thể điền vào ô A1.

Trên đây chính là cách nghĩ khi đi tìm cells.

Biến cách nghĩ thành hình ảnh trực quan:
Bạn cần đăng nhập để thấy đính kèm

Thời điểm nào thì gọi phương án giải số 2 ra giải quyết?
Phương án giải số 2 là một trong các phương án để giải bài toán với ô vuông 3x3.
Trong ô vuông 9x9, mỗi khi nhìn thấy ô màu vàng như dưới đây, thì ta sẽ gọi phương án giải số 2 ra giải quyết.
Bạn cần đăng nhập để thấy đính kèm


Kiểm tra trước khi gọi phương án giải số 2:
Nếu như ô vuông 3x3 đã được lấp đầy không còn ô trống, thì việc gọi phương án giải số 2 ra giải quyết là không cần thiết.
Vì vậy ta cần có bước kiểm tra, xem ô vuông 3x3 đã được lấp đầy hay chưa? Nếu chưa được lấp đầy thì phải gọi thủ tục phương án giải số 2 ra giải quyết.
Bạn cần đăng nhập để thấy đính kèm


Kiểm tra (1):
Ta sẽ kiểm tra các số từ 1~9 đã tồn tại trong ô vuông 3x3 hay chưa, nếu tồn tại rồi thì chuyển sang số tiếp theo.
Ví dụ: Số 1 đã tồn tại rồi, thì ta sẽ chuyển sang số 2.
Bạn cần đăng nhập để thấy đính kèm

Số 2 chưa tồn tại, cho nên ta chuyển sang xử lý (2)
Bạn cần đăng nhập để thấy đính kèm

:
:
Cứ như vậy ta thử hết các số cho tới 9.
Xử lý (2):
Ở hình dưới đây, ta có ví dụ, ta cần điền số 2 và ta có bốn vị trí ô trống màu vàng, ta sẽ cho thử lần lượt các vị trí xem vị trí nào thỏa mãn.
Bạn cần đăng nhập để thấy đính kèm

Nếu cùng hàng và cùng cột đã tồn tại số 2 rồi thì sẽ không thể nhập số 2 vào vị trí đó.
Trường hợp có thể nhập số 2 vào thì ta sẽ lưu thông tin gồm có 3 biến số sau:
Tên biến sốKiểu dữ liệuĐịnh nghĩa
SetCntLongĐếm số lượng cells có khả năng nhập số này vào
yLongLưu thông tin dòng của cells có khả năng nhập số này
xLongLưu thông tin cột của cells có khả năng nhập số này

Cụ thể, sau đây ta sẽ thuyết minh bằng hình ảnh cho dễ hiểu:
Biến số: SetCnt
Bạn cần đăng nhập để thấy đính kèm

Cách dùng:
Bạn cần đăng nhập để thấy đính kèm

Ta tăng biến SetCnt lên 1: SetCnt = SetCnt+1
Và lưu thông tin dòng và cột của ô A1 vào các biến y và x.
Bạn cần đăng nhập để thấy đính kèm
 

tuhocvba

Administrator
Thành viên BQT
Ở đây sẽ có một điểm thắc mắc: Tại sao ta đã có biến toàn cục (public) hàng r và c của cells hiện tại rồi mà lại còn tạo thêm biến mới hàng y và cột x làm gì nữa?
Bạn cần đăng nhập để thấy đính kèm

Phương án giải 2 check từng cells trong ô 3x3 chứa cells hiện tại, vì vậy hàng và cột sẽ khác với hàng và cột của cells hiện tại. Như trong ảnh trên, ta sẽ phải quét toàn bộ các cells có hàng 4~6 và cột 4~6, trong khi đó cells hiện tại lúc này thì đang cố định hàng r = 5 và cột c = 4.
Vì vậy ta sử dụng thêm hai biến mới là y và x như đã nói ở bài viết phía trên.
Bạn cần đăng nhập để thấy đính kèm

Để bạn đọc hình dung biến y và x được sử dụng như thế nào, tôi sẽ minh họa dưới đây, chúng ta sẽ thử kiểm tra xem số 2 sẽ được điền vào đâu:

Bạn cần đăng nhập để thấy đính kèm

Quyết định kết quả:
Trường hợp SetCnt > 1: Tức là có quá nhiều khả năng, ta không thể đi tới quyết định kết quả được.
Trường hợp SetCnt = 1: Đây là trường hợp chỉ có một đáp số, do đó ta đi tới quyết định sẽ điền đáp số vào ô trống mà ta tìm được.
Bạn cần đăng nhập để thấy đính kèm

Sau mỗi lần kiểm tra một số, sang số mới, chúng ta phải reset SetCnt = 0. Ví dụ kiểm tra xong số 2, ta kiểm tra tiếp số 8 thì trước khi kiểm tra số 8 phải reset biến số SetCnt cho nó về 0.
 

Euler

Administrator
Thành viên BQT
Như vậy flowchart cho phương án giải số 2 sẽ là:
Bạn cần đăng nhập để thấy đính kèm
 

tuhocvba

Administrator
Thành viên BQT
Tới đây chúng ta sẽ đi vào chương trình cụ thể:
Mã:
If (r = 1 Or r = 4 Or r = 7) And (c = 1 Or c = 4 Or c = 7) Then Call Solution2
Thủ tục phương án giải số 2 có tên là Solution2.
Hàng r là 1,4 hay 7 cột c là 1,4 hay 7 thì ta gọi thủ tục này ra giải quyết.
Bạn cần đăng nhập để thấy đính kèm


Các xử lý của phương án giải số 2:
Dựa vào flowchart, ta sẽ xây dựng toàn bộ chương trình cho phương án giải số 2.
Ô vuông 3x3 có cells rỗng hay không:
Mã:
Dim BlockArea As Range
Set BlockArea = Range(Cells(r1, c1), Cells(r1 + 2, c1 + 2))
    
'Ô vuông 3×3 không còn cells rỗng thì kết thúc
If WorksheetFunction.CountBlank(BlockArea) = 0 Then Exit Sub
Đối tượng ô vuông 3x3 ta thiết định bằng biến số BlockArea(Object Range).
Hàm CountBlank sẽ kiểm tra khối vuông 3x3 BlockArea có bao nhiêu cells rỗng, nếu là 0 thì cho kết thúc phương án giải số 2 ngay.
Loop 1: Vòng lặp cho num = 1~9
Mã:
For num = 1 to 9
    '~Xử lý~
Next num
Đến đây, mọi người không có thắc mắc gì chứ?
Khối vuông 3x3 đã tồn tại số num hay chưa?
Mã:
If isExistNum(r1, c1, r1 + 2, c1 + 2) = False Then
    '~Xử lý~
End If
Ta gọi hàm dùng chung isExistNum để kiểm tra.
Bạn cần đăng nhập để thấy đính kèm

Tham số đầu vào và giá trị trả về:
Tham số đầu vào gồm có 4 dữ liệu để xác định vùng Range cần kiểm tra.
  • Dòng của cells bắt đầu
  • Cột của cells bắt đầu
  • Dòng của cells kết thúc
  • Cột của cells kết thúc
Giá trị trả về:
num tồn tại thì giá trị trả về của hàm là True.​
num không tồn tại thì giá trị trả về của hàm là False.​
Chạy hết các ô trong ô vuông 3x3 xem cells là rỗng hay không:
Mã:
Dim cell As Range
For Each cell In BlockArea 'Chạy hết các cells trong khối 3x3
        
    If cell.Value = "" Then
        '~Xử lý~       
    End If
            
Next
Bạn cần đăng nhập để thấy đính kèm

Trường hợp cells rỗng thì công việc tiếp theo là:
[Tìm kiếm 1] Trong cùng hàng chứa cells ấy, số num đã tồn tại chưa?
[Tìm kiếm 2] Trong cùng cột chứa cells ấy, số num đã tồn tại chưa?
Mã:
Dim check1 As Boolean, check2 As Boolean

check1 = isExistNum(cell.Row, 1, cell.Row, 9) '① Tìm trong hàng
check2 = isExistNum(1, cell.Column, 9, cell.Column) '② Tìm trong cột
Nếu như cả kiểm tra 1 và kiểm tra 2 đều cho kết quả là False thì quá trình xử lý sẽ diễn ra:
Mã:
If check1 = False And check2 = False Then
    '~Xử lý~                   
End If
Cất kết quả:
Mã:
Dim SetCnt As Long
SetCnt = SetCnt + 1 'Số lượng cells có khả năng đáp ưng được tăng lên
                        
Dim y As Long, x As Long
y = cell.Row 'Lưu giá trị hàng của cells hiện tại
x = cell.Column 'Lưu giá trị cột của cells hiện tại
Nếu như kết thúc vòng lặp mà SetCnt = 1 thì có thể quyết định đáp án
Mã:
If SetCnt = 1 Then Call AnswerSet(y, x, num)
Sau đó ta phải reset lại biến SetCnt để phục vụ cho vòng lặp khác.
Mã:
SetCnt = 0
Tóm lại code sẽ là:
Module chung:
Mã:
For r = 1 To 9
    For c = 1 To 9

        r1 = SearchBlockArea(r)
        c1 = SearchBlockArea(c)

        'Gọi phương án giải số 1
        If Cells(r, c).Value = "" Then Call Solution1

        'Gọi phương án giải số 2
        If (r = 1 Or r = 4 Or r = 7) And (c = 1 Or c = 4 Or c = 7) Then Call Solution2

        'Phương án giải số 3
            
    Next c
Next r
Module phương án giải 2:
Mã:
Option Explicit
Option Base 1
' ------------------------
' * Module phương án giải số 2
' ------------------------

Sub Solution2()

    Dim BlockArea As Range
    Set BlockArea = Range(Cells(r1, c1), Cells(r1 + 2, c1 + 2))
    
    'Ô vuông 3×3 không còn cells rỗng thì kết thúc
    If WorksheetFunction.CountBlank(BlockArea) = 0 Then Exit Sub

    For num = 1 To 9
    
        'BlockArea(3×3): Kiểm tra đã tồn tại số num hay chưa
        If isExistNum(r1, c1, r1 + 2, c1 + 2) = False Then
            
            Dim cell As Range
            For Each cell In BlockArea 'Chạy hết các cells trong khối 3x3
            
                If cell.Value = "" Then
                
                    Dim check1 As Boolean, check2 As Boolean
                    check1 = isExistNum(cell.Row, 1, cell.Row, 9) '①Tìm kiếm trong hàng
                    check2 = isExistNum(1, cell.Column, 9, cell.Column) '② Tìm kiếm trong cột
            
                    'num chưa tồn tại cả trong hàng và trong cột
                    If check1 = False And check2 = False Then
            
                        Dim SetCnt As Long
                        SetCnt = SetCnt + 1 'Tăng lên 1
                        
                        Dim y As Long, x As Long
                        y = cell.Row 'Lưu giá trị hàng của cells hiện tại
                        x = cell.Column 'Lưu giá trị cột của cells hiện tại
                    
                    End If
            
                End If
            
            Next
            
            If SetCnt = 1 Then Call AnswerSet(y, x, num)
            
            SetCnt = 0 'Chuyển sang số num tiếp theo nên cần reset bộ đếm
            
        End If
    
    Next num
    
End Sub
 

Euler

Administrator
Thành viên BQT
==========
PHẦN 3: Các phương án giải (tiếp theo)
==========
Phương án giải số 3.1: Giải theo hàng
Ở phương án giải số 3 ta chia ra làm 3.1 giải theo hàng và 3.2 giải theo cột.
Ở phần này chúng ta tiếp tục sử dụng các biến số sau:
Tên biến sốKiểu dữ liệuĐịnh nghĩa
PuzzleAreaRangeKhối ô vuông tổng thể 9x9
BlockAreaRangeKhối ô vuông con 3x3 PuzzleArea
rLongHàng của khối ô vuông 9x9
cLongCột của khối ô vuông 9x9
r1LongHàng của cells bắt đầu của khối BlockArea
c1LongCột của cells bắt đầu của khối BlockArea
numLongSố từ 1~9
Tôi sẽ thuyết minh dòng 1 khoanh đỏ như hình dưới đây:
Bạn cần đăng nhập để thấy đính kèm

Ở dòng 1 có 4 cells trống, và có 4 số có thể điền vào các vị trí này là 1,4,6,7.
Ô D1 và F1 đều nằm trong khối Block 3x3 mà đã có số 1. Vì vậy không thể điền 1 vào D1 và F1.
Ô G1: Trong cột chứa ô G1 đã có số 1 nên không thể điền 1 vào ô G1.
Từ lập luận trên, ta thấy rằng 1 chỉ có thể điền vào ô A1.
Đây chính là cách nghĩ của việc giải bài toán theo hàng.
Cách nghĩ của cách giải này giống với phương án giải số 2, nhưng phạm vi tìm kiếm thì khác.
Phương án giải số 2: Điền số vào trong ô vuông 3x3.
Phương án giải số 3.1: Điền số vào hàng.
Bạn cần đăng nhập để thấy đính kèm

Chúng ta sẽ sử dụng cách nghĩ này và giải lần lượt từng hàng.
 
Top