91 lines
2 KiB
Text
91 lines
2 KiB
Text
//
|
|
// N-queens problem solver
|
|
//
|
|
// Using FutureBasic 7.0.34
|
|
// August 2025, R.W.
|
|
//
|
|
// Solves 8 queens on 8 x 8 board. You
|
|
// can adjust the number of queens and
|
|
// board size in the first two lines.
|
|
//
|
|
// Program will calculate the number of solutions.
|
|
// If the flag "detail" is set to _True, the
|
|
// placement of the queens would be indicated.
|
|
|
|
|
|
Int BoardSize = 8 // 8x8 board
|
|
Int board(8, 8) //
|
|
Int solution = 0 // solution count
|
|
Boolean detail // whether detailed solution is desired
|
|
|
|
// Check if placing a queen at (row, col) is safe
|
|
|
|
local fn Safe(row as int, col as int) as Boolean
|
|
dim i as int, j as int
|
|
|
|
// Check column
|
|
for i = 1 to row - 1
|
|
if board(i, col) = 1 then exit fn = _false
|
|
next
|
|
|
|
// Check upper-left diagonal
|
|
i = row - 1 : j = col - 1
|
|
while (i >= 1) and (j >= 1)
|
|
if board(i, j) = 1 then exit fn = _false
|
|
i-- : j--
|
|
wend
|
|
|
|
// Check upper-right diagonal
|
|
i = row - 1 : j = col + 1
|
|
while (i >= 1) and (j <= BoardSize)
|
|
if board(i, j) = 1 then exit fn = _false
|
|
i-- : j++
|
|
wend
|
|
end fn = _True
|
|
|
|
// Recursive backtracking solver
|
|
local fn Solve(row as int, wantDetail as boolean)
|
|
dim col as int
|
|
|
|
if row > BoardSize
|
|
// Found one solution — print it
|
|
dim r as int, c as int
|
|
solution++
|
|
if wantDetail
|
|
for r = 1 to BoardSize
|
|
for c = 1 to BoardSize
|
|
if board(r, c) == 1
|
|
print chr$(asc("a") + r - 1); c; " ";
|
|
end if
|
|
next
|
|
next
|
|
print
|
|
end if
|
|
exit fn
|
|
end if
|
|
|
|
for col = 1 to BoardSize
|
|
if fn Safe(row, col)
|
|
board(row, col) = 1
|
|
fn Solve(row + 1,detail)
|
|
board(row, col) = 0
|
|
end if
|
|
next
|
|
end fn
|
|
|
|
window 1,@"N-queens problem"
|
|
|
|
detail = _True // we want board placement detail
|
|
|
|
if detail
|
|
print@
|
|
print @"Detailed placements for chessboard of size ";¬
|
|
BoardSize; @"x"; BoardSize
|
|
print@
|
|
end if
|
|
|
|
fn Solve(1,detail)
|
|
print@
|
|
print @"There are ";solution;@" solutions for "; BoardSize; @"x"; BoardSize;@" board."
|
|
|
|
handleEvents
|