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]")
Huh?
#!/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..
Hi 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
what’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) [] []
[…] Curious Programmer wrote C++ and OCaml solutions. According to the blog, “the fixed C++ completes 100 solutions in 9.5 […]