Programming implementation of eight queens

Eight queens problem description

Eight queens question , It's an old and famous question , It's a typical case of backtracking algorithm . The problem is that international chess player Max · Bethel in 1848 year
Put forward ： stay 8×8 GE's chess set eight queens , Make it impossible to attack each other , namely ： No two Queens can be in the same line 、 On the same column or slash , Ask how many kinds of pendulum

The idea of backtracking algorithm

The eight queens problem needs to be tried if the exhaustive method is used 88=16,777,216 In this case . Put a queen in each column , You can put it on the 1 That's ok , The first 2 That's ok ,……, Until the first 8 That's ok . At the time of exhaustion, all queens are placed in the first 1 The plan of the line begins , Test whether queens will attack each other . If it will , List H The queen moved a space , Verify the next solution . Move to the bottom and “ carry ” To column G The queen moved a space , Column H The queen of tried all again 8 That's ok . This method is very inefficient , Because it doesn't adjust where there is conflict , Instead, blindly enumerate all possible solutions in a given order .
Backtracking algorithm is better than exhaustive method . Column A After the first line , Column B The queen on the first line has clashed . There is no need to continue to put columns at this time C Queen of , Instead, adjust the columns B Queen to the second line , Continue the conflict and put the third line , No conflict before entering the column C. In this way, the following A to E Queen of . Turn each queen horizontally to the right 、 The point of oblique attack is marked with a fork , Discovery column F The queen has nowhere to live . This goes back to the column E Queen of , Change its position from 4 Line is adjusted to 8 That's ok , Enter the column F, Found that the queen still had nowhere to live , Retrace the column again E. Column at this time E All cases have been enumerated , Go back to column D, Change it from 2 Move the line to 7 That's ok , Then enter the column E continue . According to this algorithm flow, the final result is as shown in the figure 3 The solution shown , Success put down in the chessboard 8 individual “ Peaceful coexistence ” Queen of . Continue to find all the solutions 92 individual .
The principle of backtracking algorithm to solve the eight queens problem is ： There is conflict, conflict resolution , No conflict, go ahead , There is no way to go back , At the end is the answer . In order to speed up the judgment of whether there is conflict , You can create a flag array for each row and each diagonal in both directions . Put down a new queen as a sign , Move an old queen back to clear the sign .

Programming to realize

Haskall

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

GO

package main
import "fmt"
func main() {
     
    var balance = [8]int{
    0, 0, 0, 0, 0, 0, 0, 0} 
    queen(balance, 0)
}
func queen(a [8]int, cur int) {
    
    if cur == len(a) {
    
        fmt.Print(a)  
        fmt.Println()  
        return
    } 
    for i := 0; i < len(a); i++ {
      
        a[cur] = i  
        flag := true  
        for j := 0; j < cur; j++ {
       
            ab := i - a[j]   
            temp := 0   
            if ab > 0 {
    
                temp = ab   
            } else {
        
                temp = -ab
            }
            if a[j] == i || temp == cur-j {
    
                flag = false    
                break  
            }
         }  
         if flag {
       
             queen(a, cur+1)  
         }
    }
}

JS

function queen(a, cur) {
    
    if (cur==a.length) {
     console.log(a); return; }
    for (var i = 0; i < a.length; i++) {
    
        a[cur] = i;
        var flag = true;
        for (var j = 0; j < cur; j++) {
    
            var ab = i - a[j];
            if (a[j]==i||(ab>0?ab:-ab)==cur-j) {
     flag=false; break };
        };
        if (flag) {
     queen(a,cur+1); }
    };
};
queen([1,1,1,1,1,1,1,1],0);

C++

#include <iostream>
using namespace std;
 
const int N = 8;
int arr[10], total_cnt;
// arr Record each line (X) Queen's Y coordinate 
 
bool isPlaceOK(int *a, int n, int c) {
    
    for (int i = 1; i <= n - 1; ++i) {
    
        if (a[i] == c || a[i] - i == c - n || a[i] + i == c + n)
            return false;
        // Check whether the position can be put 
        //c Is the place to be placed 
        //a[i] == c If you put it in the same column ,false
        //a[i] -+ i = c -+ n  On the diagonal ,false
    }
    return true;
}
 
void printSol(int *a) {
    
    for (int i = 1; i <= N; ++i) {
     // Go through every line 
        for (int j = 1; j <= N; ++j) {
     // Traverse each column 
            cout << (a[i] == j ? "X" : "-") << " ";;
        } // If the queen of this row in the tag array is placed in j Location , The output X, Otherwise output -,
        // Separate... With spaces 
        cout << endl; // Output a new line for each line 
    }
    cout << endl; // Each set of data is separated by a newline 
}
 
void addQueen(int *a, int n) {
    
    if (n > N) {
     //n Stands for placing... From the first line 
        printSol(a);
        total_cnt++;
        return ;
    }
    for (int i = 1; i <= N; ++i) {
     //i From 1 Column to the first N Column traversal 
        if (isPlaceOK(a, n, i)) {
    
            a[n] = i; // If you can put , Just put the queen on the first n Xing di i Column 
            addQueen(a, n + 1);
        }
    }
 
}
 
