Przejdź do treści

Problem n królowych

Opis problemu

Implementacja

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
fun findSolution(n: Int, queenId: Int, positions: Array<Int>): Boolean {
    if (queenId == n) {
        return true
    }

    for (i in 0 until n) {
        if (!checkNewPosition(queenId, i, positions)) {
            continue
        }

        positions[queenId] = i

        if (findSolution(n, queenId + 1, positions)) {
            return true
        }
    }

    return false
}

fun checkNewPosition(x: Int, y: Int, positions: Array<Int>): Boolean {
    for (i in 0 until x) {
        if (positions[i] == y) {
            return false
        }

        if ((y - positions[i]) == (x - i)) {
            return false
        }
    }

    return true
}

fun printCheckboard(n: Int, positions: Array<Int>) {
    val board = Array(n) { IntArray(n) }

    for (i in 0 until n) {
        board[positions[i]][i] = 1
    }

    for (i in 0 until n) {
        println(board[i].contentToString())
    }
}

fun main() {
  val n = 5
  val positions = Array(n) {0}

  val result = findSolution(n, 0, positions)

  if (result) {
      println("Pozycje:")
      println(positions.contentToString())
      println("Szachownica:")
      printCheckboard(n, positions)
  } else {
      println("Brak rozwiazania")
  }
}