N-Queens без рекурсии (но с одним goto)

По сравнению с рекурсивной версией, например, в Rosetta, она на 5-10% быстрее и использует на 50% меньше инструкций (для N = 12).

Единственная проблема — это goto. Можно ли этого избежать без использования функции?

Два внешних цикла for мало что делают с точки зрения управления циклом. Но вот как я мог заставить его работать.

Есть ли более убедительная нерекурсивная версия? Я искал довольно много, и большинство из них рекурсивны и / или длиннее.

/* N-Queens, non-recursive, with goto */
#include <stdio.h>
//const int N = 8;  //92 solutions
const int N = 12;   //14200 in 0.100 s

/* Print excluding last row, plus last col */
void pr_solution(int *bq, int col) {
    for (int i = 0; i < N - 1; i++)
        printf("%d:", bq[i]);
    printf("%dn", col);
}   
void init_board(int bq[], int v) {
    for (int i = 0; i < N; i++)
        bq[i] = v;
}
int main() {
    int bq[N];
    init_board(bq, -1); 
    int row, col, rd, old;
    int cnt = 0;
    for (row = 0; row >= 0;) {
        
        for (col = bq[row];;) {
            NEXT_col:
            if (++col == N) 
                bq[row--] = -1;
            else {
                for (rd = 1; rd <= row; rd++)
                    if ((old = bq[row-rd]) == col || old == col+rd || old == col-rd)
                        goto NEXT_col;
                if (row == N - 1) {
                    cnt++;
                    row--;
                    //pr_solution(bq, col); 
                }
                else  
                    bq[row++] = col;
            }
            break;
        }
    }
    printf("%d SOLUTIONS (%dx%d)n", cnt, N, N);
    return 0;
}

Единственная проблема — это переход. Можно ли этого избежать без использования функции?

Кандидат goto замена

    for (col = bq[row];;) {
        //NEXT_col: // Delete
        if (++col == N) 
            bq[row--] = -1;
        else {
            for (rd = 1; rd <= row; rd++)
                if ((old = bq[row-rd]) == col || old == col+rd || old == col-rd)
                    // goto NEXT_col;  // Delete
                    break; //ADD
            if (rd <= row) continue; // ADD
            if (row == N - 1) {
                cnt++;
                row--;
                //pr_solution(bq, col); 
            }
            else  
                bq[row++] = col;
        }
        break;
    }

if (rd <= row) continue; пользуется тем, что for (col = bq[row];;) не хватает теста и приращения.

Есть ли более убедительная нерекурсивная версия?

Я бы переписал цикл (возможно, Государственный аппарат) — нужно время, чтобы подумать.

Позже:

Написанный код довольно плотный. А очень хорошо простое нерекурсивное решение.

Тем не менее (рискуя вызвать гнев OP) не хватает ясности, что излишне затрудняет оптимизацию.

В стиль использует краткие имена переменных, например rd и bq которые не очень хорошо передают их смысл. Как будто короткие имена переменных ускоряют код (это не так). init_board() инициализирует не плату, а отдельное измерение данных. Используйте более значимые имена.

Использование неполного for петли вроде for (col = bq[row];;) похоже на кодовую цель гольфа, чем на более ясную col = bq[row]; while (1).

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

Создание экземпляров локальной переменной поможет увидеть их ограниченное влияние.

Для ясности используйте {} даже для однострочных блоков.

Рассматривайте прямоугольники, а не только квадраты. Он добавляет ясности коду и предлагает другие исследования для возможной оптимизации.

Некоторые другие идеи в коде ниже.

Первый круглый разрез:

int main(void) {
  for (int N = 1; N <= 8; N++) {
    const int ROW_N = N;
    const int COL_N = ROW_N;
    int queen_column[ROW_N];
    init_queen_column(ROW_N, queen_column, -1);
    long long count = 0;
    int parity[2] = { 0,0};
    int row = 0;
    while (row >= 0) {
      int col = queen_column[row];
      while (1) {
        if (++col == COL_N) {
          queen_column[row--] = -1;
        } else {
          int row_offset;
          for (row_offset = 1; row_offset <= row; row_offset++) {
            int old = queen_column[row - row_offset];
            int diff = old - col;
            if ((diff == 0) || diff == row_offset || diff == -row_offset) {
              break;
            }
          }
          if (row_offset <= row) { // From early break above
            continue; // ADD
          }
          if (row == ROW_N - 1) {
            count++;
            // print_solution(ROW_N, queen_column, col); // Print, then change state.
            row--;
          } else {
            parity[(row ^ col)&1]++; // Count parity for later optimization (stub code)
            queen_column[row++] = col;
          }
        }
        break;
      }
    }
    printf("%lld SOLUTIONS (%dx%d)n", count, ROW_N, COL_N);
  }
  return 0;
}
1 SOLUTIONS (1x1)
0 SOLUTIONS (2x2)
0 SOLUTIONS (3x3)
2 SOLUTIONS (4x4)
10 SOLUTIONS (5x5)
4 SOLUTIONS (6x6)
40 SOLUTIONS (7x7)
92 SOLUTIONS (8x8)