int main() {
    
    addQueen(arr, 1);
    cout << "total: " << total_cnt << " solutions.\n";
    return 0;
}

Pascal

program queen; var a:array[1…8]of longint; // Record the row coordinates of the queen
b,c,d:array[-7…16]of longint; // That's ok , The upper right , The space occupying sign of the lower right slash m,ans:longint;
procedure queen(j:longint); var i:longint; begin
if j>8 then
begin
inc(ans); // Meet the conditions , Find a solution
exit;
end;
for i:=1 to 8 do// There are eight possibilities for each queen position
if(b[i]=0)and(c[i+j]=0)and(d[j-i]=0)then // If the position is not occupied, run
begin
a[j]:=i; // The queen is placed on this trip
b[i]:=1; // Occupy No i That's ok
c[i+j]:=1; // Occupy the upper right
d[j-i]:=1; // Occupy the lower right
queen(j+1); // recursive
b[i]:=0; // to flash back , Restore row placeholder
c[i+j]:=0; // to flash back , Restore the slant above （ The upper right ） Placeholder sign
d[j-i]:=0; /// to flash back , Restore the slope below （ The lower right ） Placeholder sign
end; end; begin // The main program
for m:=-7 to 16 do // The data is initialized to 0
begin
b[m]:=0; // The row data is initialized to 0
c[m]:=0; // The upper right data is initialized to 0
d[m]:=0; // The lower right data is initialized to 0
end;
ans:=0;
queen(1); // Start placing the first queen
writeln(ans); end.

Java

public class Queen {
    
    private int[] column; // Is there a queen in the same column ,1 Express 
    private int[] rup; // Is there a queen from top right to bottom left 
    private int[] lup; // Is there a queen from top left to bottom right 
    private int[] queen; // answer 
    private int num; // Answer number 
 
    public Queen() {
    
        column = new int[8+1];
        rup = new int[(2*8)+1];
        lup = new int[(2*8)+1];
        for (int i = 1; i <= 8; i++)
            column[i] = 0;
        for (int i = 1; i <= (2*8); i++)
            rup[i] = lup[i] = 0;  // The initial definition has no queen 
        queen = new int[8+1];
    }
 
    public void backtrack(int i) {
    
        if (i > 8) {
    
            showAnswer();
        } else {
    
            for (int j = 1; j <= 8; j++) {
    
                if ((column[j] == 0) && (rup[i+j] == 0) && (lup[i-j+8] == 0)) {
    
                    // No queen 
                    queen[i] = j; // Set to occupied 
                    column[j] = rup[i+j] = lup[i-j+8] = 1;
                    backtrack(i+1);  // Cycle call 
                    column[j] = rup[i+j] = lup[i-j+8] = 0;
                }
            }
        }
    }
 
    protected void showAnswer() {
    
        num++;
        System.out.println("\n answer " + num);
        for (int y = 1; y <= 8; y++) {
    
            for (int x = 1; x <= 8; x++) {
    
                if(queen[y]==x) {
    
                    System.out.print("Q");
                } else {
    
                    System.out.print(".");
                }
            }
            System.out.println();
        }
    }
 
    public static void main(String[] args) {
    
        Queen queen = new Queen();
        queen.backtrack(1);
    }
}

Erlang

-module(queen).
-export([printf/0, attack_range/2]).
-define(MaxQueen, 4).% Find all possible permutations of strings 
%perms([]) ->% [[]];
%perms(L) ->% [[H | T] || H <- L, T <- perms(L -- [H])].
perms([]) ->[[]];
perms(L) ->[[H | T] || H <- L, T <- perms(L -- [H]), attack_range(H,T) == []].printf() ->L = lists:seq(1, ?MaxQueen),io:format("~p~n", [?MaxQueen]),perms(L).
% Detect the numbers in the first row and the numbers in the next row %left Downward left detection %right Downward right detection 
attack_range(Queen, List) ->attack_range(Queen, left, List) ++ attack_range(Queen, right, List).attack_range(_, _, []) ->[];
attack_range(Queen, left, [H | _]) when Queen - 1 =:= H ->[H];
attack_range(Queen, right, [H | _]) when Queen + 1 =:= H ->[H];
 
attack_range(Queen, left, [_ | T]) ->attack_range(Queen - 1, left, T);attack_range(Queen, right, [_ | T]) ->attack_range(Queen + 1, right, T).

python

def queen(A, cur=0):
    if cur == len(A):
        print(A)
        return 0
    for col in range(len(A)):  #  Traverse all positions of the current line 
        A[cur] = col
        for row in range(cur):  #  Check whether the current position is relative 
            if A[row] == col or abs(col - A[row]) == cur - row:
                break
        else:  #  If the whole traversal is completed , It means that there is no restriction on the position 
            queen(A, cur+1)  #  Calculate the position of the next line 
