ĐỌC VUI VÀ SUY NGHĨ

Cổ vũ lòng yêu thích các trò chơi hữu ích cho sự luyện tập trí óc trong cộng đồng người Việt

QLSU05 – Hình chữ nhật không giải được

Xét khung Sudoku sau đây:

Bốn ô E2, I2, I3, E3 là 4 đỉnh của một hình chữ nhật. Bốn đỉnh nầy đều có trị khả dụng là 2,8.
Nếu E2 = 2 => E3 = 8, I3 = 2, I2 = 8
Nếu E2 = 8 => E3 = 2, I3 = 8, I2 = 2

Như vậy thì khung Sudoku có 2 lời giải. Theo quy ước thì một Sudoku đúng phải chỉ có một lời giải duy nhất => Sudoku trên không giải được và E2I2I3E3 được gọi là hình chữ nhật không giải được. Trị khả dụng chung 2, 8 của 4 đỉnh gọi là trị của hình chữ nhật.

Hình chữ nhật không giải được xảy ra khi khung Sudoku không có một lời giải duy nhất.
Nói khác đi, hình chữ nhật không giải được không thể xảy ra trong bất cứ khung Sudoku (đúng) nào.

Gọi A (n,m), B (n,m), C (n,m) and D (n,m) là 4 đỉnh của một hình chữ nhật không giải được có trị ‘n’ và ‘m’, nằm trong 1 khung Sudoku đúng.

a) Giả sử chỉ có đỉnh D là có chứa thêm 1 trị khả dụng khác ‘p’, hay D(n,m,p).

Nếu ‘p’ không phải là trị của D, thì ABCD là 1 chữ nhật không giải được .
Vậy: ‘p’ phải là trị của D.

b) Giả sử có 2 đỉnh không đối xứng C và D, mỗi đỉnh có chứa thêm 1 trị khả dụng lần lượt là
‘p’ và ’q’, hay C(n,m,p) và D(n,m,q).

Nếu ‘p’ không phải là trị của C và ‘q’ không phải là trị của D, thì ABCD là 1 hình chữ nhật
không giải được.
Vậy: ‘p’ phải là trị của C hoặc ‘q’ phải là trị của D.
Ta có thể xem như C và D hợp lại thành 1 ô giả (dummy cell) X có trị khả dụng là ‘p’ và ‘q’.

Nếu trong một hành phần (hàng, cột hay khối) chứa C và D, có 1 ô Y cũng có trị khả dụng
là ‘p’ và ‘q’, thì 2 ô X và Y hợp thành một cặp 2 ô Sudoku với trị khả dụng ‘p’ và ‘q’.
Suy ra: Trong thành phần chứa C, D và Y, các ô khác C, D, Y không thể có trị số là ‘p’
hay ‘q’ (hay không thích hợp với ‘p’ và ‘q’)

Tính chất trên có thể suy rộng đến trường hợp khi số các trị khả dụng khác ‘n’ và ‘m’ bằng 2,
như các trường hợp sau đây:

C (n, m, p) D (n, m, q)
C (n , m) D (n, m, p, q)
C (n, m, p) D (n, m, p, q) Y (p, q)
C (n, m, p, q) D (n, m, p, q)

c) Nếu C và D đều chứa thêm cùng 1 trị khả dụng ‘p’, tức là C(n,m,p), D(n,m,p), thì hoặc C hoặc
D phải có trị là ‘p’. Suy ra, các ô trống trong thành phần chứa C và D không thể có trị ‘p’.

Thí dụ 1:   Xét khung Sudoku:

Trong dãy khối ngang 2, xét hình chữ nhật hợp bởi 4 ô D2(7,8), D7 (7, 8),
F7 (7, 8, 4) and F2 (7, 8).

Nếu 4 không phải là trị của F7, thì D2D7F7F2 là 1 hình chữ nhật không giải được.
Để tránh trường hợp nầy, F7 phải bằng 4.

F7 = 4 => F8 = 7 => F2 = 8 => D2 = 7 => D7 = 8
=> I7 = 7 => I4 = 3 => I8 = 4

Thí dụ 2:   Xét khung Sudoku:

Trong dãy khối dọc 1, xét hình chữ nhật hợp bởi 4 ô H1(1,6), H3(1,6), C1(1,6,7)
và C3(1,6,4.

Nếu C1 = 1 hay 6 => C3 = 4
Nếu C3 = 1 hay 6 => C1 = 7
=> C1 và C3 hợp thàng 1 ô giả X có trị khả dụng là 4 và 7.

Trong khối 1, thành phần chứa 2 đỉnh không đối xứng C1 C3 của hình chữ nhật H1H3C3C1, có chứa ô B2(4,7)

=> X(4,7) và B2(4,7) hợp thàng 1 cặp 2 ô Sudoku với trị khả dụng 4 và 7
=> Các ô của khối 1, khác C1, C3 và B2, không thể có trị là 4 hay 7
=> Các ô A1 và A2 không thể có trị 4 hay 7 => A2 = 6, A1 = 8.

Tương tự, trên hàng C chứa C1 và C3, có ô C7(4,7)
=> X(4,7) và C7(4,7) hợp thàng 1 cặp 2 ô Sudoku với trị khả dụng 4 và 7
=> Các ô của hàng C, khác C1, C3 và C7, không thể có trị là 4 hay 7
=> Ô C5(4,6,7) không thể có trị 4 hay 7 => C5 = 6

Thí dụ 3: Xét khung Sudoku:

Trong dãy khối dọc 1, xét hình chữ nhật hợp bởi 4 ô I1(4,8), I3(4,8), C1(4,8,5) và C3 (4, 8, 6).

Nếu C1 = 4 hay 8 => C3 = 6
Nếu C3 = 4 hay 8 => C1 = 5

Trên hàng C, thành phần có chứa 2 đỉnh không đối xứng C1 và C3 của hình chữ nhật I1 I3 C3 C1, có 1 cặp 2 ô Sudoku với tri 5, 6 hợp bởi ô C9(5,6 và ô giả tạo bởi C1 và C3.

=> Trên hàng C, các ô, ngoài C1, C3, C9, không thích hợp với 5 và 6
=> Hai ô C5(5,6,8) và C6(5,7,8) không thích hợp với 5 và 6
=> C5 = 8   =>   C6 = 7

 
%d bloggers like this: