Lập trình game sudoku bằng python
Trong bài này chúng ta sẽ sử dụng thuật toán quay lui để giải quyết bài toán giải Sudoku. Để hiểu thuật toán quay lui là gì mời bạn xem bài Thuật toán quay lui và minh họa. Show
Xem thêm: Python: Bài toán xếp hậu sử dụng đệ quy Bài viết tham khảo từ techwithtim.net 1. Giới thiệu luật chơi và cách giải SudokuSudoku là một trò chơi giải đố theo wiki định nghĩa như sau:
Cách giải trò chơi Sudoku, mời các bạn xem video hướng dẫn sau: 2. Thuật toán giải SudokuSau đây ta sẽ tìm thuật toán giải Sudoku bằng kỹ thuật backtracking, ngôn ngữ lập trình sử dụng là Python. Các bước tiến hành như sau:
Input, một câu đố sudoku biểu diễn bởi danh sách cau_do = [ [7,8,0,4,0,0,1,2,0], [6,0,0,0,7,5,0,0,9], [0,0,0,6,0,1,0,7,8], [0,0,7,0,4,0,2,6,0], [0,0,1,0,5,0,9,3,0], [9,0,4,0,6,0,0,0,5], [0,7,0,3,0,0,0,1,2], [1,2,0,0,0,7,4,0,0], [0,4,9,2,0,6,0,0,7] ] Chú ý rằng chỉ số 2.1. Viết hàm in câu đố Sudoku ra màn hìnhỞ đây chúng ta sử dụng giao diện dòng lệnh, chưa sử dụng giao diện đồ họa GUI nên sẽ sử dụng hàm Ta sẽ viết hàm Nếu dòng def in_sudoku(q): for d in range(len(q)): if d % 3 == 0 and d != 0: print("- - - - - - - - - - -") for c in range(len(q[0])): if c % 3 == 0 and c != 0: print("| ", end ="") if c == 8: print(str(q[d][c])) else: print(str(q[d][c]) + " ", end = "") Thử in với 2.2. Viết hàm tìm các ô trống trong SudokuMục tiêu của chúng ta là tìm các vị trí ô trống trong câu đố def tim_o_trong(q): for d in range(len(q)): for c in range(len(q[0])): if q[d][c] == 0: return d, c return None 2.3. Viết hàm kiểm tra tính hợp lệ của một câu đốdef kiem_tra(q, gia_tri, dong, cot): for i in range(len(q[0])): if q[i][cot] == gia_tri and i != dong: return False for i in range(len(q)): if q[dong][i] == gia_tri and i != cot: return False x = cot // 3 y = dong // 3 for i in range(y*3, y*3+3): for j in range(x*3, x*3+3): if q[i][j] == gia_tri and i != dong and j != cot: return False return True 2.4. Viết hàm chính để tìm lời giải cho một câu đố Sudokudef giai(q): tim_thay = tim_o_trong(q) if not tim_thay: return True else: d, c = tim_thay for i in range(1,10): if kiem_tra(q, i, d, c): q[d][c] = i if giai(q): return True else: q[d][c] = 0 return False 3. Chương trình Python giải Sudoku hoàn chỉnhcau_do = [ [7,8,0,4,0,0,1,2,0], [6,0,0,0,7,5,0,0,9], [0,0,0,6,0,1,0,7,8], [0,0,7,0,4,0,2,6,0], [0,0,1,0,5,0,9,3,0], [9,0,4,0,6,0,0,0,5], [0,7,0,3,0,0,0,1,2], [1,2,0,0,0,7,4,0,0], [0,4,9,2,0,6,0,0,7] ] def in_sudoku(q): for d in range(len(q)): if d % 3 == 0 and d != 0: print("- - - - - - - - - - -") for c in range(len(q[0])): if c % 3 == 0 and c != 0: print("| ", end ="") if c == 8: print(str(q[d][c])) else: print(str(q[d][c]) + " ", end = "") def giai(q): tim_thay = tim_o_trong(q) if not tim_thay: return True else: d, c = tim_thay for i in range(1,10): if kiem_tra(q, i, d, c): q[d][c] = i if giai(q): return True else: q[d][c] = 0 return False def tim_o_trong(q): for d in range(len(q)): for c in range(len(q[0])): if q[d][c] == 0: return d, c return None def kiem_tra(q, gia_tri, dong, cot): for i in range(len(q[0])): if q[i][cot] == gia_tri and i != dong: return False for i in range(len(q)): if q[dong][i] == gia_tri and i != cot: return False x = cot // 3 y = dong // 3 for i in range(y*3, y*3+3): for j in range(x*3, x*3+3): if q[i][j] == gia_tri and i != dong and j != cot: return False return True in_sudoku(cau_do) giai(cau_do) print('Loi giai cua Sudoku tren la:') in_sudoku(cau_do) Cho chạy chương trình, chúng ta được kết quả như hình sau: |