8queen.dart

/*
 * Ali Ghanbari - 970216657
 * online compiler: https://dartpad.dev/b7812076139d58b2c46258c33b5e7f30?null_safety=true
 */
import 'dart:math';

const n = 8;
enum Moves { Up, Down }

final random = Random();

void main() {
  final tests = 10000;

  var hcSolvedProblems =
      List.generate(tests, (i) => hillClimbing(Board.random()))
          .where((e) => e.isSolved)
          .toList();

  var saSolvedProblems = List.generate(
          tests, (i) => simulatedAnnealing(simpleTemperature, Board.random()))
      .where((e) => e.isSolved)
      .toList();

  printMethodStats(hcSolvedProblems, tests, 'Hill-Climbing');
  print('');
  printMethodStats(saSolvedProblems, tests, 'Simulated-Annealing');
}

void printMethodStats(List<Answer> answer, int total, String name) {
  var success = answer.length;
  var avgCost = answer.map((e) => e.cost).reduce(sum) / answer.length;
  var solvedPercent = ((success / total) * 100).toStringAsFixed(2);

  print('# $name:');
  print('Total instances: $total');
  print('Instances solved: $success');
  print('Solved percentage: $solvedPercent%');
  print('Average cost: $avgCost');
}

Answer hillClimbing(Board initialState) {
  var current = initialState;
  var i = 1;
  while (true) {
    var neighbours = current.allNeighbours().toList()..sort();
    var neighbour = neighbours.first; // board with min h
    if (neighbour.h >= current.h)
      return Answer(current, i); // if no improvement return
    current = neighbour;
    i++;
  }
}

Answer simulatedAnnealing(
    double Function(int iteration) temp, Board initialState) {
  var current = initialState;
  for (var i = 1; true; i++) {
    var t = temp(i);
    if (t == 0) return Answer(current, i);
    var neighbours = current.allNeighbours().toList();
    var next =
        neighbours[random.nextInt(neighbours.length)]; // random neighbour
    var delta = current.h - next.h;
    if (delta > 0 || probability(delta, t)) current = next;
  }
}

bool probability(int delta, double t) {
  var p = pow(e, delta / t);
  var result = p > random.nextDouble();
  return result;
}

double simpleTemperature(int i) {
  if (i < 100) {
    var t = 1.0;
    while (i-- > 0) {
      t *= 0.9;
    }
    return t;
  } else {
    return 0;
  }
}

class Board implements Comparable<Board> {
  final List<int> _state;

  Board(List<int> state) : _state = state; // constructor

  // generate a random board
  factory Board.random() {
    final state = List.generate(n, (i) => random.nextInt(n));
    return Board(state);
  }

  // row getter using bracket operator
  List<bool> operator [](int value) {
    final row = List.generate(n, (i) => _state[i] == value);
    return row;
  }

  List<List<bool>> get as2dBoard => List.generate(n, (i) => this[i]);

  Board? neighbour(int col, Moves move) {
    var newState = [..._state];
    if (move == Moves.Up) {
      if (newState[col] == 0) return null;
      newState[col] = (newState[col] - 1);
    } else {
      if (newState[col] == n - 1) return null;
      newState[col] = (newState[col] + 1);
    }
    return Board(newState);
  }

  Iterable<Board> allNeighbours() sync* {
    for (var i = 0; i < n; i++) {
      for (var m in Moves.values) {
        var board = neighbour(i, m);
        if (board != null) {
          yield board;
        }
      }
    }
  }

  int? _value;

  int get h {
    if (_value == null) {
      var attacking = 0;
      var board = as2dBoard;
      var countAttack = (int y, int x) => board[y][x] ? attacking++ : null;
      for (var j = 0; j < n; j++) {
        var i = _state[j];
        for (var k = j + 1; k < n; k++) // right
          countAttack(i, k);
        for (var k = j - 1; k >= 0; k--) // left
          countAttack(i, k);
        for (var k = i - 1, l = j - 1; k >= 0 && l >= 0; k--, l--) // topLeft
          countAttack(k, l);
        for (var k = i - 1, l = j + 1; k >= 0 && l < n; k--, l++) // topRight
          countAttack(k, l);
        for (var k = i + 1, l = j - 1; k < n && l >= 0; k++, l--) // bottomLeft
          countAttack(k, l);
        for (var k = i + 1, l = j + 1; k < n && l < n; k++, l++) // bottomRight
          countAttack(k, l);
      }
      _value = attacking ~/ 2;
    }
    return _value!;
  }

  @override
  int compareTo(Board other) => h - other.h;
}

class Answer {
  final Board board;
  final int cost;

  Answer(this.board, this.cost);

  bool get isSolved => board.h == 0;
}

int sum(int a, int b) => a + b;