Last modified on 24 May 2014, at 17:00

Algorithm Implementation/Miscellaneous/N-Queens

The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard, where solutions exist only for n = 1 or n ≥ 4.

C++Edit

A fully commented backtracking implementation in C++

#include <iostream>
 
using namespace std;
 
const int N = 5;
int position[N];
 
// Check if a position is safe
bool isSafe(int queen_number, int row_position)
{
	// Check each queen before this one
	for (int i = 0; i < queen_number; i++)
	{
		// Get another queen's row_position
		int other_row_pos = position[i];
 
		// Now check if they're in the same row or diagonals
		if (other_row_pos == row_position || // Same row
			other_row_pos == row_position - (queen_number - i) || // Same diagonal
			other_row_pos == row_position + (queen_number - i))   // Same diagonal
			return false;
	}
	return true;
}
 
 
// Recursively generate a tuple like [0 0 0 0], then [0 0 0 1] then etc...
void solve(int k)
{
	if (k == N) // We placed N-1 queens (0 included), problem solved!
	{
		// Solution found!
		cout << "Solution: ";
		for (int i = 0; i < N; i++)
			cout << position[i] << " ";
		cout << endl;
	}
	else
	{
		for (int i = 0; i < N; i++) // Generate ALL combinations
		{
			// Before putting a queen (the k-th queen) into a row, test it for safeness
			if (isSafe(k, i))
			{
				position[k] = i;
				// Place another queen
				solve(k + 1);
			}
		}
	}
}
 
int main()
{
	solve(0);
 
	return 0;
}

CEdit

A backtracking depth-first search (DFS) solution in C:

#include <stdio.h>
 
int
is_safe(int rows[8], int x, int y)  
{
    int i;
 
    if (y == 0)
            return 1;
    for (i=0; i < y; ++i) {
       if (rows[i] == x || rows[i] == x + y - i || rows[i] == x - y +i)
            return 0;
    }
 
    return 1;
}
 
void
putboard(int rows[8])  
{
    static int s = 0;
    int x, y;
 
    printf("\nSolution #%d:\n---------------------------------\n", ++s);
    for (y=0; y < 8; ++y) {
        for (x=0; x < 8; ++x)
            printf(x == rows[y] ? "| Q " : "|   ");
        printf("|\n---------------------------------\n");
    }
}
 
void
eight_queens_helper(int rows[8], int y)
{
    int x;
 
    for (x=0; x < 8; ++x) {
        if (is_safe(rows, x, y)) {
            rows[y] = x;
            if (y == 7)
              putboard(rows);
            else
              eight_queens_helper(rows, y+1);
        }
    }
}
 
int
main()
{
    int rows[8];
 
    eight_queens_helper(rows, 0);
 
    return 0;
}

HaskellEdit

import Control.Monad
 
queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n]
safe x [] n = True
safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
 
main = mapM_ print $ queens 8

PythonEdit

def queensproblem(rows, columns):
    solutions = [[]]
    for row in range(rows):
        solutions = add_one_queen(row, columns, solutions)
    return solutions
 
def add_one_queen(new_row, columns, prev_solutions):
    return [solution + [new_column]
            for solution in prev_solutions
            for new_column in range(columns)
            if no_conflict(new_row, new_column, solution)]
 
def no_conflict(new_row, new_column, solution):
    return all(solution[row]       != new_column           and
               solution[row] + row != new_column + new_row and
               solution[row] - row != new_column - new_row
               for row in range(new_row))
 
for solution in queensproblem(8, 8):
    print(solution)

MathematicaEdit

Invalid language.

You need to specify a language like this: <source lang="html4strict">...</source>

Supported languages for syntax highlighting:

