Algoritmo di Sudoku in C#

Question

Ho bisogno di un supporto (o vicino ad esso) che verifichi che un dato array di 9 elementi non contenga numeri ripetuti 1,2,3, ..., 9. Gli zeri ripetuti non contano (rappresentano le celle vuote).

il migliore che abbia uscito finora è:

var a = new int[9] {1,2,3,4,5,6,7,8,9}; 
var itIsOk = a.Join(a, i => i, j => j, (x, y) => x) 
    .GroupBy(y => y).Where(g => g.Key > 0 && g.Count() > 1).Count() == 0; 

Se non si vuole risolvere i miei problemi :), potrebbe almeno dire se quanto sopra algoritmo funziona correttamente?

E, sì, uno ha letto this one.

Answer 1

Fortunato per te ho costruito un risolutore di sudoku da solo non molto tempo fa :) L'intera operazione era di circa 200 righe di C# e risolveva i puzzle più difficili che riuscivo a trovare in 4 secondi o meno.

prestazioni probabilmente non è poi così grande a causa dell'uso di Count, ma dovrebbe funzionare:

!a.Any(i => i != 0 && a.Where(j => j != 0 && i == j).Count > 1) 

Inoltre, la parte j != 0 non è realmente necessario, ma dovrebbe aiutare le cose funzionano un po ' Più veloce.

[modifica:] La risposta di KVB mi ha dato un'altra idea:

!a.Where(i => i != 0).GroupBy(i => i).Any(gp => gp.Count() > 1) 

filtro del 0 del prima raggruppamento. Sebbene basato su come funziona IEnumerable, potrebbe non avere importanza.

In entrambi i casi, per ottenere prestazioni ottimali sostituire .Count > 1 in uno di quelli con un nuovo metodo di estensione IEnumerable che assomiglia a questo:

bool MoreThanOne(this IEnumerable<T> enumerable, Predictate<T> pred) 
{ 
    bool flag = false; 
    foreach (T item in enumerable) 
    { 
     if (pred(item)) 
     { 
      if (flag) 
      return true; 
      flag = true; 
     } 
    } 
    return false; 
} 

probabilmente non importa molto in quanto le matrici sono limitati a 9 elementi, ma se lo chiami molto potrebbe aggiungere.

Answer 2

!a.GroupBy(i => i).Any(gp => gp.Key != 0 && gp.Count() > 1)

Answer 3

ne dite:

var itIsOk = a.Where(x => x > 0).Distinct().Count() == a.Where(x => x > 0).Count(); 

Ragionamento: Innanzitutto creare un'enumerazione, senza 0s. Tra i numeri rimanenti, se la sua distinta lista ha la stessa lunghezza della lista attuale, non ci sono ripetizioni.

oppure: Se l'elenco di numeri univoci è inferiore all'elenco effettivo, è necessario disporre di un numero ripetuto.

Questa è la versione monocamera. L'elenco a.Where (x => x> 0) potrebbe essere scomposto.

var nonZeroList = a.Where(x => x > 0).ToList(); 
var itIsOk = nonZeroList.Distinct().Count() == nonZeroList.Count(); 

Answer 4

perché vuoi una linea contorta di codice LINQ, piuttosto che avvolgendo un'efficace attuazione del test in un metodo di estensione e la chiamata che?

var a = new int[9] {1,2,3,4,5,6,7,8,9}; 
var itIsOk = a.HasNoNonZeroRepeats(); 

Uno attuazione NoNonZeroRepeats potrebbe essere quella di utilizzare i 9 bit inferiori di un breve per indicare la presenza di un valore nella matrice, dando un O (lunghezza (a)) Prova non sfruttati memoria dinamica.Linq è carino, ma a meno che tu non lo stia usando solo per ragioni estetiche (non dici specificamente che stai scrivendo un solutore di sudoku usando solo Linq come esercizio) sembra solo aggiungere complessità qui.

Answer 5

solito cipiglio su soluzioni che coinvolgono catturati variabili, ma ho avuto il bisogno di scrivere questo:

bool hasRepeating = false; 
int previous = 0; 

int firstDuplicateValue = a 
    .Where(i => i != 0) 
    .OrderBy(i => i) 
    .FirstOrDefault(i => 
    { 
    hasRepeating = (i == previous); 
    previous = i; 
    return hasRepeating; 
    }); 

if (hasRepeating) 
{ 
    Console.WriteLine(firstDuplicateValue); 
} 

Answer 6

Si tratta di circa 50-250 volte più veloce di una soluzione LINQ (a seconda di come presto il duplicato è trovato):

public static bool IsValid(int[] values) { 
    int flag = 0; 
    foreach (int value in values) { 
     if (value != 0) { 
      int bit = 1 << value; 
      if ((flag & bit) != 0) return false; 
      flag |= bit; 
     } 
    } 
    return true; 
} 

Answer 7

Questa è una vecchia questione, ma di recente ho è stato segnalato ad una soluzione 1 line utilizzando SQL personalizzato di Oracle per fare le strutture ad albero. Ho pensato che sarebbe stato carino convertirlo in Linq.

Si può leggere di più sul mio blog su come Solve Sudoku in 1 line of Linq

Ecco il codice:

public static string SolveStrings(string Board) 
{ 
    string[] leafNodesOfMoves = new string[] { Board }; 
    while ((leafNodesOfMoves.Length > 0) && (leafNodesOfMoves[0].IndexOf(' ') != -1)) 
    { 
     leafNodesOfMoves = (
      from partialSolution in leafNodesOfMoves 
      let index = partialSolution.IndexOf(' ') 
      let column = index % 9 
      let groupOf3 = index - (index % 27) + column - (index % 3) 
      from searchLetter in "123456789" 
      let InvalidPositions = 
      from spaceToCheck in Enumerable.Range(0, 9) 
      let IsInRow = partialSolution[index - column + spaceToCheck] == searchLetter 
      let IsInColumn = partialSolution[column + (spaceToCheck * 9)] == searchLetter 
      let IsInGroupBoxOf3x3 = partialSolution[groupOf3 + (spaceToCheck % 3) + 
       (int)Math.Floor(spaceToCheck/3f) * 9] == searchLetter 
      where IsInRow || IsInColumn || IsInGroupBoxOf3x3 
      select spaceToCheck 
      where InvalidPositions.Count() == 0 
      select partialSolution.Substring(0, index) + searchLetter + partialSolution.Substring(index + 1) 
       ).ToArray(); 
    } 
    return (leafNodesOfMoves.Length == 0) 
     ? "No solution" 
     : leafNodesOfMoves[0]; 
} 

Answer 8

Per brevità, se non le prestazioni, come su var = itIsOk a.Sum() == . a.Distinct() Sum();

Answer 9

Quanto segue è semplice e veloce.

if a.Select(i => Math.Pow(2, i - 1)).ToArray().Sum()==511 ...