Algoritmo de sudoku en C#

Question

Necesito un liner (o cerca) que verifique que una matriz dada de 9 elementos no contenga los números repetitivos 1,2,3, ..., 9. La repetición de ceros no cuenta (representan celdas vacías).

El mejor que he salió hasta ahora es:

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; 

Si no desea resolver mis problemas :), ¿podría al menos decir si el algoritmo anterior funciona correctamente?

Y, sí, a han leído this one.

Answer 1

Afortunado para ti construí un solucionador de sudoku no hace mucho tiempo :) Todo el asunto tenía unas 200 líneas de C#, y resolvería los acertijos más difíciles que pude encontrar en 4 segundos o menos.

rendimiento probablemente no es tan grande debido a la utilización de .Count, pero debería funcionar:

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

Además, la parte j != 0 no es realmente necesario, pero debe ayudar a que las cosas funcionen un poco Más rápido.

[editar:] La respuesta de kvb me dio otra idea:

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

Filtrar el 0 de antes agrupación. Aunque basado en cómo funciona IEnumerable, puede que no importe.

De cualquier manera, Para un mejor rendimiento reemplazar .Count > 1 en cualquiera de aquellos con un nuevo método de extensión IEnumerable que tiene este aspecto:

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; 
} 

Es probable que no importa demasiado ya que las matrices están limitados a 9 elementos, pero si lo llamas mucho, podría sumar.

Answer 2

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

Answer 3

¿Qué tal:

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

Razonamiento: En primer lugar crear una enumeración sin 0s. De los números restantes, si su lista distinta es de la misma longitud que la lista real, entonces no hay repeticiones.

o: Si la lista de números únicos es más pequeña que la lista real, entonces debe tener un número repetido.

Esta es la versión de una sola línea. La lista a.Where (x => x> 0) se puede descartar.

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

Answer 4

¿Por qué quiere una línea de código enrevesado LINQ, en lugar de envolver una implementación eficiente de la prueba en un método de extensión y llamar a eso?

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

Una implementación de NoNonZeroRepeats podría ser utilizar los 9 bits más bajos de un corto para indicar la presencia de un valor de la matriz, dando un O (longitud (a)) prueba sin el uso de memoria dinámica.Linq es lindo, pero a menos que solo lo estés usando por razones estéticas (no dices específicamente que estás escribiendo un sudoku para resolverlo usando solo Linq como ejercicio) parece que está agregando complejidad aquí.

Answer 5

lo general fruncir el ceño en soluciones que implican las variables capturadas, pero no tenía ganas de escribir esto:

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

Esto es aproximadamente 50-250 veces más rápido que una solución LINQ (dependiendo de la antelación con el duplicado es encontrado):

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

Esta es una vieja pregunta, pero se señaló recientemente a una solución de 1 línea utilizando SQL personalizada de Oracle para hacer estructuras en forma de árbol. Pensé que sería bueno convertir esto en Linq.

Usted puede leer más en mi blog acerca de cómo Solve Sudoku in 1 line of Linq

Aquí está el código:

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

Por razones de brevedad, si no el rendimiento, ¿qué hay de var = itIsOk a.Sum() == a.Distinct(). Sum();

Answer 9

Lo que sigue es simple y rápido.

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