116 lines
2.4 KiB
C#
116 lines
2.4 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using System.Diagnostics;
|
|
using System.Linq;
|
|
|
|
namespace nqueens
|
|
{
|
|
class Program
|
|
{
|
|
static void Main(string[] args)
|
|
{
|
|
var n = Convert.ToInt32(args[0]);
|
|
var lsQueens = new MinConflictsQueens(n);
|
|
var solution = lsQueens.Solve();
|
|
|
|
if (solution != null)
|
|
{
|
|
var s = string.Join(" ", solution.Select(i => i.ToString()));
|
|
Console.WriteLine(n);
|
|
Console.WriteLine(s);
|
|
Debug.WriteLine(n);
|
|
Debug.WriteLine(s);
|
|
}
|
|
else
|
|
{
|
|
Console.WriteLine("No solution");
|
|
}
|
|
}
|
|
}
|
|
|
|
public class MinConflictsQueens
|
|
{
|
|
private readonly int _n;
|
|
|
|
public MinConflictsQueens(int n)
|
|
{
|
|
_n = n;
|
|
}
|
|
|
|
private NBoard Initial()
|
|
{
|
|
//var random = new Random(1);
|
|
//var randValues = (from i in Enumerable.Range(0, _n)
|
|
// select random.Next(0, _n)).ToArray();
|
|
|
|
//var board = new List<int>(_n);
|
|
//for (var i = 0; i < _n; i++)
|
|
//{
|
|
// if (i % 2 == 0)
|
|
// board.Insert(0,i);
|
|
// else
|
|
// board.Insert(i,i);
|
|
|
|
//}
|
|
|
|
//return new NBoard(board.ToArray());
|
|
|
|
var board = new int[_n];
|
|
var n2 = _n/2;
|
|
for (var i = 1; i <= n2; i++)
|
|
{
|
|
board[i - 1] = 2*i - 1;
|
|
board[n2 + i - 1] = 2* (i - 1);
|
|
}
|
|
//board[n2 - 1] = 0;
|
|
return new NBoard(board);
|
|
}
|
|
|
|
public IList<int> Solve()
|
|
{
|
|
var nBoard = Initial();
|
|
var random = new Random();
|
|
int lastColumn = -1;
|
|
int iterations = 0;
|
|
|
|
while (true)
|
|
{
|
|
if (nBoard.IsFeasible())
|
|
return nBoard.Columns;
|
|
|
|
if (++iterations % 100 == 0)
|
|
Debug.WriteLine("{0} : {1}", iterations, nBoard.Conflicts.Sum());
|
|
|
|
// select the next biggest conflict count
|
|
var maxConflictColumn =
|
|
(from c in Enumerable.Range(0, _n)
|
|
let conflicts = nBoard.Conflicts[c]
|
|
select new {c, conflicts})
|
|
.GroupBy(arg => arg.conflicts)
|
|
.OrderByDescending(grouping => grouping.Key)
|
|
.First()
|
|
.OrderBy(arg => random.Next())
|
|
.First()
|
|
.c;
|
|
|
|
if (maxConflictColumn == lastColumn)
|
|
maxConflictColumn = random.Next(0, _n);
|
|
lastColumn = maxConflictColumn;
|
|
|
|
var minConflictRow =
|
|
(from row in Enumerable.Range(0, _n)
|
|
let conflicts = nBoard.TestConflictCount(maxConflictColumn, row)
|
|
select new {row, conflicts})
|
|
.GroupBy(arg => arg.conflicts)
|
|
.OrderBy(grouping => grouping.Key)
|
|
.First()
|
|
.OrderBy(arg => random.Next())
|
|
.First()
|
|
.row;
|
|
|
|
nBoard.UpdateRow(maxConflictColumn, minConflictRow);
|
|
}
|
|
}
|
|
}
|
|
}
|