Sudoku backtracking - Historial de revisiones

Edeliochajc en 03:13 22 feb 2015

2015-02-22T03:13:48Z

Edeliochajc en 00:16 22 feb 2015

2015-02-22T00:16:44Z

Yaquelin pedagogico.ssp en 15:23 11 ene 2011

2011-01-11T15:23:26Z

Mostrar los cambios

Kenia idict en 14:01 10 jun 2010

2010-06-10T14:01:40Z

Year bot: Removida de referencia

2010-06-09T17:37:39Z

Removida de referencia

Asanto uci: Página creada con '{{Referencia}}Sudoku (en japonés: 数独, sūdoku) es un pasatiempo que se popularizó en Japón en 1986, y se dio a conocer en el ámbito internacional en 2005. El objetivo de…'

2010-06-09T16:59:36Z

Página creada con '{{Referencia}}Sudoku (en japonés: 数独, sūdoku) es un pasatiempo que se popularizó en Japón en 1986, y se dio a conocer en el ámbito internacional en 2005. El objetivo de…'

Página nueva

{{Referencia}}Sudoku (en japonés: 数独, sūdoku) es un pasatiempo que se popularizó en Japón en 1986, y se dio a conocer en el ámbito internacional en 2005. El objetivo del sudoku es rellenar una cuadrícula de 9 × 9 celdas (81 casillas) dividida en subcuadrículas de 3 × 3 (también llamadas "cajas" o "regiones") con las cifras del 1 al 9 partiendo de algunos números ya dispuestos en algunas de las celdas. Aunque se podrían usar colores, letras, figuras, se conviene en usar números para mayor claridad. Lo que importa, en todo caso, es que sean nueve elementos diferenciados. No se debe repetir ninguna cifra en una misma fila, columna o subcuadrícula. Un sudoku está bien planteado si la solución es única. La resolución del problema requiere paciencia y ciertas dotes lógicas.

La solución de un sudoku siempre es un cuadrado latino, aunque el recíproco en general no es cierto ya que el sudoku establece la restricción añadida de que no se puede repetir un mismo número en una región.

Numerosos periódicos han empezado a publicar el sudoku desde el 2005 en su sección de pasatiempos.

== Reglas y terminología ==

El sudoku se presenta normalmente como una tabla de 9 × 9, compuesta por subtablas de 3 × 3 denominadas "regiones" (también se le llaman "cajas" o "bloques"). Algunas celdas ya contienen números, conocidos como "números dados" (o a veces "pistas"): El objetivo es rellenar las celdas vacías, con un número en cada una de ellas, de tal forma que cada columna, fila y región contenga los números 1–9 sólo una vez. Además, cada número de la solución aparece sólo una vez en cada una de las tres "direcciones", de ahí el "los números deben estar solos" que evoca el nombre del juego.

== Métodos de resolución ==

[[Image:Soduku ejemplo de trazado.png]]La región 3 × 3 de la esquina superior izquierda debe contener un 7.

La estrategia para resolver este rompecabezas se puede considerar como la combinación de tres procesos: escaneo, marcado y análisis.

=== Escaneo ===

Rastreando a lo largo y ancho los sietes localizados en cualquier lugar de la rejilla, el jugador puede eliminar todas las celdas vacías de la esquina superior izquierda que no pueden contener un 7. Esto deja sólo una celda posible (remarcada en verde).]]

=== Marcado ===

El escaneo viene a interrumpirse cuando no pueden descubrirse nuevos números. En este punto es necesario centrarse en algún análisis lógico. La mayoría encuentra útil guiar este análisis mediante el marcado de números candidatos en las celdas vacías. Hay dos notaciones populares: subíndices y puntos

En la notación de subíndice, los números candidatos se escriben en pequeño en las celdas. La desventaja es que los puzles originales se publican en periódicos que habitualmente no dejan demasiado espacio para acomodar más que unos pocos dígitos. Si se usa esta notación, los resolutores crean, a menudo, una copia más grande del puzzle y emplean un lápiz afilado.

La segunda notación es un patrón de puntos con un punto en la esquina superior izquierda representando un 1 y un punto en la esquina inferior derecha representando un 9. Esta notación tiene como ventaja que puede usarse en el puzle original. Se requiere destreza para el emplazamiento de los puntos, porque la existencia de puntos desplazados o marcas inadvertidas lleva, inevitablemente, a confusión y no son fáciles de borrar sin añadir más confusión.

=== Análisis ===

Hay dos aproximaciones principales:

