Сделал небольшой перерыв в своих занятиях на 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