Разработка на коленке

"тут должна быть красивая цитата о программировании"

8 Queens puzzle на OCaml методом минимальных конфликтов

2016-12-06 23:14
8 queens puzzle

Сделал небольшой перерыв в своих занятиях на codingame, чтобы больше уделить внимания "зелёной книге" (Искусственный интеллект. Питер Норвиг). В теме про локальный поиск мне очень понравилась эвристика с минимальными конфликтами, и я решил написать её реализацию для задачи о 8 ферзях (на самом деле для произвольного количества ферзей, но об этом ниже).

Сначала я сделал версию с кучей хардкода, большим количеством кусков закоментированного кода, неудачной реализацией вложенных циклов через рекурсию - [1]. Эта версия почти всегда работала. Почти, потому что она не обрабатывала граничные условия в виде пустой доски или доски с 1 и 2 ферзями. Но это меня не смущало, потому что это было проблемой реализации обхода данных, что на OCaml у меня порой вызывает затруднения.

В таком виде, помимо очевидных проблем, меня не устраивало то, что количество конфликтов считается каждый раз для всех ферзей, поэтому я задумал реализацию, в которой матрица конфликтов должна храниться постоянно, а пересчитываться только для изменившихся данных (и даже несмотря на это, программа долго работает уже с 500 ферзями).

Потом было несколько неудачных попыток реализовать задуманное, но в итоге у меня получилось решение, которое на данный момент меня почти устраивает. Почти, потому что хочется наглядную визуализацию шахматной доски, пусть и в терминале, а ещё неплохо бы прикрутить выгрузку в JSON всех шагов поиска решения с последующей визуализацией в браузере. Но это пока только в планах.

С точки зрения изучения OCaml, самым интересным для меня стали попытки реализовать break из вложенных циклов при помощи рекурсии, а потом при помощи исключений.

let under_attack board i1 i2 =
    board.(i1) = board.(i2) || (abs (i1 - i2)) = (abs (board.(i1) - board.(i2)))


let allsafe board =
    let under_attack = under_attack board in

    let last_index = (Array.length board) - 1 in
    try
        for i1 = 0 to (last_index - 1) do
            for i2 = i1 + 1 to last_index do
                if under_attack i1 i2 then raise Wrong
            done
        done;
        true
    with Wrong -> false

Репозиторий ocaml-8queens

comments powered by Disqus