The 8-Queens problem backtracking, the OOP-style
(This code is an ocaml translation of a Little Smalltalk code example, unknown original author)
The 8-queens problem is to place 8 queens on a regular chessboard without any threatening possible.
let null_queen =
object
method first = false
method next = false
method check (x:int) (y:int) = false
method print = print_newline ()
end
class queen column (neighbor:queen) =
object (self)
val mutable row = 1
method check r c =
let diff = c - column in
(row = r) ||
(row + diff = r) || (row - diff = r) ||
neighbor#check r c
method private test =
try
while neighbor#check row column do
if not self#advance then raise Exit
done;
true
with
| Exit -> false
method first =
ignore(neighbor#first);
row <- 1;
self#test
method next =
self#advance && self#test
method private advance =
if row = 8 then
(if neighbor#next then (row <- 1; true) else false)
else (row <- row + 1; true)
method print : unit =
print_int row; print_char ' '; neighbor#print
end
let () =
let last = ref null_queen in
for i = 1 to 8 do
last := new queen i !last
done;
if !last#first then begin
!last#print;
while !last#next do
!last#print
done
end else
print_string "Zero solution."
This program prints all 8-Queens 92 solutions.