Desafío Sudoku
#3 Solución de unkas
Ver código
|
Ver comentarios (6)
|
Descargar código
Fecha: 04 febrero 2006
Tamaño: 200332 caracteres
Comentarios: 6
Solución online:
http://unkas.homeip.net/sudoku
Premios 
Recomendado PPT!
Valoración
9.67
(12 votos)
"Sudoku realizado utilizando objetos en PHP, ya que soy programador en Java me resultaba más intuitivo la resolución de este modo. Permito crear sudokus por formulario o por archivo de texto (el del desafio).
Espero que os guste..."
Valora esta solución
<?php
/**
* SUDOKU
* Autor: 'unkas' <carlos.alonso.gonzalez@gmail.com>
* Fecha: 2006-02-04
* Referencia: http://php-hispano.net/desafios/10
* http://unkas.no-ip.info/sudoku
*
*
* Como buen programador de Java que soy he utilizado Clases para la solución de
* este problema, en concreto dos:
* - Celda: clase que guarda todos los atributos que debe contener una celda para
* la resolución del problema (valor, posibles, reducido, fila, bloque...), implementando
* además los métodos necesarios para trabajar con estos atributos.
*
* - Sudoku: clase encargada de crear, validar, solucionar, representar un sudoku. El
* atributo en sí 'sudoku', es una matriz de n x n objetos Celda. Esta clase implementa
* todos los métodos necesarios para trabajar con sudokus.
*
* En definitiva, tenemos una matriz (n x n) donde cada valor es un objeto de tipo Celda,
* a partir de aquí se empieza a trabajar en la solución de esta, la cual sigue los siguientes
* pasos:
* 1º. Inicializar: consiste en asignar todos los valores posibles que no contiene valor.
*
* 2º. Reducción: consiste en borrar todos los valores posibles de las celdas sin valor, que
* se hayan repetido en la fila, columna o bloque.
*
* 3º. Modificar: encontrar aquellos elementos posibles que solo se repiten una vez, ya sea en
* una fila, una columna o un bloque.
*
* 4º. Conjetura: si no hemos obtenido la solución al problema tras estos pasos, procedemos a
* suponer un numero posible en una celda sin valor, e intentamos resolver el sudoku.
*
* Aplicando estos pasos en bucles con pseudocodigo sería algo como:
* inicialiar();
* hacer {
* hacer
* reducir();
* modificar();
* mientras (no_solucionado o no cambios)
*
* if (no_solucionado)
conjetura();
* }mientras(no_solucionado)
*
* Con la combinación de estos algoritmos he obtenido los mejores tiempo de respuesta,
* además de utilizar una matriz para el sudoku en vez de un array de una dimensión (también
* hize la prueba), el cual resulta más lento de acceder a los datos.
*
* Espero que os guste la solución, las clases incluyen muchos métodos algunos son solo
* para validación, visualización, captura de datos,
*/
/**
* Clase celda el cual contiene todos los atributos que debe tener una celda para
* poder solucionar un sudoku, además de los métodos para gestionarlos
*/
class Celda
{
private $valor; //variable que almacena el valor de la celda (0 si no tiene)
private $posibles; //array donde se guardan los posibles valores aplicables a la celda
private $reducido; //vble para recordar que una celda ha sido ya reducida
private $nivel_conjetura; //nivel que se obtuvo el valor, o cambio, para conjeturas
private $inicial; //vble para saber si es una celda dada inicial
private $fila; //fila de la celda
private $columna; //columna de la celda
private $bloque; //numero de bloque donde esta situada la celda
private $bloque_fila; //fila del bloque
private $bloque_col; //columna del bloque
/**
* Constructor inicializamos algunos datos
**/
public function Celda() {
$this->valor = (int) 0;
$this->reducido = false;
$this->inicial = false;
$this->nivel_conjetura = (int) 0;
$this->posibles = array();
}
public function setValor($valor) {
$this->valor = (int) $valor;
}
public function getValor() {
return $this->valor;
}
/**
* Metodo para crear todos los valores posibles de una celda, si es inicial seran
* todos 0, sino los valores [1][2]...[n], estarna a 1
*/
public function setPosibles($numeros) {
if ($this->getInicial())
$this->posibles = array_fill(1, $numeros, 0);
else
$this->posibles = array_fill(1, $numeros, 1);
}
/**
* Metodo que devuelve un array con los valores posibles
*/
public function getPosibles() {
return @array_keys($this->posibles, 1);
}
/**
* Metodo que valida si un numero es posible en la celda
**/
public function esPosible($pos) {
if (@$this->posibles[$pos])
return true;
else
return false;
}
/**
* Metodo para reducir un numero posible, si solo queda ese valor
* automáticamente se asigna este al valor de la celda, retornando true
*/
public function reducePosibles($posicion, $nivel_conjetura) {
if (@$this->posibles[$posicion]) {
$this->posibles[$posicion] = 0;
$this->setNivelConjetura($nivel_conjetura);
}
if (count($this->getPosibles()) == 1) {
$this->valor = implode("", $this->getPosibles());
return true;
}
else {
return false;
}
}
public function setReducido($reducido) {
$this->reducido = $reducido;
}
public function getReducido() {
return $this->reducido;
}
public function setNivelConjetura($nivel_conjetura) {
$this->nivel_conjetura = (int) $nivel_conjetura;
}
public function getNivelConjetura() {
return $this->nivel_conjetura;
}
public function setInicial($inicial) {
$this->inicial = $inicial;
}
public function getInicial() {
return $this->inicial;
}
public function setFila($fila) {
$this->fila = (int) $fila;
}
public function getFila() {
return $this->fila;
}
public function setColumna($columna) {
$this->columna = (int) $columna;
}
public function getColumna() {
return $this->columna;
}
public function setBloque($bloque) {
$this->bloque = (int) $bloque;
}
public function getBloque() {
return $this->bloque;
}
public function setBloqueFila($bloque_fila) {
$this->bloque_fila = (int) $bloque_fila;
}
public function getBloqueFila() {
return $this->bloque_fila;
}
public function setBloqueColumna($bloque_columna) {
$this->bloque_columna = (int) $bloque_columna;
}
public function getBloqueColumna() {
return $this->bloque_columna;
}
/**
* Metodo devolver un string para pintar pantalla (consola)
*/
public function toString() {
if ($this->getValor()) {
return ' '.$this->getValor().' ';
}
if ($this->getPosibles()) {
return implode(" ",$this->posibles());
}
return ' ? ';
}
/**
* Metodo devolver un string para pintar pantalla (HTML)
*/
public function toHTML() {
if ($this->getInicial()) {
return '<td width="20" valign="middle" align="center" bgcolor="#33CCFF"><b>'.$this->getValor().'</b></td>';
}
if ($this->getValor()) {
return '<td width="20" valign="middle" align="center" bgcolor="#33FF00"><b>'.$this->getValor().'</b></td>';
}
if ($this->getPosibles()) {
return '<td width="20" valign="middle" align="center">'.implode(",",array_keys($this->posibles, 1)).'</td>';
}
return '<td width="20" valign="middle" align="center">?</td>';
}
}
/***********************************************************************/
/**
* Clase sudoku, el cual contiene todos los metodos para crear, validar, pintar
* y solucionar un sudoku, siguiendo el algoritmo anteriormente citado
*/
class Sudoku
{
private $sudoku; //matriz que almacenara todos los objetos celda
private $bloques; //vble que almacena el nº de bloques del sudoku
private $reducido; //vble booleana para saber si se ha reducido el sudoku
/**
* Constructor, solo inicializa las variables
*/
public function Sudoku() {
$this->sudoku = array();
$this->bloques = (int) 0;
$this->reducido = false;
}
/**
* Metodo para pasar un sudoku como matriz
*/
public function setSudoku($sudoku) {
$this->sudoku = $sudoku;
$this->sudokuOK();
$this->setBloque();
}
/**
* Metodo para pasar un sudoku archivo, su funcionamiento consiste en leer el
* archivo linea a linea e ir inicializando el sudoku, para después validar
* los datos que contiene el sudoku
*/
public function setSudokuPath($path) {
$this->sudoku = array();
if (!file_exists($path)) {
throw new Exception('ERROR: el archivo no existe...');
}
if (!($fp = @fopen($path, "r"))) {
throw new Exception('ERROR: el archivo índicado no se puede leer...');
}
while (!feof($fp)) {
$aux = array();
foreach(explode(" ",fgets($fp)) as $v) {
if (ereg("[0-9]", $v)) {
$celda = new Celda();
$celda->setValor($v);
$celda->setInicial(true);
$aux[] = $celda;
}
else if (ereg("[*]|[-]|[?]", $v)) {
$celda = new Celda();
$celda->setValor(0);
$aux[] = $celda;
}
}
$this->sudoku[]=$aux;
}
fclose($fp);
//validamos que todas las columnas tengan el mismo tamaño que la columna
for ($i=0; $i < count($this->sudoku); $i++) {
if (count($this->sudoku) != count($this->sudoku[$i])) {
throw new Exception('ERROR: el sudoku es invalido. Filas ['.count($this->sudoku).'] != Columnas ['.count($this->sudoku[$i]).'].');
}
}
//validamos el sudoku, con este método
$this->sudokuOK();
$this->setBloque();
}
/**
* Metodo para captuar todos los parametros de un sudoku creado en HTML, validandolo
* e iniciandolo correctamente
*/
public function setSudokuHTML($tamanio, $valores) {
for($fila=0; $fila < $tamanio; $fila++) {
$aux = array();
for($col=0; $col < $tamanio; $col++) {
if (isset($valores['celda'.$fila.$col]) && ereg("[0-9]", $valores['celda'.$fila.$col])) {
$celda = new Celda();
$celda->setValor($valores['celda'.$fila.$col]);
$celda->setInicial(true);
}
else {
$celda = new Celda();
$celda->setValor(0);
}
$aux[] = $celda;
}
$this->sudoku[] = $aux;
}
$this->sudokuOK();
$this->setBloque();
}
public function getSudoku() {
return $this->sudoku;
}
/**
* Metodo para obtener el numero de bloques del sudoku, ademas de
* comprobar que sea estandar 4x4, 9x9, 16x16, 25x25...
**/
private function setBloque() {
$this->bloques = (int) sqrt(count($this->sudoku));
if ($this->bloques * $this->bloques != count($this->sudoku)) {
throw new Exception('ERROR: el sudoku no es estandar: '.count($this->sudoku).' x '.count($this->sudoku).'.');
}
}
public function getBloque() {
return $this->bloques;
}
/**
* Metodo para rellenear todos los valores que faltaran de poner al sudoku (bloques,
* posibles, fila, columna...)
*/
private function inicializar() {
for ($fila=0; $fila < count($this->sudoku); $fila++) {
for ($col=0; $col < count($this->sudoku); $col++) {
$bloque_fila=0;
$v = $fila;
while (($v = $v - $this->bloques) >= 0) {
$bloque_fila++;
}
$bloque_col=0;
$v = $col;
while(($v = $v - $this->bloques) >= 0) {
$bloque_col++;
}
$this->sudoku[$fila][$col]->setPosibles(count($this->sudoku));
$this->sudoku[$fila][$col]->setFila($fila);
$this->sudoku[$fila][$col]->setColumna($col);
$this->sudoku[$fila][$col]->setBloqueFila($bloque_fila);
$this->sudoku[$fila][$col]->setBloqueColumna($bloque_col);
$this->sudoku[$fila][$col]->setBloque($bloque_fila * $this->bloques + $bloque_col);
}
}
}
/**
* Metodo para solucionar el sudoku, invocando a otros métodos
*/
public function getSolucion() {
$this->inicializar();
$this->solucion();
if (!$this->validaSolucion()) {
$this->conjetura();
}
}
/**
* Metodo para solucionar el sudoku iterativamente, mostrando resultados por pantalla
* en cada paso realizado.
*/
public function getSolucionIterativa() {
$this->inicializar();
echo '<b>SUDOKU INICIAL:</b><br/>'.$this->toHTML().'<br/>';
$this->solucionIterativa();
if (!$this->validaSolucion()) {
$this->conjeturaIterativa();
}
}
/**
* Metodo para realizar una solucion sencilla del sudoku (reducción, modificar)
**/
private function solucion($nivel=0) {
$fin = false;
do {
if (!$this->reduce($nivel) && !$this->modifica($nivel)) {
$fin=true;
}
}while(!$this->esSolucion() && !$fin);
}
/**
* Metodo para realizar una solucion iterativa sencilla del sudoku (reducción, modificar)
**/
private function solucionIterativa($nivel=0) {
$fin = false;
do {
if ($this->reduce($nivel)) {
echo '<b>SUDOKU REDUCIDO:</b><br/>'.$this->toHTML().'<br/>';
}
else if ($this->modifica($nivel)) {
echo '<b>SUDOKU MODIFICADO:</b><br/>'.$this->toHTML().'<br/>';
}
else {
echo '<b>SUDOKU OBTENIDO:</b><br/>'.$this->toHTML().'<br/>';
$fin = true;
}
}while(!$this->esSolucion() && !$fin);
}
/**
* Metodo que encuentra una casilla con valor y reduce posibles en su fila, columna
* y bloque que le rodea, para cada uno de estos pasos invoca a su correspondiente
* método
**/
private function reduce($nivel) {
$this->reducido = false;
for ($fila=0; $fila < count($this->sudoku); $fila++) {
for ($col=0; $col < count($this->sudoku); $col++) {
if ($this->sudoku[$fila][$col]->getValor() && !$this->sudoku[$fila][$col]->getReducido()) {
$this->reduceFila($this->sudoku[$fila][$col], $nivel);
$this->reduceColumna($this->sudoku[$fila][$col], $nivel);
$this->reduceBloque($this->sudoku[$fila][$col], $nivel);
$this->sudoku[$fila][$col]->setReducido(true);
}
}
}
return $this->reducido;
}
/**
* Metodo para reducir una fila dada una celda con un valor
**/
private function reduceFila($celda, $nivel) {
for ($col=0; $col < count($this->sudoku); $col++) {
if (!$this->sudoku[$celda->getFila()][$col]->getValor()) {
if ($this->sudoku[$celda->getFila()][$col]->reducePosibles($celda->getValor(), $nivel)) {
$this->reducido = true;
}
}
}
}
/**
* Metodo para reducir una columna dada una celda con un valor
**/
private function reduceColumna($celda, $nivel) {
for ($fila=0; $fila < count($this->sudoku); $fila++) {
if (!$this->sudoku[$fila][$celda->getColumna()]->getValor()) {
if ($this->sudoku[$fila][$celda->getColumna()]->reducePosibles($celda->getValor(), $nivel)) {
$this->reducido = true;
}
}
}
}
/**
* Metodo para reducir un bloque dada una celda con un valor
**/
private function reduceBloque($celda, $nivel) {
for ($fila=$celda->getBloqueFila()*$this->bloques; $fila < ($celda->getBloqueFila() * $this->bloques) + $this->bloques; $fila++) {
for ($col=$celda->getBloqueColumna()*$this->bloques; $col < ($celda->getBloqueColumna() * $this->bloques) + $this->bloques; $col++) {
if (!$this->sudoku[$fila][$col]->getValor()) {
if ($this->sudoku[$fila][$col]->reducePosibles($celda->getValor(), $nivel)) {
$this->reducido = true;
}
}
}
}
}
/**
* Metodo para modificar el sudoku, buscando aquellos posibles que solo tengan
* un valor, en una fila, una columna o un bloque. Cada uno de estos pasos invoca
* a su correspondiente método
**/
private function modifica($nivel) {
if ($this->modificaFila($nivel) || $this->modificaColumna($nivel) || $this->modificaBloque($nivel)) {
return true;
}
else {
return false;
}
}
/**
* Método para rastrear las filas, si se encontramos un valor que solo este en una celda
*/
private function modificaFila($nivel) {
$modificado = false;
for ($fila=0; $fila < count($this->sudoku); $fila++) {
$aux = array_fill (1, count($this->sudoku), 0);
for ($col=0; $col < count($this->sudoku); $col++) {
if (!$this->sudoku[$fila][$col]->getValor()) {
foreach($this->sudoku[$fila][$col]->getPosibles() as $v) {
$aux[$v]++;
}
}
}
if ($aux = array_keys($aux, 1)) {
for ($col=0; $col < count($this->sudoku); $col++) {
if (!$this->sudoku[$fila][$col]->getValor()) {
for($i=0; $i < count($aux); $i++) {
if ($this->sudoku[$fila][$col]->esPosible($aux[$i])) {
$this->sudoku[$fila][$col]->setValor($aux[$i]);
$this->sudoku[$fila][$col]->setNivelConjetura($nivel);
$modificado = true;
}
}
}
}
}
}
return $modificado;
}
/**
* Método para rastrear las columnas, si se encontramos un valor que solo este en una celda
*/
private function modificaColumna($nivel) {
$modificado = false;
for ($col=0; $col < count($this->sudoku); $col++) {
$aux = array_fill(1, count($this->sudoku), 0);
for ($fila=0; $fila < count($this->sudoku); $fila++) {
if (!$this->sudoku[$fila][$col]->getValor()) {
foreach($this->sudoku[$fila][$col]->getPosibles() as $v) {
$aux[$v]++;
}
}
}
if ($aux = array_keys($aux, 1)) {
for ($fila=0; $fila < count($this->sudoku); $fila++) {
if (!$this->sudoku[$fila][$col]->getValor()) {
for($i=0; $i < count($aux); $i++) {
if ($this->sudoku[$fila][$col]->esPosible($aux[$i])) {
$this->sudoku[$fila][$col]->setValor($aux[$i]);
$this->sudoku[$fila][$col]->setNivelConjetura($nivel);
$modificado = true;
}
}
}
}
}
}
return $modificado;
}
/**
* Método para rastrear los bloques, si se encontramos un valor que solo este en una celda
*/
private function modificaBloque($nivel) {
$modificado = false;
for ($i=0; $i < $this->bloques; $i++) {
for ($j=0; $j < $this->bloques; $j++) {
$aux = array_fill(1, count($this->sudoku), 0);
for($fila=$i*$this->bloques; $fila < $this->bloques + ($i*$this->bloques); $fila++) {
for($col=$j*$this->bloques; $col < $this->bloques + ($j*$this->bloques); $col++) {
if (!$this->sudoku[$fila][$col]->getValor()) {
foreach($this->sudoku[$fila][$col]->getPosibles() as $v) {
$aux[$v]++;
}
}
}
}
if ($aux = array_keys($aux, 1)) {
for($fila=$i*$this->bloques; $fila < $this->bloques + ($i*$this->bloques); $fila++) {
for($col=$j*$this->bloques; $col < $this->bloques + ($j*$this->bloques); $col++) {
if (!$this->sudoku[$fila][$col]->getValor()) {
for($k=0; $k < count($aux); $k++) {
if ($this->sudoku[$fila][$col]->esPosible($aux[$k])) {
$this->sudoku[$fila][$col]->setValor($aux[$k]);
$this->sudoku[$fila][$col]->setNivelConjetura($nivel);
$modificado = true;
}
}
}
}
}
}
}
}
return $modificado;
}
/**
* Metodo recursivo para suponer un valor en la celda con menores posibilidades (numeros posibles),
* si no alcanzamos la solución con los anteriores pasos. Si se llega a un error, retrocedemos
* deshaciendo la conjetura y todos los cambios que puedieran suponer, para eso utilizamos
* la variable nivel, la cual nos indica el nivel de conjetura en que nos encontramos
*/
private function conjetura($nivel=0) {
//incrementamos el nivel de conjetura
$nivel++;
//buscamos la celda del sudoku con menos posibilidades (numeros)
$celda = $this->menorPosible();
$this->sudoku[$celda->getFila()][$celda->getColumna()]->setNivelConjetura($nivel);
foreach ($this->sudoku[$celda->getFila()][$celda->getColumna()]->getPosibles() as $v) {
$this->sudoku[$celda->getFila()][$celda->getColumna()]->setValor($v);
if ($this->solucionaConjetura($nivel)) {
if ($this->celdasRestantes() != 0) {
if ($this->conjeturaOK() && $this->conjetura($nivel)) {
return true;
}
else {
$this->deshacerConjetura($nivel);
}
}
else if ($this->validaSolucion()) {
return true;
}
else {
$this->deshacerConjetura($nivel);
}
}
else {
$this->deshacerConjetura($nivel);
}
}
return false;
}
/**
* Metodo recursivo para suponer un valor en la celda con menores posibilidades (numeros posibles),
* si no alcanzamos la solución con los anteriores pasos. Si se llega a un error, retrocedemos
* deshaciendo la conjetura y todos los cambios que puedieran suponer, para eso utilizamos
* la variable nivel, la cual nos indica el nivel de conjetura en que nos encontramos.
* En este caso mostramos por pantalla las conjeturas supuestas.
*/
private function conjeturaIterativa($nivel=0) {
$nivel++;
$celda = $this->menorPosible();
$this->sudoku[$celda->getFila()][$celda->getColumna()]->setNivelConjetura($nivel);
foreach ($this->sudoku[$celda->getFila()][$celda->getColumna()]->getPosibles() as $v) {
$this->sudoku[$celda->getFila()][$celda->getColumna()]->setValor($v);
echo '<b>SUDOKU CONJETURA ['.$celda->getFila().']['.$celda->getColumna().'] = '.$v.'. Nivel Conjetura = '.$nivel.':</b><br/>'.$this->