Я уже как-то говорил, что считаю awk недооцененным. Большинство примеров сводится к тому, чтобы убрать лишние колонки из отчета. А между тем, AWK, практически полноценный язык программирования.

Сегодня я Вам это постараюсь показать. Будем решать задачу о расстановке 8 ферзей на шахматной доске, так, чтобы они не били друг друга.

Роман Шубин
Роман Шубин
CEO & CTO, Главред в «Цифровой улей»
Задать вопрос
Решать будем методом перебора. Ну, не полного перебора, немного включим голову.

Напомню, ферзь бьёт по вертикали, горизонтали, диагонали. Поэтому для начала расставим каждого ферзя на свою вертикаль и будем двигать, проверяя условия боя.

Таких будет два - горизонталь и диагональ. Для удобства клеточки буду нумеровать с 0.

Итого - получаем 10 вложенных циклов (8 двигают ферзей, 2 - проверка условий боя) ха, тут всего-то 8^8=16777216 вариантов.

#!/bin/bash
#8 ферзей

awk 'BEGIN{
  for(c[0]=8;c[0]--;){
    for(c[1]=8;c[1]--;){
      for(c[2]=8;c[2]--;){
for(c[3]=8;c[3]--;){
  for(c[4]=8;c[4]--;){
    for(c[5]=8;c[5]--;){
      for(c[6]=8;c[6]--;){
        for(c[7]=8;c[7]--;){
          b=1
          for(i=0;i<7 && b;i++){
            for(j=i+1;j<8;j++){
              if(c[i]==c[j]){b=0;break}
              a=c[i]-c[j];n=j-i
              if(a==n || a==-n){b=0;break}}}
if(b){print c[0]c[1]c[2]c[3]c[4]c[5]c[6]c[7] }
}}}}}}}}
}'

Пояснения: c[i]==c[j]) - проверка на горизонталь.

a=c[i]-c[j];n=j-i - проверка на диагональ.

Вообще-то тут должен быть abs(c[i]-c[j]), но в awk нет модуля, поэтому if(a==n || a==-n)

Да, и в awk оператор break выходит из одного цикла, поэтому пришлось немного извращаться. (&& b), но задача решена.

Примечание: я знаю про алгоритмы пермутаций, но тут лобовое решение.

Вариантов всего 92.

Приведу последний: 04752613 Время выполнения на моем дохлом ноуте ~1.5 минуты.

Продолжение следует…