PDA

View Full Version : Bài toán về số trường hợp Sudoku



TranVuMaiAnh
12-06-2009, 08:27 PM
Có 1 số bài bọn bạn đố tớ mà nghĩ ko ra nên post lên nhờ a e giải típ, mọi người cùng giúp nhé:
1. Có thể tạo được bao nhiêu ô số Sudoku dạng thường (nghĩa là ô dạng có các khu vực 3x3 hình vuông)
2. Có thể tạo được bao nhiêu ô số Sudoku ma trận (nghĩa là các khu vực phân biệt có 9 ô nhưng là hình dáng bất kỳ, không phải hình vuông)

i love rubik
13-06-2009, 08:56 PM
Số cách điền cũng chính là số trường hợp.
http://i612.photobucket.com/albums/tt208/zhugeliang95/a.jpg
Giải thích:
Màu vàng:
Ô 1: 9 cách (từ 1->9)
Ô 2: 9-1=8 (cách).
...
=>9! cách.
Màu xanh lá
Tương tự như trên
=>Có 6! cách
Màu xanh dương nhạt
Có: 3!(cách)cho 1 vùng viền đỏ=> có: 4*3! cách
Màu cam:
Bằng màu xanh nhạt * 2/3 màu vàng: 6!*3!*4 (cách)
Màu trắng: ko biết làm :rolleyes::rolleyes:
Em mới học lớp 8 nên có thể làm sai, có j nhớ mấy anh sửa giúp.

UMU
18-06-2009, 04:27 PM
Mình nghĩ là bài toán này không chỉ đơn giản như vậy vì có sự ràng buộc giữa các ô ở cùng hàng, cùng cột và cùng ô lớn
Mình đưa ra một ví dụ để chứng minh như sau (xem file đính kèm):


Trong ví dụ này:
Chúng ta xét ô thứ 4 hàng 2, nếu vị trí các ô trước sắp xếp như TH1, các ô 4,5,6 hàng 1 trùng với các ô 1, 2, 3 hàng 2 thì ở đây ô 4 hàng 2 có 6 cách điền (trừ các giá trị là 4, 5, 6 )
Còn ở TH2, các ô 4,5,6 hàng 1 khác hoàn toàn với các ô 1, 2, 3 hàng 2 thì ở đây ô 4 hàng 2 chỉ có 3 cách điền (trừ các giá trị là 4, 5, 6, 7, 8, 9 )

i love rubik
18-06-2009, 04:41 PM
Mình nghĩ là bài toán này không chỉ đơn giản như vậy vì có sự ràng buộc giữa các ô ở cùng hàng, cùng cột và cùng ô lớn
Mình đưa ra một ví dụ để chứng minh như sau (xem file đính kèm):


Trong ví dụ này:
Chúng ta xét ô thứ 4 hàng 2, nếu vị trí các ô trước sắp xếp như TH1, các ô 4,5,6 hàng 1 trùng với các ô 1, 2, 3 hàng 2 thì ở đây ô 4 hàng 2 có 6 cách điền (trừ các giá trị là 4, 5, 6 )
Còn ở TH2, các ô 4,5,6 hàng 1 khác hoàn toàn với các ô 1, 2, 3 hàng 2 thì ở đây ô 4 hàng 2 chỉ có 3 cách điền (trừ các giá trị là 4, 5, 6, 7, 8, 9 )



Trường hợp bạn UMU nói, tường chừng như có 6 cách, nhưng nếu nhìn kĩ lại, thật chất cũng 3 cách.
Mặc dù chỉ phải loại bỏ 3 số 4,5,6 là ko điền được, nhưng cũng phãi loại bỏ 3 số 1,2,3. Vì nếu điền 1,2,3 lần lượt vào 3 ô đó sẽ ko còn số để điền vào 3 ô còn lại của hàng 2. (3 số duy nhất còn lại là 7,8,9 nhưng lại trùng)

Với lại, mình ko tính hàng 2 ngay (bạn đọc kĩ bài giải sẽ thấy)
Nếu có thể, mình sẽ chèn hình sau

UMU
19-06-2009, 08:36 AM
Trường hợp bạn UMU nói, tường chừng như có 6 cách, nhưng nếu nhìn kĩ lại, thật chất cũng 3 cách.
Mặc dù chỉ phải loại bỏ 3 số 4,5,6 là ko điền được, nhưng cũng phãi loại bỏ 3 số 1,2,3. Vì nếu điền 1,2,3 lần lượt vào 3 ô đó sẽ ko còn số để điền vào 3 ô còn lại của hàng 2. (3 số duy nhất còn lại là 7,8,9 nhưng lại trùng)

