Mick Byrne
BAN USERHere's a solution in C# using a recursive, backtracking algorithm. It gets there, but once you get around n >= 14, it's pretty slow.
using System;
using System.Collections.Generic;
namespace NQueens
{
class MainClass
{
// This is an array of the column positions for each row for each placed queen.
// So if placedQueens[3] == 2, then it means there's a queen on the 3rd row, 2nd column.
static int[] placedQueens;
static int matches;
public static void Main (string[] args)
{
Console.WriteLine("N Queens");
Console.WriteLine("---");
for (int i = 4; i <= 15; i++)
{
StartPlacingQueens(i);
}
}
static void StartPlacingQueens(int size)
{
Console.WriteLine("Placing " + size + " queens...");
matches = 0;
placedQueens = new int[size + 1]; // The value at placedQueens[0] is ignored
PlaceQueens(1, size);
Console.WriteLine("Total matches " + matches);
Console.WriteLine();
}
static void PlaceQueens(int row, int size)
{
for (int col = 1; col <= size; col++)
{
if(CanPlace(row, col))
{
placedQueens[row] = col;
if (row == size)
{
matches++;
}
else
{
PlaceQueens(row + 1, size);
}
}
}
}
static bool CanPlace(int row, int col)
{
// If we call this method, we assume that all the prior rows (i.e. <= row) already have queens on them
for(int queenRow = 1; queenRow < row; queenRow++)
{
int queenCol = placedQueens[queenRow];
if (DoesIntefere(row, col, queenRow, queenCol))
{
return false;
}
}
return true;
}
static bool DoesIntefere(int xRow, int xCol, int yRow, int yCol)
{
// Check matching row - you could remove this check in this context
if (xRow == yRow) { return true; }
// Check matching col
if (xCol == yCol) { return true; }
// Check diagonal
if (Math.Abs(xCol - yCol) == Math.Abs(xRow - yRow)) { return true; }
// Check for the knight collision
if (
(Math.Abs(xCol - yCol) == 2 && Math.Abs(xRow - yRow) == 1) ||
(Math.Abs(xCol - yCol) == 1 && Math.Abs(xRow - yRow) == 2)
)
{
return true;
}
// We're good
return false;
}
}
}
using System;
using System.Collections.Generic;
// This is a trick question. No need to actually determine the string, only to find if it _can_be shuffled or not.
// String can always be shuffled as long as the count of the most common character is <= (s.length + 1) / 2
namespace FancyShuffle
{
class MainClass
{
public static void Main (string[] args)
{
Console.WriteLine("Fancy Shuffle");
Console.WriteLine("---");
Console.WriteLine("Can shuffle 'aa' : " + CanFancyShuffle("aa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ab' : " + CanFancyShuffle("ab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'aba' : " + CanFancyShuffle("aba".ToCharArray())); // True
Console.WriteLine("Can shuffle 'abaa' : " + CanFancyShuffle("abaa".ToCharArray())); // False
Console.WriteLine("Can shuffle 'abab' : " + CanFancyShuffle("abab".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababa' : " + CanFancyShuffle("ababa".ToCharArray())); // True
Console.WriteLine("Can shuffle 'ababaa' : " + CanFancyShuffle("ababaa".ToCharArray())); // False
Console.WriteLine("Can shuffle '' : " + CanFancyShuffle("".ToCharArray())); // True
}
static bool CanFancyShuffle(char[] s)
{
int highestCount = 0;
Dictionary<char, int> charCounts = new Dictionary<char, int> ();
foreach (char c in s)
{
if (charCounts.ContainsKey(c))
{
charCounts[c] = charCounts[c] + 1;
}
else
{
charCounts.Add(c, 1);
}
highestCount = Math.Max(highestCount, charCounts[c]);
}
return highestCount <= (s.Length + 1) / 2;
}
}
}
Repmelodyakeel, Consultant at Progress
Hello I am Melody. I am working as Human resource clerks, also called human resource assistants. I can maintain employee ...
Here's a complete Java answer:
- Mick Byrne October 02, 2016