# ===== CodeLab: Python 小游戏⑧:数独生成与求解(控制台) =====
# 来源: https://aoerliang.dpdns.org/articles/game-python-sudoku
# 以下代码片段按文章出现顺序拼接, 共 4 段

# ----- 片段 1 (python) -----
def valid(board, r, c, n):
    for i in range(9):
        if board[r][i] == n or board[i][c] == n:
            return False
    br, bc = r // 3 * 3, c // 3 * 3
    for i in range(3):
        for j in range(3):
            if board[br + i][bc + j] == n:
                return False
    return True

# ----- 片段 2 (python) -----
def solve(board):
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                for n in range(1, 10):
                    if valid(board, r, c, n):
                        board[r][c] = n
                        if solve(board):
                            return True
                        board[r][c] = 0    # 撤销
                return False
    return True

# ----- 片段 3 (python) -----
import random

def generate(difficulty=40):
    board = [[0] * 9 for _ in range(9)]
    solve(board)                     # 先生成完整终盘
    cells = [(r, c) for r in range(9) for c in range(9)]
    random.shuffle(cells)
    for r, c in cells[:difficulty]:
        board[r][c] = 0              # 挖掉
    return board

# ----- 片段 4 (python) -----
import random

def valid(board, r, c, n):
    for i in range(9):
        if board[r][i] == n or board[i][c] == n:
            return False
    br, bc = r // 3 * 3, c // 3 * 3
    for i in range(3):
        for j in range(3):
            if board[br + i][bc + j] == n:
                return False
    return True

def solve(board):
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                for n in range(1, 10):
                    if valid(board, r, c, n):
                        board[r][c] = n
                        if solve(board):
                            return True
                        board[r][c] = 0
                return False
    return True

def generate(difficulty=40):
    board = [[0] * 9 for _ in range(9)]
    solve(board)
    cells = [(r, c) for r in range(9) for c in range(9)]
    random.shuffle(cells)
    for r, c in cells[:difficulty]:
        board[r][c] = 0
    return board

def show(board):
    for r in range(9):
        row = ' '.join(str(board[r][c]) if board[r][c] else '.'
                       for c in range(9))
        print(row)
        if r in (2, 5):
            print()

board = generate(40)
show(board)
while True:
    cmd = input('\n输入: r c 数字(如 0 1 5), q 退出, s 求解: ')
    if cmd == 'q':
        break
    if cmd == 's':
        print('答案:')
        solve(board)
        show(board)
        break
    parts = cmd.split()
    if len(parts) != 3:
        print('格式错误'); continue
    r, c, n = map(int, parts)
    if not (0 <= r < 9 and 0 <= c < 9 and 1 <= n <= 9):
        print('范围错误'); continue
    if not valid(board, r, c, n):
        print('这个位置不能放', n); continue
    board[r][c] = n
    show(board)
    if all(all(x != 0 for x in row) for row in board):
        print('恭喜,填满了!')
        break