Вот чисто для примера создал алгозадачу
Сколько джаст дуит будет решать эту задачу? Даже если он только что решил N-queens?
Решение от чатжпт
import kotlin.math.abs
fun main() {
val word = "abc"
val n = 2
val permutations = word.toList().permute().map { it.joinToString("") }
val board = Array(n) { Array<String?>(n) { null } }
val usedStartRow = Array(n) { mutableSetOf<Char>() }
val usedStartCol = Array(n) { mutableSetOf<Char>() }
val usedStartDiag1 = mutableMapOf<Int, MutableSet<Char>>() // r-c
val usedStartDiag2 = mutableMapOf<Int, MutableSet<Char>>() // r+c
val usedEndRow = Array(n) { mutableSetOf<Char>() }
val usedEndCol = Array(n) { mutableSetOf<Char>() }
val usedEndDiag1 = mutableMapOf<Int, MutableSet<Char>>()
val usedEndDiag2 = mutableMapOf<Int, MutableSet<Char>>()
place(0, 0, n, permutations, board,
usedStartRow, usedStartCol, usedStartDiag1, usedStartDiag2,
usedEndRow, usedEndCol, usedEndDiag1, usedEndDiag2)
}
fun place(
r: Int, c: Int, n: Int, words: List<String>, board: Array<Array<String?>>,
usedStartRow: Array<MutableSet<Char>>, usedStartCol: Array<MutableSet<Char>>,
usedStartDiag1: MutableMap<Int, MutableSet<Char>>, usedStartDiag2: MutableMap<Int, MutableSet<Char>>,
usedEndRow: Array<MutableSet<Char>>, usedEndCol: Array<MutableSet<Char>>,
usedEndDiag1: MutableMap<Int, MutableSet<Char>>, usedEndDiag2: MutableMap<Int, MutableSet<Char>>,
): Boolean {
if (r == n) {
printBoard(board)
return true
}
val nextR = if (c == n - 1) r + 1 else r
val nextC = if (c == n - 1) 0 else c + 1
for (w in words) {
if (isSafeFast(r, c, w,
usedStartRow, usedStartCol, usedStartDiag1, usedStartDiag2,
usedEndRow, usedEndCol, usedEndDiag1, usedEndDiag2)) {
board[r][c] = w
markUsed(true, r, c, w.first(), usedStartRow, usedStartCol, usedStartDiag1, usedStartDiag2)
markUsed(true, r, c, w.last(), usedEndRow, usedEndCol, usedEndDiag1, usedEndDiag2)
place(nextR, nextC, n, words, board,
usedStartRow, usedStartCol, usedStartDiag1, usedStartDiag2,
usedEndRow, usedEndCol, usedEndDiag1, usedEndDiag2)
board[r][c] = null
markUsed(false, r, c, w.first(), usedStartRow, usedStartCol, usedStartDiag1, usedStartDiag2)
markUsed(false, r, c, w.last(), usedEndRow, usedEndCol, usedEndDiag1, usedEndDiag2)
}
}
return false
}
fun isSafeFast(
r: Int, c: Int, word: String,
usedStartRow: Array<MutableSet<Char>>, usedStartCol: Array<MutableSet<Char>>,
usedStartDiag1: MutableMap<Int, MutableSet<Char>>, usedStartDiag2: MutableMap<Int, MutableSet<Char>>,
usedEndRow: Array<MutableSet<Char>>, usedEndCol: Array<MutableSet<Char>>,
usedEndDiag1: MutableMap<Int, MutableSet<Char>>, usedEndDiag2: MutableMap<Int, MutableSet<Char>>
): Boolean {
val s = word.first()
val e = word.last()
if (s in usedStartRow[r]) return false
if (s in usedStartCol[c]) return false
if (s in usedStartDiag1.getOrDefault(r - c, emptySet())) return false
if (s in usedStartDiag2.getOrDefault(r + c, emptySet())) return false
if (e in usedEndRow[r]) return false
if (e in usedEndCol[c]) return false
if (e in usedEndDiag1.getOrDefault(r - c, emptySet())) return false
if (e in usedEndDiag2.getOrDefault(r + c, emptySet())) return false
return true
}
fun markUsed(
add: Boolean, r: Int, c: Int, ch: Char,
usedRow: Array<MutableSet<Char>>, usedCol: Array<MutableSet<Char>>,
usedD1: MutableMap<Int, MutableSet<Char>>, usedD2: MutableMap<Int, MutableSet<Char>>
) {
if (add) {
usedRow[r].add(ch)
usedCol[c].add(ch)
usedD1.getOrPut(r - c) { mutableSetOf() }.add(ch)
usedD2.getOrPut(r + c) { mutableSetOf() }.add(ch)
} else {
usedRow[r].remove(ch)
usedCol[c].remove(ch)
usedD1[r - c]?.remove(ch)
usedD2[r + c]?.remove(ch)
}
}
fun <T> List<T>.permute(): List<List<T>> {
if (size <= 1) return listOf(this)
val result = mutableListOf<List<T>>()
for (i in indices) {
val rest = toMutableList().also { it.removeAt(i) }
for (p in rest.permute())
result += listOf(this[i]) + p
}
return result
}
fun printBoard(board: Array<Array<String?>>) {
println("Board:")
for (row in board) println(row.joinToString(" ") { it ?: "." })
println()
}