*En '''eliminación''', el progreso se realiza mediante la sucesiva eliminación de números candidatos para una o más celdas, hasta dejar sólo una elección. Después de lograr cada respuesta, debe realizarse un nuevo escaneo (habitualmente comprobando el efecto del último número). Hay una serie de tácticas de eliminación. Una de las más comunes es el "borrado del candidato no coincidente". Las celdas con idéntica configuración de números candidatos se dice que coinciden si la cantidad de números candidatos en cada una es igual al número de celdas que los contienen. Por ejemplo lápiz y una goma. Esta aproximación puede ser desaprobada por puristas lógicos por demasiado [[Ensayo y error]] pero puede llegar a soluciones claras y rápidamente.

Idealmente, se necesita encontrar una combinación de técnicas que eviten alguno de los inconvenientes de los elementos de arriba. El recuento de regiones, filas y columnas puede resultar aburrido. Escribir números candidatos en celdas vacías puede consumir demasiado tiempo. La aproximación "y-si" puede ser confusa a menos que se sea bien organizado. El quid de la cuestión es encontrar una técnica que minimice el recuento, el marcado y e

== Resolución por ordenador ==

Algunos programas que emulan la resolución humana, permiten estimar la dificultad que tendrá un humano para encontrar la solución.

Para la implementación del resolvedor de sudokus utilizaremos la clase vector (fácilmente transformable en un array clásico) y tres funciones:

*Una llamada inicial: simplemente se encarga de llamar a la función recursiva. Para darle más utilidad retornará un booleano que indicará si se ha encontrado alguna solución al sudoku.
*Una función recursiva: se encarga del proceso de ir probando números. Incluye un parámetro de entrada/salida que indica si se ha encontrado alguna solución.
*El comprobador de validez: simplemente es una función que retorna un booleano indicando si un valor puede estar en un sitio indicado.

El vector contendrá enteros codificando como "0" los lugares a rellenar (los "-") y como su propio valor numérico los valores preestablecidos. Al final de la implementación del resolvedor se propone una acción que lee un sudoku como el propuesto arriba y lo transforma en la matriz numérica.

Además, utilizaremos las siguientes definiciones y constantes: 
<pre>const int FILS = 9; // Filas de un sudoku
const int COLS = 9; // Columnas de un sudoku

typedef vector< vector<int> > Matriz; // Definición de Matriz
</pre>
<br>Llamada inicial: 
<pre>bool rellenar(Matriz& v) {
bool tr = false;
rellenar(v, 0, 0, tr); // V y TR són parámetros de E/S
return tr;
}

</pre>
Función recursiva:nst Matriz& v, int fil, int col) { for (return false; } } return true; }</source>

Por si se tiene alguna duda, aquí se propone un método para leer un sudoku como el descrito arriba (caracteres de números y "-") y lo transforma en una matriz numérica de 0 (valores a introducir) y números (preestablecidos). 
<pre>// Precondición: V es una Matriz de tamaño FILS x COLS
void leer(Matriz& v) {
char x;
for (int i = 0; i < FILS; ++i) {
for (int c = 0; c < COLS; ++c) {
cin >> x;
v[i][c] = x=='-' ? 0:x&0xF;
}
}
}

</pre>
== Niveles de dificultad ==

Los programas informáticos que resuelven sudokus pueden estimar la dificultad que tiene un humano para encontrar la solución, basándose en la complejidad de las técnicas de resolución necesarias. Esta estimación permite a los editores adaptar sus sudokus para personas con diferente experiencia resolutoria. Algunas versiones "en línea" (online) también ofrecen varios niveles de dificultad.

== Construcción ==

Es posible establecer sudokus con más de una solución y también realizar tableros iniciales de sudoku sin solución, pero no se consideran rompecabezas sudoku apropiados; como la mayor parte de los rompecabezas lógicos, se espera una solución única.

La construcción de un rompecabeza sudoku puede ser realizada a mano eficientemente predeterminando las posiciones de los números dados y asignándoles valores para realizar un proceso deductivo. Tal indefinido dada se puede suponer que no tienen ningún valor particular, mientras se le da un valor diferente antes de que se complete la construcción, el encargado de resolver será capaz de hacer las mismas deducciones derivadas de tales supuestos, como en ese momento, el dado es muy mucho más definido como algo más. Esta técnica da al constructor un mayor control sobre el flujo de resolución de puzzles, líder en el alvistas solucionador de sudokus por compuestas íntegramente.

