Jon Harrop spotted that the Ocaml code was calling is_threatened 64515 times compared to the C++ calling is_threatened just 1915 times. I eventually spotted the bug in the C++ code: next_valid_posn was not correctly iterating through the x positions. The fix was straight-forward:

Posn next_valid_posn(const Posn& p) const { for (int y = p.y_; y < size_; y++) { int initX = (y == p.y_) ? (p.x_ + 1) : 0; for (int x = initX; x < size_; x++) { if (ref(x, y) == Safe) { return Posn(x, y); } } } return Posn(-1, -1); }

and now the C++ and Ocaml are much more closely matched. The fixed C++ completes 100 solutions in 9.5 seconds and the Ocaml completes 100 solutions in 19.3 seconds.

Andrej Bauer on the Ocaml mailing list came up with an attractive translation from my C++ which duplicates the bug of not covering all of the x positions. I’ve attached it below.

Thanks for the help to everyone on the Ocaml mailing list.

(* Andrej Bauer's solution *) type square = Qu | Safe | At (* A board is an array of arrays of squares *) type board = square array array type posn = int * int let string_of_square = function | Qu -> "Qu" | Safe -> "#f" | At -> "At" let init_pos = (0,0) let get board (x,y) = board.(y).(x) let display board = Array.iter (fun row -> Array.iter (fun square -> print_string (string_of_square square ^ " ")) row ; print_newline () ) board let build size f = Array.init size (fun y -> Array.init size (fun x -> f (x,y))) let is_threatened (x1,y1) (x2,y2) = x1 = x2 || y1 = y2 || (x2 - x1) = (y2 - y1) || (x1 - y2) = (x2 - y1) let add_queen board p = build (Array.length board) (fun q -> if q = p then Qu else match get board q with | Safe when is_threatened q p -> At | square -> square) exception No_solution (* This function is the equivalent of Board::placement. *) let rec solve board p rem = let size = Array.length board in let next_posn (px,_) (x,y) = if x + 1 < size then (x+1, y) else if y + 1 < size then (px, y+1) else raise No_solution in let next_valid_posn p = let rec loop q = match get board q with | Safe -> q | _ -> loop (next_posn p q) in loop p in if rem = 0 then board else let p' = next_valid_posn p in try solve (add_queen board p') init_pos (rem-1) with No_solution -> solve board (next_posn p p') rem let main = try let size = int_of_string Sys.argv.(1) in let times = int_of_string Sys.argv.(2) in let empty_board = build size (fun _ -> Safe) in for i = 2 to times do ignore (solve empty_board (0,0) 8 ) done ; display (solve empty_board (0,0) 8 ) with | No_solution -> print_endline "No solution." | _ -> print_endline ("Usage: " ^ Sys.argv.(0) ^ " [size] [times]")

on January 2, 2007 at 11:19joe bloggHuh?

on January 2, 2007 at 11:21Harshad Joshi#!/bin/env python

“”” General solution to the 8 queens puzzle.

“””

class queen:

“”” A queen on a chess board.

“””

def __init__(self, row, col):

self.row, self.col = row, col

def __str__(self):

return “(%d, %d)” % (self.row, self.col)

def safe_from(self, queens):

“”” Is this queen safe from the list of queens?

“””

for queen in queens:

if self.attacked_by(queen):

return False

return True

def attacked_by(self, queen):

“”” Is this queen attacked by the input queen?

“””

r, c = self.row, self.col

qr, qc = queen.row, queen.col

def same_row():

return r == qr

def same_column():

return c == qc

def same_diagonal():

return r + c == qr + qc or r – c == qr – qc

return same_row() or same_column() or same_diagonal()

def queens_puzzle(board_size):

“”” Generate solutions to the Queens puzzle for the input board size.

“””

def queen_columns(cols):

if cols == 0:

yield list()

else:

cols -= 1

for queens in queen_columns(cols):

for row in range(board_size):

new_queen = queen(row, cols)

if new_queen.safe_from(queens):

yield queens + [new_queen]

for queens in queen_columns(board_size):

yield queens

def outer_join(s, seq):

return “%s%s%s” % (s, s.join(seq), s)

def print_solution(board_size, queens):

line = outer_join(“+”, “-” * board_size)

for row in range(board_size):

print line

print outer_join(“|”,

[” Q”[q.row == row] for q in queens])

print line

print

try:

print “””\

Queens puzzle solver.

Puts N chess queens on an N by N chessboard such that none of

them is able to capture any other.

At the prompt, enter the board size or Q to quit.

“””

while True:

board_size = int(raw_input(“board size (Q to quit)? “))

if board_size 16:

print (“That’s a tough one but I’ll try my best. ”

“Press CTRL-C to interrupt.”)

try:

solutions = 0

for solutions, queens in enumerate(queens_puzzle(board_size)):

print_solution(board_size, queens)

if solutions: solutions += 1 # Users count from 1, not 0

print “There %s %d solution%s to the %d Queen%s puzzle.\n” % (

solutions == 1 and “is” or “are”,

solutions, “s”[solutions==1:],

board_size,”s”[board_size==1:])

except KeyboardInterrupt:

print “Execution interrupted.”

except ValueError, v:

print “Bye for now!”

Try the above version too..

on January 3, 2007 at 07:03IanOHi Harshad,

Unfortunately, wordpress has destroyed your code by removing the white-space (and possibly mangling punctuation such as > and <). Even if it hadn’t, I believe the code is not similar to the original as it generates all solutions rather than back-tracking for a single solution so the benchmark would be invalid.

Ian

on January 24, 2007 at 20:51pietro abatewhat’s about this solution ?

let return x = [x]

let bind m f = List.flatten ( List.map f m )

let mzero = []

let mplus = List.append

let guard b = if b then return () else mzero

let rec select = function

|[] -> mzero

|a::x -> mplus (return (a,x)) (bind (select x) ( fun (b,x') -> return

(b,a::x') ))

let notin q l = not(List.mem q l)

let range n =

let rec aux i l =

if i = 0 then l else i::(aux (i-1) l)

in List.rev ( aux n [] )

let rec place i rs d1 d2 = match i with

|0 -> return []

|i ->

bind (select rs) (fun (q,rs') -> (* select one queen *)

let q1 = q - i in

let q2 = q + i in

bind (guard (notin q1 d1)) (fun r1 ->

bind (guard (notin q2 d2)) (fun r2 ->

bind (place (i-1) rs' (q1::d1) (q2::d2)) (fun qs ->

(return (q::qs))))))

`let queen n = place n (range n) [] []`

on September 14, 2008 at 12:40N-Queens Revisited: A Haskell Reply < Ha4[…] Curious Programmer wrote C++ and OCaml solutions. According to the blog, “the fixed C++ completes 100 solutions in 9.5 […]