4cs, 6502acme, 6502kickass, 6502tasm, 68000devpac, abap, actionscript, actionscript3, ada, algol68, apache, applescript, apt_sources, arm, asm, asp, asymptote, autoconf, autohotkey, autoit, avisynth, awk, bascomavr, bash, basic4gl, bf, bibtex, blitzbasic, bnf, boo, c, c_loadrunner, c_mac, caddcl, cadlisp, cfdg, cfm, chaiscript, cil, clojure, cmake, cobol, coffeescript, cpp, cpp-qt, csharp, css, cuesheet, d, dcl, dcpu16, dcs, delphi, diff, div, dos, dot, e, ecmascript, eiffel, email, epc, erlang, euphoria, f1, falcon, fo, fortran, freebasic, freeswitch, fsharp, gambas, gdb, genero, genie, gettext, glsl, gml, gnuplot, go, groovy, gwbasic, haskell, haxe, hicest, hq9plus, html4strict, html5, icon, idl, ini, inno, intercal, io, j, java, java5, javascript, jquery, kixtart, klonec, klonecpp, latex, lb, ldif, lisp, llvm, locobasic, logtalk, lolcode, lotusformulas, lotusscript, lscript, lsl2, lua, m68k, magiksf, make, mapbasic, matlab, mirc, mmix, modula2, modula3, mpasm, mxml, mysql, nagios, netrexx, newlisp, nsis, oberon2, objc, objeck, ocaml, ocaml-brief, octave, oobas, oorexx, oracle11, oracle8, oxygene, oz, parasail, parigp, pascal, pcre, per, perl, perl6, pf, php, php-brief, pic16, pike, pixelbender, pli, plsql, postgresql, povray, powerbuilder, powershell, proftpd, progress, prolog, properties, providex, purebasic, pycon, pys60, python, q, qbasic, rails, rebol, reg, rexx, robots, rpmspec, rsplus, ruby, sas, scala, scheme, scilab, sdlbasic, smalltalk, smarty, spark, sparql, sql, stonescript, systemverilog, tcl, teraterm, text, thinbasic, tsql, typoscript, unicon, upc, urbi, uscript, vala, vb, vbnet, vedit, verilog, vhdl, vim, visualfoxpro, visualprolog, whitespace, whois, winbatch, xbasic, xml, xorg_conf, xpp, yaml, z80, zxbasic


dispSol[sol_] := sol /. {1 -> "Q" , 0 -> "-"} // Grid

solveNqueens[n_] := 
 Module[{c, m, b, vars}, c = cqueens[n]; m = mqueens[n]; 
  vars = mqueens2[n]; b = bqueens[Length[m]]; 
  Partition[LinearProgramming[c, m, b, vars, Integers], n]]

cqueens[n_] := Table[-1, {i, n^2}]

bqueens[l_] := Table[{1, -1}, {i, l}]

mqueens2[n_] := Table[{0, 1}, {i, n^2}]

mqueens[n_] := 
 Module[{t, t2, t3, t4}, t = mqueensh[n]; t2 = Append[t, mqueensv[n]];
   t3 = Append[t2, mqueensd[n]]; t4 = Append[t3, mqueensdm[n]]; 
  Partition[Flatten[t4], n^2]]

mqueensh[n_] := 
 Module[{t}, t = Table[0, {i, n}, {j, n^2}]; 
  For[i = 1, i <= n, i++, 
   For[j = 1, j <= n, j++, t[[i, ((i - 1)*n) + j]] = 1]]; t]

mqueensv[n_] := 
 Module[{t}, t = Table[0, {i, n}, {j, n^2}]; 
  For[i = 1, i <= n, i++, 
   For[j = 1, j <= n, j++, t[[j, ((i - 1)*n) + j]] = 1]]; t]

mqueensd[n_] := 
 Module[{t}, t = Table[0, {i, (2*n) - 1}, {j, n^2}]; 
  For[k = 2, k <= 2 n, k++, 
   For[i = 1, i <= n, i++, 
    For[j = 1, j <= n, j++, 
     If[i + j == k, t[[k - 1, ((i - 1)*n) + j]] = 1]]]]; t]

mqueensdm[n_] := 
 Module[{t}, t = Table[0, {i, Sum[1, {i, 1 - n, n - 1}]}, {j, n^2}]; 
  For[k = 1 - n, k <= n - 1, k++, 
   For[i = 1, i <= n, i++, 
    For[j = 1, j <= n, j++, 
     If[i == j - k, t[[k + n, ((i - 1)*n) + j]] = 1]]]]; t]