Los sudoku [[Nikoli]] se construyen a mano,y el nombre del autor aparece en los créditos junto a cada rompecabeza; los números dados siempre se encuentran en forma de un patrón simétrico. Los rompecabezas ''Number Place Challenger'' de Dell (véase Variantes más abajo) también citan los créditos del autor. Los rompecabezas sudoku que aparecen en la mayoría de los periódicos del Reino Unido aparentemente son generados por ordenador, pero emplean probables en sudokus generados por ordenador. El desafío para los programadores de sudokus es enseñar a un programa cómo construir rompecabezas inteligentes, de manera que no se puedan distinguir de aquellos realizados por humanos; Wayne Gould necesitó retocar su popular programa durante seis años para creer que había alcanzado ese nivel.

<br>

[[Category:Algoritmos]]

@@ Línea 50: / Línea 50: @@
 Los programas informáticos que resuelven sudokus pueden estimar la dificultad que tiene un humano para encontrar la solución, basándose en la complejidad de las técnicas de resolución necesarias. Esta estimación permite a los editores adaptar sus sudokus para personas con diferente experiencia resolutoria. Algunas versiones "en línea" (online) también ofrecen varios niveles de dificultad. <br>
 == Construcción ==
-[[Image: sudoku-3d.PNG|thumb|RIGHT|185x141px|Juego Sudoku]] <br>
+[[Image: sudoku-3d.PNG|thumb|RIGHT|185x141px|Juego Sudoku]]
 La construcción de un rompecabeza sudoku puede ser realizada a mano eficientemente predeterminando las posiciones de los números dados y asignándoles valores para realizar un proceso deductivo. <br>
 Tal indefinido dados se puede suponer que no tienen ningún valor particular, mientras se le da un valor diferente antes de que se complete la construcción, el encargado de resolver será capaz de hacer las mismas deducciones derivadas de tales supuestos, como en ese momento, el dado es muy mucho más definido como algo más. Esta técnica da al constructor un mayor control sobre el flujo de resolución de puzzles, líder en el alvistas solucionador de sudokus por compuestas íntegramente. <br>
 El desafío para los programadores de sudokus es enseñar a un programa cómo construir rompecabezas inteligentes, de manera que no se puedan distinguir de aquellos realizados por humanos; Wayne Gould necesitó retocar su popular programa durante seis años para creer que había alcanzado ese nivel. <br>
 == Fuentes ==
