N-queens minimum and knights and bishops: Difference between revisions

Content added Content deleted
m (→‎{{header|Go}}: Moved some code.)
(→‎{{header|Wren}}: Improvements in line with Go example.)
Line 1,619: Line 1,619:
=={{header|Wren}}==
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-fmt}}
⚫
This was oringinally 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 then used the more efficient way for checking the diagonals described [https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/ here] and have now incorporated the improvements made to the Go version.
Although this seems to work and give the correct answers, it's very slow taking about 23.5 minutes to run even when the board sizes are limited to 6 x 6 (bishops) and 5 x 5 (knights).


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 26 minutes to get to 10.
⚫
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
<lang ecmascript>import "./fmt" for Fmt


Line 1,632: Line 1,632:
var minCount
var minCount
var layout
var layout

var isAttacked = Fn.new { |piece, row, col|
var isAttacked = Fn.new { |piece, row, col|
if (piece == "Q") {
if (piece == "Q") {
Line 1,641: Line 1,641:
diag2Lookup[diag2[row][col]]) return true
diag2Lookup[diag2[row][col]]) return true
} else if (piece == "B") {
} else if (piece == "B") {
if (board[row][col]) return true
if (diag1Lookup[diag1[row][col]] ||
if (diag1Lookup[diag1[row][col]] ||
diag2Lookup[diag2[row][col]]) return true
diag2Lookup[diag2[row][col]]) return true
Line 1,656: Line 1,655:
}
}
return false
return false
}

var attacks = Fn.new { |piece, row, col, trow, tcol|
if (piece == "Q") {
return row == trow || col == tcol || (row-trow).abs == (col-tcol).abs
} else if (piece == "B") {
return (row-trow).abs == (col-tcol).abs
} else { // piece == "K"
var rd = (trow - row).abs
var cd = (tcol - col).abs
return (rd == 1 && cd == 2) || (rd == 2 && cd == 1)
⚫
}
}
}


Line 1,668: Line 1,679:


var placePiece // recursive function
var placePiece // recursive function
placePiece = Fn.new { |piece, countSoFar|
placePiece = Fn.new { |piece, countSoFar, maxCount|
if (countSoFar >= minCount) return
if (countSoFar >= minCount) return
var allAttacked = true
var allAttacked = true
var ti = 0
var tj = 0
for (i in 0...n) {
for (i in 0...n) {
for (j in 0...n) {
for (j in 0...n) {
if (!isAttacked.call(piece, i, j)) {
if (!isAttacked.call(piece, i, j)) {
allAttacked = false
allAttacked = false
ti = i
tj = j
break
break
}
}
Line 1,685: Line 1,700:
return
return
}
}
for (i in 0...n) {
if (countSoFar <= maxCount) {
for (j in 0...n) {
var si = (piece == "K") ? 0 : ti
if (!isAttacked.call(piece, i, j)) {
var sj = (piece == "K") ? 0 : tj
board[i][j] = true
for (i in si...n) {
diag1Lookup[diag1[i][j]] = true
for (j in sj...n) {
diag2Lookup[diag2[i][j]] = true
if (!isAttacked.call(piece, i, j)) {
placePiece.call(piece, countSoFar + 1)
if ((i == ti && j == tj) || attacks.call(piece, i, j, ti, tj)) {
board[i][j] = false
board[i][j] = true
diag1Lookup[diag1[i][j]] = false
if (piece != "K") {
diag2Lookup[diag2[i][j]] = false
diag1Lookup[diag1[i][j]] = true
diag2Lookup[diag2[i][j]] = true
⚫
}
placePiece.call(piece, countSoFar + 1, maxCount)
board[i][j] = false
if (piece != "K") {
diag1Lookup[diag1[i][j]] = false
diag2Lookup[diag2[i][j]] = false
}
}
}
}
}
}
}
Line 1,700: Line 1,725:
}
}


var start = System.clock
var pieces = ["Q", "B", "K"]
var pieces = ["Q", "B", "K"]
var limits = {"Q": 10, "B": 6, "K": 5}
var limits = {"Q": 10, "B": 10, "K": 10}
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
for (piece in pieces) {
for (piece in pieces) {
Line 1,710: Line 1,736:
board = List.filled(n, null)
board = List.filled(n, null)
for (i in 0...n) board[i] = List.filled(n, false)
for (i in 0...n) board[i] = List.filled(n, false)
diag1 = List.filled(n, null)
if (piece != "K") {
for (i in 0...n) {
diag1 = List.filled(n, null)
diag1[i] = List.filled(n, 0)
for (i in 0...n) {
for (j in 0...n) diag1[i][j] = i + j
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)
}
}
⚫
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
minCount = Num.maxSafeInteger
layout = ""
layout = ""
placePiece.call(piece, 0)
for (maxCount in 1..n*n) {
placePiece.call(piece, 0, maxCount)
if (minCount <= n*n) break
⚫
}
Fmt.print("$2d x $-2d : $d", n, n, minCount)
Fmt.print("$2d x $-2d : $d", n, n, minCount)
if (n == limits[piece]) {
if (n == limits[piece]) {
Line 1,733: Line 1,764:
n = n + 1
n = n + 1
}
}
}
}</lang>
System.print("Took %(System.clock - start) seconds.")</lang>


{{out}}
{{out}}
Line 1,773: Line 1,805:
5 x 5 : 5
5 x 5 : 5
6 x 6 : 6
6 x 6 : 6
7 x 7 : 7
8 x 8 : 8
9 x 9 : 9
10 x 10 : 10


Bishops on a 6 x 6 board:
Bishops on a 10 x 10 board:


B . . B . .
. . . . . . . . . B
. . . B . .
. . . . . . . . . .
. . . B . .
. . . B . B . . . .
. . . . . .
. . . B . B . B . .
. . B B . .
B . . . . . . . . .
. . . . . .
. . . . . . . . . .
⚫
. . . . . B . . . .
⚫
. . . . . B . . . .
⚫
. . . . . B . . . .
⚫
. . . . . . . . . .


Knights
Knights
Line 1,791: Line 1,831:
4 x 4 : 4
4 x 4 : 4
5 x 5 : 5
5 x 5 : 5
6 x 6 : 8
7 x 7 : 13
8 x 8 : 14
9 x 9 : 14
10 x 10 : 16


Knights on a 5 x 5 board:
Knights on a 10 x 10 board:


K . . . .
. . . . . . . . . .
. . . . .
. . K K . . . . . .
. . K K .
. . K K . . . K K .
. . K K .
. . . . . . . K K .
. . . . .
. . . . . . . . . .
⚫
. . . . . . . . . .
</pre>
⚫
. K K . . . . . . .
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:
⚫
. K K . . . K K . .
<pre>
. . . . . . K K . .
Queens on a 8 x 8 board:
. . . . . . . . . .


Took 1583.020941 seconds.
⚫
Q . . . . . . .
⚫
. . Q . . . . .
⚫
. . . . Q . . .
⚫
. Q . . . . . .
⚫
. . . Q . . . .
⚫
. . . . . . . .
⚫
. . . . . . . .
⚫
. . . . . . . .
</pre>
</pre>
Retrieved from "https://rosettacode.org/wiki/N-queens_minimum_and_knights_and_bishops"