mình đâu có nói là điền lần lượt vào 3 ô đó đâu :D, chỉ xét riêng ô thứ 4 hàng 2 mà :D
Ý mình muốn nói ở đây là cách tính tổ hợp đơn thuần thì không đúng vì mỗi cách điền của ô trước liên quan đến ô sau :D

i love rubik
19-06-2009, 08:54 AM
Trường hợp bạn UMU nói, tường chừng như có 6 cách, nhưng nếu nhìn kĩ lại, thật chất cũng 3 cách.
Mặc dù chỉ phải loại bỏ 3 số 4,5,6 là ko điền được, nhưng cũng phãi loại bỏ 3 số 1,2,3. Vì nếu điền 1,2,3 lần lượt vào 3 ô đó sẽ ko còn số để điền vào 3 ô còn lại của hàng 2. (3 số duy nhất còn lại là 7,8,9 nhưng lại trùng)

mình đâu có nói là điền lần lượt vào 3 ô đó đâu :D, chỉ xét riêng ô thứ 4 hàng 2 mà :D
Ý mình muốn nói ở đây là cách tính tổ hợp đơn thuần thì không đúng vì mỗi cách điền của ô trước liên quan đến ô sau :D


Nếu chỉ xét riêng ô thứ 4, hàng thứ 2, thì cũng chỉ có 3 trường hợp. (chỉ điền được 3 số 7, 8, 9). Vì 3 số 1, 2, 3 đã sử dụng đềin vào 3 ô 7, 8, 9 của hàng 2.
Mình đã sửa lại bài trên

UMU
19-06-2009, 01:10 PM
uh, đúng rồi :P, ở ví dụ này thì vẫn là 3!. Mình muốn lấy một ví dụ đơn giản nhưng hóa ra lại sai. Đây!! ví dụ này chắc sẽ ko sai :D
Ở TH1 có ô 4 hàng 2, 5 cách {1; 2; 3; 7; 8} .Ví dụ điền các ô (4->9) như sau:
Cách 1: 1-7-8-2-3-6
Cách 2: 2-7-8-1-3-6
Cách 3: 3-7-8-1-2-6
Cách 4: 7-8-1-2-3-6
Cách 5: 8-7-1-2-3-6
Còn ở TH2 chỉ có 3 cách điền ô 4 hàng 2 là {1; 2; 3}

Vậy mình vẫn giữ nguyên quan điểm là các ô sau bị ràng buộc bởi các ô trước!
Hình vẽ trong bài giải của bạn: 3 hàng đầu bạn chỉ đề cập đến TH các ô vào thành 1 cụm (123, (456) hoặc (789) nên nó luôn là 3! :P

i love rubik
19-06-2009, 04:28 PM
@ UMU: Đồng ý với ý kiến của bạn.:) :"các ô sau bị ràng buộc bởi các ô trước!". Và nếu sau khi tính số trường hợp của hàng 1, ta tính hàng 2 thì sẽ ko tính được (theo như bạn giải thích).
Nhưng mình vẫn tin vào kết quả của bài mình :D:D:D:D.
Sau khi điền các số vào màu vàng và màu xanh lá, ta điền màu xanh nhạt.
Phần số cách điền của màu xanh nhạt, mình viết kết quả là 4*3!. Kết quả này đúng vớitrường hợp điền giống hình vẽ trong bài giải của mình. Còn những trường hợp ko như vậy (như VD bạn cho) thì mình ko giải thích đựơc:P.Nhưng mình nghĩ, số cách điền ở các trường hợp đó cũng phải bằng với trường hợp của mình,(còn nếu khác nhau thì bó tay :P:P) nên mới làm vậy.
Bạn thử suy nghĩ tính giùm số trường hợp màu xanh nhạt đó đi. Và tính cả số trường hợp của màu trắng còn lại nữa để hoàn thành bài toán.
P/s: biết bạn lớn hơn nên xưng ngang hàng ngại wa :P:P

UMU
19-06-2009, 05:36 PM
"mình" xưng thế với toàn bộ 4rum đấy chứ, tại "bạn" gọi mình là bạn ... làm mình cũng phải xưng lại thế :D haha
anh nghĩ là bài này chắc phải vét cạn, xét từng trường hợp tương đối 1 ví dụ như lúc nào thì là 5!, lúc nào là 3! hay là n! gì đó ...
rubik thì cũng có ràng buộc 2 màu dính nhau trong 1 viên cạnh, 3 màu dính nhau trong 1 viên góc xét đã khó, còn cái này số ô nhiều hơn mà các ô ràng buộc kiểu khác nên chắc ko ra ngay dc:D
Mọi người cũng suy nghĩ nhé!