//------------------------------------------------------------------------------
// Задача о 8 ферзях (точнее, об n ферзях)
//------------------------------------------------------------------------------

BackStep << prefunc
NotFullSetNextQ << prefunc

//.....................................................
// Проверка того, что один ферзь бьет другого
IsAttack << funcdef QvsQ
  // QvsQ имеет формат ((row1,col1),(row2,col2)),
  // где (row1, col1) - координаты первого ферзя,
  // (row2, col2) - координаты второго ферзя.
{
  row1 << QvsQ:1:1; col1 << QvsQ:1:2;
  row2 << QvsQ:2:1; col2 << QvsQ:2:2;
  [(row1, row2), 
   (col1, col2), 
   ([(row1,col1),(row2,col2)]:-), 
   ([(row1,col1),(row2,col2)]:+)
  // Далее приходится извращаться...
  ]:=

  // Или так...
  //:(.):[(1,2),(3,4)]:+:(.):+

  // это то же, но раздельно
  //>> rezult;
  //rezult:(.):[(1,2),(3,4)]:+:(.):+
//  (rezult:?:type,.):<> // А хотелось бы так...

  :(.):+ >>return
}

//.....................................................
// Проверка того, что некоторый ферзь бьет хотя бы одного ферзя
// из всех ферзей, указанных в списке
//.....................................................
IsOneOfListAttack << funcdef QvsQList
  // QvsQList имеет формат ((row,col),((row1,col1),...(row1,col1))),
  // где (row, col) - координаты проверяемого ферзя,
  // (row2, col2) - координаты установленных ферзей.

  // Функция возвращает true, если ферзя атакуют 
  // или false, если позиция не атакуется
{
  Q << QvsQList:1; // Текущий ферзь - проблемы с обозначением
  QList << QvsQList:2; // Установленные ферзи

  len << QList:|; // Количество установленных ферзей
  // Делается одновременная проверка всех ферзей,
  // Хотя, возможно, это не рационально
  QDup << (Q, len):dup; // Список копий для текущего ферзя
  (QList, QDup):#:[]:IsAttack:(.):+ >>return
}

//.....................................................
// Поиск допустимой строки для очередного ферзя
//.....................................................
setRow << funcdef QList_Row_N
  // Формат аргумента: (QList, row, n), 
  // где QList - список уже установленных ферзей в формате:
  //   ((row1,col1),(row2,col2),...)
  // row - значение текущей строки, используемое для проверки на допустимость
  // n - размер доски, используется для перебора заданного числа вариантов.
{
  // Фиксируются начальные аргументы
  QList << QList_Row_N:1; // Список установленных ферзей
  row << QList_Row_N:2; // текущее значение строки
  n << QList_Row_N:3;     // Размер шахматной доски
  len << QList:|;       // Число установленных ферзей
  col << (len,1):+;    // Номер столбца для устанавливаемого ферзя

  // Проверка: атакуется ли текущая позиция?
  attack << (2, ((row,col), QList):IsOneOfListAttack:int):-;

  // Выбор дальнейших действий с использованием булевского селектора
  attack^
  (
    // Если ферзь атакуется, то необходимо его переставить на следующую 
    // позицию и снова проверить. Переставлять до тех пор, пока не будут
    // просмотрены все позиции или пока не будет найдено положительное решение.
    {block {
      nextRow << (row,1):+;
      [(2,(nextRow, n):>:int):-]^
        (
          0, // Дошли до конца доски, возвращается неподходящее значение
          {(QList,nextRow,n):setRow}
        ):. >>break
    }},
    // Ферзь не атакуется. Возвращается номер строки.
    row
  ):. >>return
}

//.....................................................
// Установка i-го ферзя из n возможных, начиная со строки row,
// учитывающая приход заполненного списка
//.....................................................
setNextQ << funcdef QListRowN
  // Формат QListRowN: (QList, row, n)
  // QList задает список устанавленных ферзей
  // в формате: ((row1,col1), ... (rown,coln))
  // row - начальная позиция для установки
  // n - размер шахматной доски

  // Функция возвращает список с еще одним добавленным ферзем
  // или n-элементный список, заполненный ошибочными значениями, 
  // если  установка нового ферзя невозможна
  // (практически недостижимо при n > 3)
  // При этом положение позиций ферзей внутри списка может измениться
{
  // Фиксируются начальные аргументы
  row << QListRowN:2;   // Исходная позиция для установки ферзя
  n << QListRowN:3;     // Размер шахматной доски
  QList << QListRowN:1; // Список установленных ферзей
  len << QList:|;       // Число установленных ферзей
  next << (len,1):+;    // Номер столбца для следующего ферзя

  // Если доска заполнена, то осуществляется выход без каких-либо действий
  // с возвращением существующего списка
  [(2,(len,n):=:int):-]^
  (
     QList,
   
     // В противном случае призводится формирование данного списка
     // Дополнительные функции используются из-за проблем с обработкой 
     // транслятором вложенных блоков (надеюс, временных)
     {QListRowN:NotFullSetNextQ}
  ):. >>return
};

