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

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

Решать будем методом перебора. Ну, не полного перебора, немного включим голову.

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

Таких будет два - горизонталь и диагональ. Для удобства клеточки буду нумеровать с 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 минуты.

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

tags: #bash © by Tagd Tagd
—
🔔 @bashdays➡️ @gitgate