Другая идея, чтобы ускорить процесс

1. Следите за счетом размещения ферзя на черных (и / или белых) полях. Как только это превысит половину N, время расслабиться, поскольку все последующие итерации вперед потерпят неудачу.

2. Ищите шаблоны. Пример: симметрия. Решение, которое начинается с первого ферзя на row[0] будет столько решений, сколько row[N-1]. Похоже, время выполнения можно как-то сократить вдвое.

void pr_solution(int *bq, int col) {
void init_board(int bq[], int v) {

Их можно объявить с помощью static связь.

int main() {

Предпочитаю int main(void) сделать это объявление прототипом (не принимает аргументы, а не неопределенные аргументы).

int row, col, rd, old;

Все они могли иметь меньший охват. Например

for (int row = 0; row >= 0;) {

Всегда лучше объявлять и инициализировать одновременно, а не оставлять окно, в котором переменная существует, но не инициализирована.

                //pr_solution(bq, col);

Закомментированный код может стать непоследовательным. Либо удалите его, либо раскомментируйте (и, возможно, предоставьте аргумент командной строки для включения / отключения).

Второй цикл for делает так мало, что его можно заменить меткой, ЕСЛИ вы придерживаетесь goto:

for (row = 0; row >= 0;) {
    col = bq[row];
    NEXT_col:
    if (++col == N)
        bq[row--] = -1;
    else {
        for (rd = 1; rd <= row; rd++)
            if ((old = bq[row-rd]) == col || abs(old - col) == rd)
                goto NEXT_col;
        if (row == N - 1) {
            cnt++;
            row--;
        }
        else
            bq[row++] = col;
    }
}

Больше не надо break в конце. Это было разное то, что сделал цикл for: сломался в конце. Первым делом было: на него набросились continue (или же goto).

Сейчас я вполне доволен — это все еще «goto», но теперь это имеет смысл.

Как говорится об этой проблеме N-Queens: простой, но не тривиальный.

Оказывается, отслеживать угрозы в 2D-массиве — дело вдвое быстрее. Теперь вместо того, чтобы увеличивать столбец и проверять позже, следующий столбец находит функция.

Основной цикл освобождается от проверки по диагонали. Но теперь он должен добавлять, а также удалять угрозы при перемещении ферзя.

/* Returns zeroed n*n array */
int **init_threats(int n) {
    int r;
    int **t2d = malloc(n * sizeof*t2d);
    for (r = 0; r < n; r++)
        t2d[r] = calloc(n, sizeof**t2d);
    return t2d;
}
/* Only needs a row from "threats[][]" */
int next_free(int *r, int after) {
    for (int c = after + 1; c < N; c++)
        if (r[c] == 0)
            return c;
    return -1;
}
/* Cumulative threats - they can overlap */
void change_thr(int chg, int r, int c, int **threats) {
    int tr, diag;
    for (tr = r + 1; tr < N; tr++) { 
        threats[tr][c] += chg;
        diag = c + tr - r;
        if (diag < N)
            threats[tr][diag] += chg;  
        diag = c - (tr - r);
        if (diag >= 0)
            threats[tr][diag] += chg;  
    }
}
int main() {
    int queen[N];
    init_board(queen, -1);  
    int **threats = init_threats(N);
    int row = 0, cnt = 0;
    int col;
    while (row >= 0) {
        col = next_free(threats[row], queen[row]);
        if (row == N - 1) { 
            if (col >= 0) 
                cnt++;
            row--;
        } else {
            if (queen[row] >= 0)
                change_thr(-1, row, queen[row], threats);   
            if (col >= 0) {
                change_thr(1, row, col, threats);   
                queen[row++] = col;
            } else 
                queen[row--] = -1;
        }
    }   
    printf("%d SOLUTIONS (%d-Queens)n", cnt, N);
    return 0;
}