//.....................................................
// Установка i-го ферзя из n возможных, начиная со строки row,
// не учитывающая приход заполненного списка
//.....................................................
NotFullSetNextQ << funcdef QListRowN
  // Формат QListRowN: (QList, row, n)
  // QList задает список устанавленных ферзей
  // в формате: ((row1,col1), ... (rown,coln))
  // row - начальная позиция для установки
  // n - размер шахматной доски

  // Функция возвращает список с еще одним добавленным ферзем
  // или n-элементный список, заполненный ошибочными значениями, 
  // если  установка нового ферзя невозможна
  // (практически недостижимо при n > 3)
  // При этом положение позиций ферзей внутри списка может измениться
{
  // Фиксируются начальные аргументы
  row << QListRowN:2;   // Исходная позиция для установки ферзя
  n << QListRowN:3;     // Размер шахматной доски
  QList << QListRowN:1; // Список установленных ферзей
  len << QList:|;       // Число установленных ферзей
  next << (len,1):+;    // Номер столбца для следующего ферзя

  // Если доска пустая, то ферзь ставится в указанную позицию и первую колонку
  [(2,(len,0):=:int):-]^
  (
    ((row,1)),
    // В противном случае идет установка в следующие строки 
    {block {
      // Запускается процесс поиска строки, удовлетворяющей условию задачи
      // Возвращается номер строки или 0, если строка не найдена
      goodRow << (QList, row, n):setRow;
      badNextRow << (2,(goodRow, 0):=:int):-;
      badNextRow^
      (
        // Если строка оказалась не найденной, необходимо изменить положение
        // ранее поставленного ферзя, попытавшись найти для него новую позицию, 
        // начиная с первой, а затем еще раз повторить попытку установки 
        // заданного ферзя c первой позиции
        {((QList, n):BackStep, 1, n):setNextQ},

        // Строка найдена: нужно добавить к списку еще один элемент и осуществить 
        // поиск позиции для следующего ферзя. И так до тех пор, пока не дойдем 
        // до конца шахматной доски
        {
          (QList:[], (goodRow,next))
        }
      ):.
      >>break
    }} // Конец блока поиска строки
  ):. >>return
};

//.....................................................
// Если строка оказалась не найденной, необходимо изменить положение
// ранее поставленного ферзя, попытавшись найти для него новую позицию
// Функция введена из-за проблем с вложением блоков
//.....................................................
BackStep << funcdef QListAndN
{
  // Фиксируются начальные аргументы
  n << QListAndN:2;     // Размер шахматной доски
  QList << QListAndN:1; // Список установленных ферзей
  len << QList:|;       // Число установленных ферзей

  // Необходимо проверить, опустел ли список ферзей?
  // Если это так, то правильные установки невозможны.
  [(2,(len,0):=:int):-]^
  ( 
    // При откате до нуля возвращается заполненный список
    // с занесенными ошибочными значениями.
    {((0,n):dup,(0,n):dup):#}
    , 

    // В противном случае осуществляются дальнейшие операции
    {block{
      // Определим строку для последнего установленного ферзя
      lastRow << QList:len:1;
      // Сократим список на последний элемент
      shortQList << QList:[len:-];
      // И продолжим устанавливать предыдущего ферзя со следующей строки
      // Но, предварительно надо проверить на выход за границы доски
      [(2,(lastRow, n):=:int):-]^
      ( 
        {(shortQList, n):BackStep}, // Еще шаг назад с переустановкой предыдущего ферзя
        {(shortQList, (lastRow,1):+, n):setNextQ} // Текущего ферзя на следующую позицию
      ):.
      >>break
    }}
  ):
  . >>return
}

//.....................................................
// Добавление всех оставшихся ферзей из n возможных, к уже установленным
// Формируется первая найденная комбинация
FirstAppend <<  funcdef QListAndN
  // Формат QListAndN: (QList, n)
  // QList задает список уже устанавленных ферзей
  // в формате: ((row1,col1), ... (rown,coln))
  // row - начальная позиция для установки
  // n - размер шахматной доски

  // Функция возвращает список с уже расставленными ферзями
  // или пустой список, если невозможна установка всех ферзей 
  // (практически недостижимо при n > 3)
{
  // Фиксируются начальные аргументы
  n << QListAndN:2;     // Размер шахматной доски
  QList << QListAndN:1; // Список установленных ферзей
  len << QList:|;       // Число установленных ферзей
  next << (len,1):+;    // Номер столбца для следующего ферзя

  [(2, (len,n):=:int):-]^
  (
    // При равенстве длин, список можно считать сформированным
    QList,
    // В противном случае необходимо добавить еще ферзей
    {block {
      // Устанавливается следующий ферзь на первую позицию
      // И рекурсивно процесс повторяется для последующих ферзей
      break<< ((QList,1,n):setNextQ, n):FirstAppend 
    }} // Блок добавления ферзей завершен
  ):
  . >>return
}

//.....................................................
// Установка всех ферзей из n возможных, начиная с первого
// Формируется первая найденная комбинация
QN_first << funcdef n
  // n - размер шахматной доски
{
  // Начинаем с пустой доски
  return<< ((),n):FirstAppend
}

//.....................................................
// Установка восьми ферзей из 8 возможных
// Формируется первая найденная комбинация
Q8_first << funcdef
{
  return<< 8:QN_first
}

//==============================================================================
// Тестовые функции 
//==============================================================================

//------------------------------------------------------------------------------
//
testIsAttack << funcdef {
[
  ((1,1),(1,1)):IsAttack, 
  ((1,1),(1,2)):IsAttack, 
  ((1,1),(1,3)):IsAttack, 
  ((1,1),(3,1)):IsAttack, 
  ((1,1),(2,3)):IsAttack, 
  ((1,1),(3,2)):IsAttack, 
.]>>return
}

//------------------------------------------------------------------------------
//
testIsOneOfListAttack << funcdef {
[
  ((1,1),((2,3),(2,4),(4,3))):IsOneOfListAttack, 
  ((1,1),((1,1),(2,1),(2,2),(3,3),(5,5),(4,4))):IsOneOfListAttack, 
.]>>return
}

//------------------------------------------------------------------------------
//
testSetRow << funcdef {
[
  (((1,1)),2,6):setRow, 
.]>>return
}