-*[http://www.websudoku.com Sitio Oficial Sudoku] <br>
+*[http://www.websudoku.com Sitio Oficial Sudoku]
-*[http://www.sudoku-online.org Sudoku y Puzzles] <br>
+*[http://www.sudoku-online.org Sudoku y Puzzles]
-*[http://www.publispain.com/sudoku/que_es_sudoku.html Sudoku] <br>
+*[http://www.publispain.com/sudoku/que_es_sudoku.html Sudoku]
-*[http://www.playsudoku.biz/historia-sudoku.aspx Historia Sudoku] <br>
+*[http://www.playsudoku.biz/historia-sudoku.aspx Historia Sudoku]
 [[Category:Algoritmos]]

@@ Línea 1: / Línea 1: @@
 {{Definición|Nombre=Sudoku backtracking|imagen=sudoku.jpg|concepto= Es un rompecabezas matemático basado en la búsqueda de la combinación numérica perfecta. El término proviene de la lengua japonesa (数独, sūdoku). }}
 <br>
-'''Sudoku.''' Entretenimiento que se inicia en los [[Estados Unidos]] y se populariza en [[Japón]] en [[1986]].Desde aquí se produce su innegable salto al ámbito internacional en el [[2005]], fecha en que numerosos periódicos lo comienzan a publicar en su sección de pasatiempos. El juego es una parrilla de crucigrama de 9 x 9 con 81 cuadritos que se agrupan en nueve cuadrados interiores con una dimensión de 3 x 3. Si la solución al juego es única, el Sodoku está bien planteado. <br>
+'''Sudoku.''' Entretenimiento que se inicia en los [[Estados Unidos]] y se populariza en [[Japón]] en [[1986]]. Desde aquí se produce su innegable salto al ámbito internacional en el [[2005]], fecha en que numerosos periódicos lo comienzan a publicar en su sección de pasatiempos. El juego es una parrilla de crucigrama de 9 x 9 con 81 cuadritos que se agrupan en nueve cuadrados interiores con una dimensión de 3 x 3. Si la solución al juego es única, el Sodoku está bien planteado. <br>
 Es fácil de explicar y desarrolla el razonamiento lógico, en eso radica su popularidad y el hecho de que hoy cientos de páginas Web contienen información sobre como resolverlos. <br>
 ==Antecedentes  históricos ==
@@ Línea 58: / Línea 58: @@
 *[http://www.sudoku-online.org Sudoku y Puzzles] <br>
 *[http://www.publispain.com/sudoku/que_es_sudoku.html Sudoku] <br>
 *[http://www.playsudoku.biz/historia-sudoku.aspx Historia Sudoku] <br>
 [[Category:Algoritmos]]

@@ Línea 1: / Línea 1: @@
-{{Referencia}}Sudoku (en japonés: 数独, sūdoku) es un pasatiempo que se popularizó en Japón en 1986, y se dio a conocer en el ámbito internacional en 2005. El objetivo del sudoku es rellenar una cuadrícula de 9 × 9 celdas (81 casillas) dividida en subcuadrículas de 3 × 3 (también llamadas &quot;cajas&quot; o &quot;regiones&quot;) con las cifras del 1 al 9 partiendo de algunos números ya dispuestos en algunas de las celdas. Aunque se podrían usar colores, letras, figuras, se conviene en usar números para mayor claridad. Lo que importa, en todo caso, es que sean nueve elementos diferenciados. No se debe repetir ninguna cifra en una misma fila, columna o subcuadrícula. Un sudoku está bien planteado si la solución es única. La resolución del problema requiere paciencia y ciertas dotes lógicas.
+{{Mejorar|poner las fuentes}}'''Sudoku''' (en japonés: 数独, sūdoku) es un pasatiempo que se popularizó en [[Japón|Japón]] en [[1986|1986]], y se dio a conocer en el ámbito internacional en [[2005|2005]]. El objetivo del sudoku es rellenar una cuadrícula de 9 × 9 celdas (81 casillas) dividida en subcuadrículas de 3 × 3 (también llamadas "cajas" o "regiones") con las cifras del 1 al 9 partiendo de algunos números ya dispuestos en algunas de las celdas. Aunque se podrían usar colores, letras, figuras, se conviene en usar números para mayor claridad. Lo que importa, en todo caso, es que sean nueve elementos diferenciados. No se debe repetir ninguna cifra en una misma fila, columna o subcuadrícula. Un sudoku está bien planteado si la solución es única. La resolución del problema requiere paciencia y ciertas dotes lógicas.
 La solución de un sudoku siempre es un cuadrado latino, aunque el recíproco en general no es cierto ya que el sudoku establece la restricción añadida de que no se puede repetir un mismo número en una región.
@@ Línea 7: / Línea 7: @@
 == Reglas y terminología  ==
-El sudoku se presenta normalmente como una tabla de 9&nbsp;×&nbsp;9, compuesta por subtablas de 3&nbsp;×&nbsp;3 denominadas &quot;regiones&quot; (también se le llaman &quot;cajas&quot; o &quot;bloques&quot;). Algunas celdas ya contienen números, conocidos como &quot;números dados&quot; (o a veces &quot;pistas&quot;): El objetivo es rellenar las celdas vacías, con un número en cada una de ellas, de tal forma que cada columna, fila y región contenga los números 1–9 sólo una vez. Además, cada número de la solución aparece sólo una vez en cada una de las tres &quot;direcciones&quot;, de ahí el &quot;los números deben estar solos&quot; que evoca el nombre del juego.
+El sudoku se presenta normalmente como una tabla de 9&nbsp;×&nbsp;9, compuesta por subtablas de 3&nbsp;×&nbsp;3 denominadas "regiones" (también se le llaman "cajas" o "bloques"). Algunas celdas ya contienen números, conocidos como "números dados" (o a veces "pistas"): El objetivo es rellenar las celdas vacías, con un número en cada una de ellas, de tal forma que cada columna, fila y región contenga los números 1–9 sólo una vez. Además, cada número de la solución aparece sólo una vez en cada una de las tres "direcciones", de ahí el "los números deben estar solos" que evoca el nombre del juego.
 == Métodos de resolución  ==
-[[Image:Soduku ejemplo de trazado.png]]La región 3&nbsp;×&nbsp;3 de la esquina superior izquierda debe contener un 7.
+La región 3&nbsp;×&nbsp;3 de la esquina superior izquierda debe contener un 7.
 La estrategia para resolver este rompecabezas se puede considerar como la combinación de tres procesos: escaneo, marcado y análisis.
@@ Línea 31: / Línea 31: @@
 Hay dos aproximaciones principales:
-*En '''eliminación''', el progreso se realiza mediante la sucesiva eliminación de números candidatos para una o más celdas, hasta dejar sólo una elección. Después de lograr cada respuesta, debe realizarse un nuevo escaneo (habitualmente comprobando el efecto del último número). Hay una serie de tácticas de eliminación. Una de las más comunes es el &quot;borrado del candidato no coincidente&quot;. Las celdas con idéntica configuración de números candidatos se dice que coinciden si la cantidad de números candidatos en cada una es igual al número de celdas que los contienen. Por ejemplo lápiz y una goma. Esta aproximación puede ser desaprobada por puristas lógicos por demasiado [[Ensayo y error]] pero puede llegar a soluciones claras y rápidamente.
+*En '''eliminación''', el progreso se realiza mediante la sucesiva eliminación de números candidatos para una o más celdas, hasta dejar sólo una elección. Después de lograr cada respuesta, debe realizarse un nuevo escaneo (habitualmente comprobando el efecto del último número). Hay una serie de tácticas de eliminación. Una de las más comunes es el "borrado del candidato no coincidente". Las celdas con idéntica configuración de números candidatos se dice que coinciden si la cantidad de números candidatos en cada una es igual al número de celdas que los contienen. Por ejemplo lápiz y una goma. Esta aproximación puede ser desaprobada por puristas lógicos por demasiado Ensayo y error pero puede llegar a soluciones claras y rápidamente.
-Idealmente, se necesita encontrar una combinación de técnicas que eviten alguno de los inconvenientes de los elementos de arriba. El recuento de regiones, filas y columnas puede resultar aburrido. Escribir números candidatos en celdas vacías puede consumir demasiado tiempo. La aproximación &quot;y–si&quot; puede ser confusa a menos que se sea bien organizado. El quid de la cuestión es encontrar una técnica que minimice el recuento, el marcado y e
+Idealmente, se necesita encontrar una combinación de técnicas que eviten alguno de los inconvenientes de los elementos de arriba. El recuento de regiones, filas y columnas puede resultar aburrido. Escribir números candidatos en celdas vacías puede consumir demasiado tiempo. La aproximación "y–si" puede ser confusa a menos que se sea bien organizado. El quid de la cuestión es encontrar una técnica que minimice el recuento, el marcado y e
 == Resolución por ordenador  ==
@@ Línea 45: / Línea 45: @@
 *El comprobador de validez: simplemente es una función que retorna un booleano indicando si un valor puede estar en un sitio indicado.
-El vector contendrá enteros codificando como &quot;0&quot; los lugares a rellenar (los &quot;–&quot;) y como su propio valor numérico los valores preestablecidos. Al final de la implementación del resolvedor se propone una acción que lee un sudoku como el propuesto arriba y lo transforma en la matriz numérica.
+El vector contendrá enteros codificando como "0" los lugares a rellenar (los "–") y como su propio valor numérico los valores preestablecidos. Al final de la implementación del resolvedor se propone una acción que lee un sudoku como el propuesto arriba y lo transforma en la matriz numérica.
 Además, utilizaremos las siguientes definiciones y constantes:&nbsp;
@@ Línea 63: / Línea 63: @@
 Función recursiva:nst Matriz&amp; v, int fil, int col) { for (return false; } } return true; }&lt;/source&gt;
-Por si se tiene alguna duda, aquí se propone un método para leer un sudoku como el descrito arriba (caracteres de números y &quot;–&quot;) y lo transforma en una matriz numérica de 0 (valores a introducir) y números (preestablecidos).&nbsp;
+Por si se tiene alguna duda, aquí se propone un método para leer un sudoku como el descrito arriba (caracteres de números y "–") y lo transforma en una matriz numérica de 0 (valores a introducir) y números (preestablecidos).&nbsp;
 <pre>// Precondición: V es una Matriz de tamaño FILS x COLS
 void leer(Matriz&amp; v) {
@@ Línea 78: / Línea 78: @@
 == Niveles de dificultad  ==
-Los programas informáticos que resuelven sudokus pueden estimar la dificultad que tiene un humano para encontrar la solución, basándose en la complejidad de las técnicas de resolución necesarias. Esta estimación permite a los editores adaptar sus sudokus para personas con diferente experiencia resolutoria. Algunas versiones &quot;en línea&quot; (online) también ofrecen varios niveles de dificultad.
+Los programas informáticos que resuelven sudokus pueden estimar la dificultad que tiene un humano para encontrar la solución, basándose en la complejidad de las técnicas de resolución necesarias. Esta estimación permite a los editores adaptar sus sudokus para personas con diferente experiencia resolutoria. Algunas versiones "en línea" (online) también ofrecen varios niveles de dificultad.
 == Construcción  ==