N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 09:07, 6 January 2024
, 4 months ago→{{header|Wren}}: Changed to Wren S/H
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 612:
=={{header|Julia}}==
Uses the Cbc optimizer (github.com/coin-or/Cbc) for its complementarity support.
<syntaxhighlight lang="
import Cbc
Line 778:
. . . . . . . . . .
</pre>
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="Nim">import std/[monotimes, sequtils, strformat]
type
Piece {.pure.} = enum Queen, Bishop, Knight
Solver = object
n: Natural
board: seq[seq[bool]]
diag1, diag2: seq[seq[int]]
diag1Lookup, diag2Lookup: seq[bool]
minCount: int
layout: string
func isAttacked(s: Solver; piece: Piece; row, col: Natural): bool =
case piece
of Queen:
for i in 0..<s.n:
if s.board[i][col] or s.board[row][i]:
return true
result = s.diag1Lookup[s.diag1[row][col]] or s.diag2Lookup[s.diag2[row][col]]
of Bishop:
result = s.diag1Lookup[s.diag1[row][col]] or s.diag2Lookup[s.diag2[row][col]]:
of Knight:
result = s.board[row][col] or
row + 2 < s.n and col - 1 >= 0 and s.board[row + 2][col - 1] or
row - 2 >= 0 and col - 1 >= 0 and s.board[row - 2][col - 1] or
row + 2 < s.n and col + 1 < s.n and s.board[row + 2][col + 1] or
row - 2 >= 0 and col + 1 < s.n and s.board[row - 2][col + 1] or
row + 1 < s.n and col + 2 < s.n and s.board[row + 1][col + 2] or
row - 1 >= 0 and col + 2 < s.n and s.board[row - 1][col + 2] or
row + 1 < s.n and col - 2 >= 0 and s.board[row + 1][col - 2] or
row - 1 >= 0 and col - 2 >= 0 and s.board[row - 1][col - 2]
func attacks(piece: Piece; row, col, trow, tcol: int): bool =
case piece
of Queen:
result = row == trow or col == tcol or abs(row - trow) == abs(col - tcol)
of Bishop:
result = abs(row - trow) == abs(col - tcol)
of Knight:
let rd = abs(trow - row)
let cd = abs(tcol - col)
result = (rd == 1 and cd == 2) or (rd == 2 and cd == 1)
func storeLayout(s: var Solver; piece: Piece) =
for row in s.board:
for cell in row:
s.layout.add if cell: ($piece)[0] & ' ' else: ". "
s.layout.add '\n'
func placePiece(s: var Solver; piece: Piece; countSoFar, maxCount: int) =
if countSoFar >= s.minCount: return
var allAttacked = true
var ti, tj = 0
block CheckAttacked:
for i in 0..<s.n:
for j in 0..<s.n:
if not s.isAttacked(piece, i, j):
allAttacked = false
ti = i
tj = j
break CheckAttacked
if allAttacked:
s.minCount = countSoFar
s.storeLayout(piece)
return
if countSoFar <= maxCount:
var si = ti
var sj = tj
if piece == Knight:
dec si, 2
dec sj, 2
if si < 0: si = 0
if sj < 0: sj = 0
for i in si..<s.n:
for j in sj..<s.n:
if not s.isAttacked(piece, i, j):
if (i == ti and j == tj) or attacks(piece, i, j, ti, tj):
s.board[i][j] = true
if piece != Knight:
s.diag1Lookup[s.diag1[i][j]] = true
s.diag2Lookup[s.diag2[i][j]] = true
s.placePiece(piece, countSoFar + 1, maxCount)
s.board[i][j] = false
if piece != Knight:
s.diag1Lookup[s.diag1[i][j]] = false
s.diag2Lookup[s.diag2[i][j]] = false
func initSolver(n: Positive; piece: Piece): Solver =
result.n = n
result.board = newSeqWith(n, newSeq[bool](n))
if piece != Knight:
result.diag1 = newSeqWith(n, newSeq[int](n))
result.diag2 = newSeqWith(n, newSeq[int](n))
for i in 0..<n:
for j in 0..<n:
result.diag1[i][j] = i + j
result.diag2[i][j] = i - j + n - 1
result.diag1Lookup = newSeq[bool](2 * n - 1)
result.diag2Lookup = newSeq[bool](2 * n - 1)
result.minCount = int32.high
proc main() =
let start = getMonoTime()
const Limits = [Queen: 10, Bishop: 10, Knight: 10]
for piece in Piece.low..Piece.high:
echo $piece & 's'
echo "=======\n"
var n = 0
while true:
inc n
var solver = initSolver(n , piece)
for maxCount in 1..(n * n):
solver.placePiece(piece, 0, maxCount)
if solver.minCount <= n * n:
break
echo &"{n:>2} × {n:<2} : {solver.minCount}"
if n == Limits[piece]:
echo &"\n{$piece}s on a {n} × {n} board:"
echo '\n' & solver.layout
break
let elapsed = getMonoTime() - start
echo "Took: ", elapsed
main()
</syntaxhighlight>
{{out}}
<pre>Queens
=======
1 × 1 : 1
2 × 2 : 1
3 × 3 : 1
4 × 4 : 3
5 × 5 : 3
6 × 6 : 4
7 × 7 : 4
8 × 8 : 5
9 × 9 : 5
10 × 10 : 5
Queens on a 10 × 10 board:
. . Q . . . . . . .
. . . . . . . . . .
. . . . . . . . Q .
. . . . . . . . . .
. . . . Q . . . . .
. . . . . . . . . .
Q . . . . . . . . .
. . . . . . . . . .
. . . . . . Q . . .
. . . . . . . . . .
Bishops
=======
1 × 1 : 1
2 × 2 : 2
3 × 3 : 3
4 × 4 : 4
5 × 5 : 5
6 × 6 : 6
7 × 7 : 7
8 × 8 : 8
9 × 9 : 9
10 × 10 : 10
Bishops on a 10 × 10 board:
. . . . . . . . . B
. . . . . . . . . .
. . . B . B . . . .
. . . B . B . B . .
B . . . . . . . . .
. . . . . . . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . B . . . .
. . . . . . . . . .
Knights
=======
1 × 1 : 1
2 × 2 : 4
3 × 3 : 4
4 × 4 : 4
5 × 5 : 5
6 × 6 : 8
7 × 7 : 13
8 × 8 : 14
9 × 9 : 14
10 × 10 : 16
Knights on a 10 × 10 board:
. . . . . . . . . .
. . K K . . . . . .
. . K K . . . K K .
. . . . . . . K K .
. . . . . . . . . .
. . . . . . . . . .
. K K . . . . . . .
. K K . . . K K . .
. . . . . . K K . .
. . . . . . . . . .
Took: (seconds: 19, nanosecond: 942476699)
</pre>
Line 2,013 ⟶ 2,231:
Although far quicker than it was originally (it now gets to 7 knights in less than a minute), it struggles after that and needs north of 21 minutes to get to 10.
<syntaxhighlight lang="
var board
Line 2,253 ⟶ 2,471:
I have borrowed one or two tricks from the Julia/Python versions in formulating the constraints.
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||