Программа на Icon для решения Судоку

Привет, друзья! Сегодня я хочу поделиться своим опытом создания программы для решения головоломки «Судоку» на языке программирования Icon. Почему именно Icon? Этот язык может показаться немного старомодным, но он обладает мощными инструментами для работы с текстом и структурами данных, что делает его интересным выбором для решения задач типа Судоку. Моей целью было не только создать рабочую программу, но и глубже погрузиться в возможности Icon, чтобы лучше понять его применение.

Что такое Судоку?

Судоку — это логическая головоломка с числами. Цель игры — заполнить 9×9 сетку цифрами от 1 до 9 таким образом, чтобы каждая цифра встречалась только один раз в каждой строке, каждом столбце и каждом из девяти 3×3 подрешёток.

Вот пример решённой головоломки Судоку:

План реализации программы

Моя программа будет работать следующим образом:

1. Считывать не полностью заполненную сетку Судоку.
2. Использовать алгоритм поиска с возвратом (backtracking) для заполнения сетки.
3. Проверять каждое возможное значение перед его вставкой в сетку, чтобы убедиться, что оно не нарушает правила Судоку.
4. Выводить решённую головоломку.

Реализация программы

Вот код программы на языке Icon с комментариями:

procedure main()
    initial_board := [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
    ]

    if solve_sudoku(initial_board) then {
        write("Solved Sudoku:")
        print_board(initial_board)
    } else {
        write("No solution exists.")
    }
end

procedure solve_sudoku(board)
    local row, col

    # Находим первую пустую ячейку
    every row := 1 to 9 do {
        every col := 1 to 9 do {
            if board[row][col] = 0 then {
                # Пробуем числа от 1 до 9
                every num := 1 to 9 do {
                    if is_safe(board, row, col, num) then {
                        board[row][col] := num
                        if solve_sudoku(board) then return 0
                        board[row][col] := 0
                    }
                }
                return 1  # Если ни одно число не подходит
            }
        }
    }
    return 0  # Если все ячейки заполнены
end

procedure is_safe(board, row, col, num)
    local i, j, box_row_start, box_col_start

    # Проверяем строку и столбец
    every i := 1 to 9 do {
        if board[row][i] = num | board[i][col] = num then return 1
    }

    # Проверяем 3x3 подрешетку
    box_row_start := (row - 1) / 3 * 3 + 1
    box_col_start := (col - 1) / 3 * 3 + 1
    every i := box_row_start to box_row_start + 2 do {
        every j := box_col_start to box_col_start + 2 do {
            if board[i][j] = num then return 1
        }
    }

    return 0
end

procedure print_board(board)
    local row, col
    every row := 1 to 9 do {
        every col := 1 to 9 do {
            if col % 9 = 0 then {
                write(board[row][col])
            } else {
                write(board[row][col], " ")
            }
        }
    }
end

---

---