$n$ -Queens Reloaded

Relevant wiki: Recursive Backtracking

An usual way to solve this problem is to back-track, i.e, keep placing amazons until there is a conflict. Each time there is a conflict, we return to our last known conflict state.

Here is the backtrack procedure to solve the standard problem where we are asked to place 8 queens in an 8 by 8 grid:

Here is a small functional solution inspired by the Haskell Wiki :

1
2
3
4
5
6
7
8
9

amazons :: Int -> [[Int]]
amazons n = map reverse $ amazons' n
    where amazons' 0       = [[]]
          amazons' k       = [q:qs | qs <- amazons' (k-1), q <- [1..n], isSafe q qs]
          isSafe   try qs = not (try `elem` qs || sameDiag try qs || knight try qs)
          sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs
          knight try qs = any (\(colDist,q) -> ((abs (try - q) == 2) && (colDist == 1)) || ((abs (try - q) == 1) && (colDist == 2))) $ zip [1..] qs

main = print (length.amazons) 12

Here is a backtracking solution in Racket (just for making the this list of solutions more varied :-)). The foundation of this code is based upon Exercise 2.42 in SICP .

#lang racket

(define (enumerate-interval low high step)
  (stream->list (in-range low (+ high 1) step)))

(define (flatmap proc seq)
  (foldl append '() (map proc seq)))

(define (amazons board-size)
  (define (amazon-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
           (lambda (rest-of-amazons)
             (map (lambda (new-row) (adjoin-position new-row k rest-of-amazons))
                  (enumerate-interval 1 board-size 1)))
           (amazon-cols (- k 1))))))
  (amazon-cols board-size))

(define empty-board '())

(define (adjoin-position row col positions)
  (cons (list row col) positions))

(define (safe? new-col positions)
  (define (under-attack? row col new-row)
    (and (not (= col new-col))                   ; exclude self test
         (or (= (+ row col) (+ new-row new-col)) ; down diagonal test
             (= (- row col) (- new-row new-col)) ; up diaginal test
             (= row new-row)                     ; row test
             (and                                ; test for all possible knight steps
              (= (+ row 2) new-row)
              (= (+ col 1) new-col))
             (and
              (= (+ row 1) new-row)
              (= (+ col 2) new-col))
             (and
              (= (- row 2) new-row)
              (= (+ col 1) new-col))
             (and
              (= (- row 1) new-row)
              (= (+ col 2) new-col))
             (and
              (= row (+ new-row 2))
              (= col (- new-col 1)))
             (and
              (= row (+ new-row 1))
              (= col (- new-col 2)))
             (and
              (= row (- new-row 2))
              (= col (+ new-col 1)))
             (and
              (= row (- new-row 1))
              (= col (- new-col 2))))))
  (let ((new-row (caar (filter (lambda (position) (= (cadr position) new-col)) positions))))
    (null? (filter (lambda (position) (under-attack? (car position) (cadr position) new-row)) positions))))

(length (amazons 12))

A Python solution with some user-friendly names. It also prints all the paths.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

from typing import List, Tuple
from copy import deepcopy


class NQueens:

    def __init__(self, _number_of_queens: int):
        self._number_of_queens = _number_of_queens
        self._solutions = []

    def find_all_solutions(self):
        self._solutions = []

        for column in range(self._number_of_queens):
            # initiate the board by placing 1 queen in the first row
            # for every column, we might have a solution
            _solution = [(0, column)]

            # Solve for next row
            self.solve(_solution, 1, self._number_of_queens - 1)

        return self._solutions

    def print_all_solutions_neatly(self):
        _all_solutions = self.find_all_solutions()
        print(f'Number of solutions: {len(_all_solutions)}')

        for _solution in _all_solutions:
            _board = [[0 for _ in range(self._number_of_queens)] for _ in range(self._number_of_queens)]

            for __row, _col in _solution:
                _board[__row][_col] = 1

            print('*' * 40)
            for _row in _board:
                print(' '.join(map(str, _row)))
            print('*' * 40)

    def solve(self, _solution: List[Tuple[int, int]], _row: int, _queens_remaining: int):
        if _queens_remaining == 0:
            self._solutions.append(deepcopy(_solution))

        for _col in range(0, self._number_of_queens):
            _next_queen_position = (_row, _col)

            # try every column value for the specified row and if that is a valid spot, use
            # that spot and invoke the solve() method recursively to solve for next row
            if NQueens.is_valid_solution(_solution, _next_queen_position):
                _solution.append((_row, _col))
                self.solve(_solution, _row + 1, _queens_remaining - 1)

                # backtrack
                _solution.pop()

    @classmethod
    def is_valid_solution(cls, _solution: List[Tuple[int, int]], position: Tuple[int, int]):
        _x, _y = position

        for _already_x, _already_y in _solution:
            # in same row
            if _already_x == _x:
                return False

            # in same column
            if _already_y == _y:
                return False

            # on same diagonal
            if abs(_already_y - _y) == abs(_already_x - _x):
                return False

            # another piece within 3 blocks
            if abs(_already_y - _y) < 3 and abs(_already_x - _x) < 3:
                return False

        return True

NQueens(12).print_all_solutions_neatly()

C++ Solution using backtracking :

#include<bits/stdc++.h>
    using namespace std;

    int cnt;

    int dirX[] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dirY[] = {2, 1, -1, -2, -2, -1, 1, 2};

    //checking for knight like move
    bool canPlaceH(char board[][100],int row,int col,int n)
    {
        for(int i = 0; i < 8; i++)
        {
            if(row + dirX[i] >= 0 && row + dirX[i] < n && col + dirY[i] >= 0 && col + dirY[i] < n && board[row + dirX[i]][col + dirY[i]] == 'Q')
                return false;
        }
        return true;
    }

    //checking for queen like move
    bool canPlaceQ(char board[][100],int row,int col,int n)
    {
        for(int i=0;i<n;i++){
            if(board[row][i]=='Q'){
                return false;
            }
        }

        for(int i=0;i<n;i++){
            if(board[i][col]=='Q'){
                return false;
            }
        }
        // Diagonals
        //Top Left
        int i=row,j=col;
        while(i>=0&&j>=0)
        {
            if(board[i][j]=='Q')
                return false;
            i--;
            j--;
        }
        //Top Right
        i=row,j=col;
        while(i>=0 && j<n)
        {
            if(board[i][j]=='Q')
                return false;
            i--;
            j++;
        }
        return true;
    }

    void solveNAmazon(char board[][100],int n,int row)
    {
        if(row == n)
        {
            cnt++;
            return;
        }
        //Rec Case
        //Try to place the amazon in the current row
        for(int pos = 0; pos < n; pos++)
        {
            if(canPlaceQ(board,row,pos,n) && canPlaceH(board, row, pos, n))
            {
                board[row][pos]='Q';
                solveNAmazon(board,n,row+1);
                board[row][pos]='.';    //Backtrack
            }
        }
    }

    int main()
    {
        char board[100][100];
        int n = 12;

        cnt = 0;

        for(int x=0;x<n;x++){
            for(int y=0;y<n;y++){
                board[x][y]='.';
            }
        }
        solveNAmazon(board,n,0);
        cout << cnt << endl;
        return 0;
    }