Comments:

Flat Nested Threaded Embedded

Oldest First Newest First

Solution in C# By kp.zeus on Saturday, July 05, 2008 (UMST)

public class NQueen { public static void DisplaySolutions(int sizeOfBoard) { Console.WriteLine("N Queens Solutions For Size : " + sizeOfBoard); List<Square[]> solutions = GetSolutions(sizeOfBoard); Console.WriteLine("No. of Solns : " + solutions.Count); foreach (Square[] solution in solutions) { foreach (Square square in solution) { Console.Write("{" + square.X + "," + square.Y + "}"); } Console.WriteLine(); } Console.WriteLine(); } public static List<Square[]> GetSolutions(int sizeOfBoard) { List<Square[]> solutions = new List<Square[]>(); //1,2,3 Not Possible if (sizeOfBoard > 3) { int x = 0; int y = 0; while (x < sizeOfBoard) { while (y < sizeOfBoard) { List<Square[]> subset = CheckFromSquare(sizeOfBoard, x, y); foreach (Square[] solution in subset) { if (!ContainsSolution(solutions,solution)) solutions.Add(solution); } y++; } x++; } } return solutions; } private static List<Square[]> CheckFromSquare(int sizeOfBoard, int x, int y) { List<Square[]> solutions = new List<Square[]>(); Square[] solution = new Square[sizeOfBoard]; bool[][] squares = GetNewBoard(sizeOfBoard); Dictionary<Square, List<Square>> failedPaths = new Dictionary<Square, List<Square>>(); int i = 0, j = 0, queenCount = 0; int count = 0, totalChecks = (int)Math.Pow(sizeOfBoard, sizeOfBoard); totalChecks = sizeOfBoard * sizeOfBoard; totalChecks = 1000; while (count < totalChecks) { count++; i = 0; j = 0; squares = GetNewBoard(sizeOfBoard); //Set Start Position To First Queen queenCount = 1; squares[x][y] = true; solution[queenCount - 1] = new Square(x, y); while (i < sizeOfBoard) { while (j < sizeOfBoard && queenCount <= sizeOfBoard) { if (Safe(squares, i, j)) { if (failedPaths.ContainsKey(solution[queenCount - 1]) && failedPaths[solution[queenCount - 1]].Contains(new Square(i, j)) ) { } else { queenCount++; solution[queenCount - 1] = new Square(i, j); squares[i][j] = true; break; } //if (queenCount == (minQueenCount + 1) && IsFailedPath(failedPaths, solution)) //{ // solution[queenCount - 1] = null; // queenCount--; //} } j++; } j = 0; i++; } if (queenCount == sizeOfBoard) { solutions.Add(solution); } else { if (queenCount > 1) { if (!failedPaths.ContainsKey(solution[queenCount - 2])) failedPaths.Add(solution[queenCount - 2], new List<Square>()); if (!failedPaths[solution[queenCount - 2]].Contains(solution[queenCount - 1])) { failedPaths[solution[queenCount - 2]].Add(solution[queenCount - 1]); } } } solution = new Square[sizeOfBoard]; } //if (queenCount == sizeOfBoard) // return solution; //else //{ // //if (history.Count < ((sizeOfBoard - 1) * sizeOfBoard)) // //{ // // history.Add(solution); // // return CheckFromSquare(sizeOfBoard, x, y, history); // //} //} return solutions; } private static bool SameSolution(Square[] a, Square[] b) { int i = 0; while ((a[i] == null && b[i] == null) || a[i].Equals(b[i])) { i++; } if (i == a.Length) return true; return false; } private static bool ContainsSolution(List<Square[]> solutions, Square[] solution) { int i = 0; foreach (Square[] element in solutions) { while (i < element.Length && ( (element[i] == null && solution[i] == null) || element[i].Equals(solution[i]) ) ) { i++; } if (i == element.Length) return true; i = 0; } return false; } private static bool Safe(bool[][] squares, int x, int y) { if ( HorizontalSafe(squares, x, y) && VerticalSafe(squares, x, y) && DiagonalSafe(squares, x, y) ) return true; else return false; } private static bool HorizontalSafe(bool[][] squares, int x, int y) { for (int i = 0; i < squares.Length; i++) { if (squares[x][i]) return false; } return true; } private static bool VerticalSafe(bool[][] squares, int x, int y) { for (int i = 0; i < squares.Length; i++) { if (squares[i][y]) return false; } return true; } private static bool DiagonalSafe(bool[][] squares, int x, int y) { int i = x; int j = y; //x increases, y increases while (i < squares.Length && j < squares.Length) { if (squares[i][j]) return false; i++; j++; } //x decreases, y increases i = x; j = y; while (i > -1 && j < squares.Length) { if (squares[i][j]) return false; i--; j++; } //x increases, y decreases i = x; j = y; while (i < squares.Length && j > -1) { if (squares[i][j]) return false; i++; j--; } //x decreases, y decreases i = x; j = y; while (i > -1 && j > -1) { if (squares[i][j]) return false; i--; j--; } return true; } private static bool[][] GetNewBoard(int sizeOfBoard) { bool[][] squares = new bool[sizeOfBoard][]; for (int i = 0; i < sizeOfBoard; i++) { squares[i] = new bool[sizeOfBoard]; } return squares; } } public class Square { int x; public int X { get { return x; } } int y; public int Y { get { return y; } } public Square(int x, int y) { this.x = x; this.y = y; } public override bool Equals(object obj) { Square entity = obj as Square; if (entity != null && entity.X == this.X && entity.Y == this.Y) return true; else return false; } public override int GetHashCode() { return (this.X * 10) + this.y; } } Reply to this Comment