dao tao lai xe day lai xe hoc lai xe thi bang lai xe thang may tai khach tổ chức sự kiện nước khoáng lavie ho ca koi dep nem cao su van thanh Máy bơm hỏa tiễn Galaxy Cung cấp bánh bao giá sỉ công ty in biểu mẫu Bơm trục ngang Dây đồng hồ cá sấu Bộ dụng cụ đóng đai công ty in offset
Bài toán về số trường hợp Sudoku
Kết quả 1 đến 9 của 9
  1. #1
    TranVuMaiAnh's Avatar
    Nhập Môn

    Status
    Offline
    Ngày tham gia
    Apr 2009
    Bài viết
    11
    Cảm ơn
    1
    Cảm ơn 5 / 4 Bài viết

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

    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)

  2. #2
    i love rubik's Avatar
    Pocket Cube

    Status
    Offline
    Ngày tham gia
    Apr 2009
    Tuổi
    24
    Bài viết
    76
    Cảm ơn
    59
    Cảm ơn 94 / 18 Bài viết

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

    Số cách điền cũng chính là số trường hợp.

    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
    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.

  3. #3
    UMU's Avatar
    Pocket Cube

    Status
    Offline
    Ngày tham gia
    Oct 2008
    Tuổi
    27
    Bài viết
    145
    Cảm ơn
    36
    Cảm ơn 115 / 59 Bài viết

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

    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):
    Trích dẫn Trích dẫn
    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 )

  4. #4
    i love rubik's Avatar
    Pocket Cube

    Status
    Offline
    Ngày tham gia
    Apr 2009
    Tuổi
    24
    Bài viết
    76
    Cảm ơn
    59
    Cảm ơn 94 / 18 Bài viết

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

    Trích dẫn Gửi bởi UMU
    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):
    Trích dẫn Trích dẫn
    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

  5. #5
    UMU's Avatar
    Pocket Cube

    Status
    Offline
    Ngày tham gia
    Oct 2008
    Tuổi
    27
    Bài viết
    145
    Cảm ơn
    36
    Cảm ơn 115 / 59 Bài viết

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

    Trích dẫn Gửi bởi i love rubik
    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 , chỉ xét riêng ô thứ 4 hàng 2 mà
    Ý 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

  6. #6
    i love rubik's Avatar
    Pocket Cube

    Status
    Offline
    Ngày tham gia
    Apr 2009
    Tuổi
    24
    Bài viết
    76
    Cảm ơn
    59
    Cảm ơn 94 / 18 Bài viết

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

    Trích dẫn Gửi bởi UMU
    Trích dẫn Gửi bởi i love rubik
    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 , chỉ xét riêng ô thứ 4 hàng 2 mà
    Ý 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
    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

  7. #7
    UMU's Avatar
    Pocket Cube

    Status
    Offline
    Ngày tham gia
    Oct 2008
    Tuổi
    27
    Bài viết
    145
    Cảm ơn
    36
    Cảm ơn 115 / 59 Bài viết

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

    uh, đúng rồi , ở 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
    Ở 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!

  8. #8
    i love rubik's Avatar
    Pocket Cube

    Status
    Offline
    Ngày tham gia
    Apr 2009
    Tuổi
    24
    Bài viết
    76
    Cảm ơn
    59
    Cảm ơn 94 / 18 Bài viết

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

    @ 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 DD.
    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.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 ) 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

  9. #9
    UMU's Avatar
    Pocket Cube

    Status
    Offline
    Ngày tham gia
    Oct 2008
    Tuổi
    27
    Bài viết
    145
    Cảm ơn
    36
    Cảm ơn 115 / 59 Bài viết

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

    "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ế 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
    Mọi người cũng suy nghĩ nhé!

 

 

Thông tin về chủ đề này

Users Browsing this Thread

Có 1 người đang xem chủ đề. (0 thành viên và 1 khách)

Members who have read this thread : 2

Actions :  (View-Readers)

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •