N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 16:44, 25 April 2022
, 2 years ago→{{header|Wren}}: Improved method for checking diagonals.
(→{{header|Wren}}: Improved method for checking diagonals.) |
|||
Line 420:
=={{header|Wren}}==
{{libheader|Wren-fmt}}
Although this seems to work and give the correct answers, it's very slow
It's based on the Java code [https://www.geeksforgeeks.org/minimum-queens-required-to-cover-all-the-squares-of-a-chess-board/ here] which uses a backtracking algorithm and which I extended to deal with bishops and knights as well as queens when translating to Wren. I've used the more efficient way for checking the diagonals described [https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/ here].
<lang ecmascript>import "./fmt" for Fmt
var board
var diag1
var diag2
var diag1Lookup
var diag2Lookup
var n
var minCount
Line 435 ⟶ 439:
if (board[i][col] || board[row][i]) return true
}
}▼
} else if (piece == "B") {
if (board[row][col]) return true
}▼
} else { // piece == "K"
if (board[row][col]) return true
Line 490 ⟶ 486:
return
}
for (i in 0...n) {
for (j in 0...n) {
if (!isAttacked.call(piece, i, j)) {
board[i][j] = true
diag1Lookup[diag1[i][j]] = true
diag2Lookup[diag2[i][j]] = true
placePiece.call(piece, countSoFar + 1)
board[i][j] = false
diag1Lookup[diag1[i][j]] = false
diag2Lookup[diag2[i][j]] = false
}
}
Line 503 ⟶ 502:
var pieces = ["Q", "B", "K"]
var limits = {"Q":
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
for (piece in pieces) {
Line 512 ⟶ 511:
board = List.filled(n, null)
for (i in 0...n) board[i] = List.filled(n, false)
diag1 = List.filled(n, null)
for (i in 0...n) {
diag1[i] = List.filled(n, 0)
for (j in 0...n) diag1[i][j] = i + j
▲ }
diag2 = List.filled(n, null)
for (i in 0...n) {
diag2[i] = List.filled(n, 0)
for (j in 0...n) diag2[i][j] = i - j + n - 1
▲ }
diag1Lookup = List.filled(2*n-1, false)
diag2Lookup = List.filled(2*n-1, false)
minCount = Num.maxSafeInteger
layout = ""
Line 538 ⟶ 549:
7 x 7 : 4
8 x 8 : 5
9 x 9 : 5
10 x 10 : 5
Queens on a
. . Q . . . . . . .
. .
. . . .
.
. . . . Q . . . . .
. . . . . . . . . .
Q . . . . . . . . .
. . . . . . . . . .
. . . . . . Q . . .
. . . . . . . . . .
Bishops
Line 585 ⟶ 600:
. . K K .
. . . . .
</pre>
If I limit the board size for the queens to 8 x 8, the run time comes down to around 2 minutes 12 seconds and the following example layout is produced:
<pre>
Queens on a 8 x 8 board:
Q . . . . . . .
. . Q . . . . .
. . . . Q . . .
. Q . . . . . .
. . . Q . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
</pre>
| |||