65 lines
1.5 KiB
Plaintext
65 lines
1.5 KiB
Plaintext
DOCU The N Queens Problem:
|
|
DOCU Place N Queens on an NxN chess board
|
|
DOCU such that they don't threaten each other.
|
|
|
|
N = 8 // try some other sizes
|
|
|
|
sub threat(q1r, q1c, q2r, q2c)
|
|
// do two queens threaten each other?
|
|
|
|
if q1c = q2c then return true
|
|
elsif (q1r - q1c) = (q2r - q2c) then return true
|
|
elsif (q1r + q1c) = (q2r + q2c) then return true
|
|
elsif q1r = q2r then return true
|
|
else return false
|
|
end if
|
|
end sub
|
|
|
|
sub conflict(r, c, queens$)
|
|
// Would square p cause a conflict with other queens on board so far?
|
|
local r2, c2
|
|
|
|
for i = 1 to len(queens$) step 2
|
|
r2 = val(mid$(queens$,i,1))
|
|
c2 = val(mid$(queens$,i+1,1))
|
|
if threat(r, c, r2, c2) then
|
|
return true
|
|
end if
|
|
next i
|
|
return false
|
|
end sub
|
|
|
|
sub print_board(queens$)
|
|
// print a solution, showing the Queens on the board
|
|
local k$
|
|
|
|
print at(1, 1);
|
|
print "Solution #", soln, "\n\n ";
|
|
for c = asc("a") to (asc("a") + N - 1)
|
|
print chr$(c)," ";
|
|
next c
|
|
print
|
|
for r = 1 to N
|
|
print r using "##"," ";
|
|
for c = 1 to N
|
|
pos = instr(queens$, (str$(r)+str$(c)))
|
|
if pos and mod(pos, 2) then
|
|
queens$ = mid$(queens$,pos)
|
|
print "Q ";
|
|
else
|
|
print ". ";
|
|
end if
|
|
next c
|
|
print
|
|
next r
|
|
print "\nPress Enter. (q to quit) "
|
|
while(true)
|
|
k$ = inkey$
|
|
if lower$(k$) = "q" then
|
|
exit
|
|
elsif k$ = "enter" then
|
|
break
|
|
end if
|
|
wend
|
|
end sub
|