queen([None]*8)

C#

using System;
using System.Collections.Generic;
namespace EightQueens_CSharp {
    
    public class EightQueens {
    
        private List<int[]> solutions;
        public List<int[]> GetSolutions(int queenCount) {
    
            solutions = new List<int[]>();
            List<int> queenList = new List<int>();
            for (int i = 0; i < queenCount; i++) {
    
                queenList.Add(0);
            }
            putQueen(queenCount, queenList, 0);
            printSolutions(solutions);
            return solutions;
        }
         
        private void putQueen(int queenCount, List<int> queenList, int nextY) {
    
            for (queenList[nextY] = 0; queenList[nextY] < queenCount; queenList[nextY]++) {
    
                if (checkConflict(queenList, nextY) == false) {
    
                    nextY++;
                    if (nextY < queenCount) {
    
                        putQueen(queenCount, queenList, nextY);
                    }
                    else {
    
                        solutions.Add(queenList.ToArray());
                        Console.WriteLine(string.Join(", ", queenList));
                    }
                    nextY--;
                }
            }
        }
         
        private bool checkConflict(List<int> queenList, int nextY) {
    
            for (int positionY = 0; positionY < nextY; positionY++) {
    
                if (Math.Abs(queenList[positionY] - queenList[nextY]) == Math.Abs(positionY - nextY) || queenList[positionY] == queenList[nextY]) {
    
                    return true;
                }
            }
            return false;
        }
         
        private void printSolutions(List<int[]> solutions) {
    
            int count = 0;
            foreach (var solution in solutions) {
    
                Console.WriteLine("Solution: {0}", count++);
                int queenCount = solution.Length;
                for (int i = 0; i < queenCount; i++) {
    
                    printLine(solution[i], queenCount);
                }
                Console.WriteLine("------------------");
            }
        }
         
        private void printLine(int pos, int width) {
    
            for (int i = 0; i < width; i++) {
    
                if (pos == i) {
    
                    Console.Write(" x");
                }
                else {
    
                    Console.Write(" .");
                }
            }
            Console.WriteLine();
        }
    }
}

Scheme

#lang racket (define (enumerate-interval low high) (cond ((> low high) null)
((= low high) (list high))
(else (cons low (enumerate-interval (+ 1 low) high)))))
(define (flatmap proc seq) (foldr append null (map proc seq)))
(define empty-board null)
(define (safe? test-column positions) (define (two-coordinate-safe? coordinate1 coordinate2)
(let ((row1 (row coordinate1))
(row2 (row coordinate2))
(col1 (column coordinate1))
(col2 (column coordinate2)))
(if (or (= row1 row2)
(= (abs (- row1 row2)) (abs (- col1 col2))))
#f
#t))) (let ((test-coordinate (get-coordinate-by-column test-column positions)))
(foldr (lambda (coordinate results)
(and (two-coordinate-safe? test-coordinate coordinate)
results))
#t
(remove test-coordinate positions))))

     (define (adjoin-position new-row new-column existing-positions)     (cons (make-coordinate new-row new-column)

existing-positions))

   (define (make-coordinate row column)     (list row column))   (define (row coordinate)     (car coordinate))   (define (column

coordinate) (cadr coordinate)) (define (get-coordinate-by-column
target-column coordinates) (cond ((null? coordinates) null)
((= target-column (column (car coordinates))) (car coordinates))
(else (get-coordinate-by-column target-column (cdr coordinates)))))

 (define (queens board-size)     (define (queen-cols k) 
 (if (= k 0) 
     (list empty-board) 
     (filter 
      (lambda (positions) (safe? k positions)) 
      (flatmap 
       (lambda (rest-of-queens) 
         (map (lambda (new-row) 
                (adjoin-position 
                 new-row k rest-of-queens)) 
              (enumerate-interval 1 board-size))) 
       (queen-cols (- k 1))))))     (queen-cols board-size))   ; knock （queens 8）, Get operation results , Each coordinate , The first representative line , The second represents the column  ; Pure recursive thinking , Running environment racket 7.5

Lua

 local num = 0;
    local t = socket.gettime();
    local function searchQueen(tab)
        local data = clone(tab)
        if data[2] == #data[1] then
            num = num + 1
            -- return print("result..", num, " ==> ", table.concat(data[1], ","))
            return
        end
        data[2] = data[2] + 1;
        for i = 1, 8 do
            data[1][data[2]] = i
            local bOk = true
            for j = 1, data[2]-1 do
                if (data[1][j] == i) or (math.abs(i - data[1][j]) == data[2] - j) then
                    bOk = false
                    break
                end
            end
            if bOk then
                searchQueen(data)
            end
        end
    end
    searchQueen({
    {
    0,0,0,0,0,0,0,0}, 0})
    print("EIGHT QUEEN result == ", num, "\ntime cost == ", socket.gettime() - t)