Quem anima desafio?

[Oenning 0]

Então, o meu está pronto. Por mim eu posto hoje, mas se o Denis e/ou o Evandro precisarem de mais uma semana, eu apoio, assim posso melhorar o meu.

[Evandro Oliveira 331]

o meu resolve apenas sudoku's fáceis =\

 

gostaria de mais uma semana para implementar o último módulo que falta, tenho ele na cabeça, mas não consigo passar para a codificação

[Denis Lins 0]

aaaaaaaaeeeeewwww!

 

eu acabei de acabar.

 

Mas acho legal mais uma semana tambem, ajuda bastante.

 

Edit: e tambem seria injusto, ja que nem todos terminaram ainda.

 

//eu apoio, assim posso melhorar o meu. [2]

[João Batista Neto 448]

Como os três participantes se manifestaram favoráveis ao adiamento da avaliação em mais uma semana, marquemos a entrega dos códigos para segunda feira, 8 de março.

 

Sucesso a todos.

[Denis Lins 0]

Então galera, negócio é o seguinte.

 

Eu humildemente venho aqui dizer que meu script não está pronto.

 

Eu quando propus este desafio, na verdade eu queria um teste para ver se eu conseguiria entrar na empresa ou não.

 

Hoje já na empresa, e na condição de estagiário, ficou muito apertado o meu tempo.

 

Mas, como aceitei participar do desafio, isso pouco importa.

 

Eu até tenho a ideia na cabeça, mas como é muito complicada, não tive tempo para passar para o código.

 

Apesar também de saber que minha lógica tinha alguns erros.

 

Mas enfim, quem ganhar, ganhará por mérito, por conseguir criar um script difícil, que requer muito tempo e MUITA lógica, apesar de não requerer tanto conhecimento do php.

 

Desejando sorte aos demais competidores, posto aqui o meu código, intacto, do mesmo jeito que deixei.

 

Inclusive com comentários, e com uma gambiarrazinha na função getPossibleValue(). Apesar da minha campanha, todo mundo é humano ne

 

Particularmente, acho que o Oenning irá ganhar. Nada contra o Evandro, torcida mesmo

<?phperror_reporting(E_ALL | E_STRICT);ini_set('display_errors' , 1);define('X', NULL);$sudoku = array(	//	   0   1   2   3   4   5   6   7   8			array( 5 , 3 , X , X , 7 , X , X , X , X ), //0	array( 6 , X , X , 1 , 9 , 5 , X , X , X ), //1	array( X , 9 , 8 , X , X , X , X , 6 , X ), //2	array( 8 , X , X , X , 6 , X , X , X , 3 ), //3	array( 4 , X , X , 8 , X , 3 , X , X , 1 ), //4	array( 7 , X , X , X , 2 , X , X , X , 6 ), //5	array( X , 6 , X , X , X , X , 2 , 8 , X ), //6	array( X , X , X , 4 , 1 , 9 , X , X , 5 ), //7	array( X , X , X , X , 8 , X , X , 7 , 9 ), //8	//     0   1   2   3   4   5   6   7   8);dlSolveSudoku::loadGame($sudoku);class dlSolveSudoku{		private static $numbers, $game, $possibles;	public final static function loadGame($game)	{		self::$numbers = range(1, 9);		self::$game = $game;		self::checkArray();	}		private final static function filterArray($array)	{		$array = array_filter($array);		$newArray = array_unique($array);		return (count($array) == count($newArray));	}		private final static function getRow($index)	{		for($i = 0; $i <= 8; $i++)		{			$array[] = self::$game[$i][$index];		}		return $array;	}		private final static function getBlock($index)	{		$x = $index % 3 * 3;		$y = floor($index / 3) * 3;		for($i = 0; $i < 3; $i++)		{			for($w = 0; $w < 3; $w++)			{				$block[] = self::$game[$y + $w][$x + $i];			}          		}		return $block;	}		private final static function getPossibleValue($line, $row, $number)	{		switch($line)		{			case 0:			case 1:			case 2:				switch($row)				{					case 0:					case 1:					case 2:						$block = 0;							break;					case 3:					case 4:					case 5:						$block = 1;							break;					case 6:					case 7:					case 8:						$block = 2;							break;				}					break;			case 3:			case 4:			case 5:				switch($row)				{					case 0:					case 1:					case 2:						$block = 3;							break;					case 3:					case 4:					case 5:						$block = 4;							break;					case 6:					case 7:					case 8:						$block = 5;							break;				}					break;			case 6:			case 7:			case 8:				switch($row)				{					case 0:					case 1:					case 2:						$block = 6;							break;					case 3:					case 4:					case 5:						$block = 7;							break;					case 6:					case 7:					case 8:						$block = 8;							break;				}					break;		}		if(!in_array($number, self::$game[$line]) && !in_array($number, self::getRow($row)) && !in_array($number, self::getBlock($block)))		{			self::$possibles[$line][$row][] = $number;		}	}		private final static function uniquePossibleValues()	{		if(isset(self::$possibles) && is_array(self::$possibles))		{			for($line = 0; $line <= 8; $line++)			{				for($row = 0; $row <= 8; $row++)				{					if(isset(self::$possibles[$line][$row]) && count(self::$possibles[$line][$row]) == 1)					{						return false;					}				}			}			return true;		}		else		{			return false;		}	}		private final static function possibleValues()	{		$ifUnique = false;		do		{			for($line = 0; $line <= 8; $line++)			{				for($row = 0; $row <= 8; $row++)				{					foreach(self::$numbers as $number)					{						if(self::$game[$line][$row] == NULL)						{							self::getPossibleValue($line, $row, $number);						}					}					if(isset(self::$possibles[$line][$row]) && count(self::$possibles[$line][$row]) == 1)					{						self::$game[$line][$row] = self::$possibles[$line][$row];						unset(self::$possibles[$line][$row]);						$ifUnique = false;					}				}			}			$ifUnique = true;		}		while(!$ifUnique);		print_r(self::$possibles);		//self::solveGame();	}		private final static function isSolved($what, $index)	{		switch($what)		{			case 'row':				$array = self::$game[$index];					break;			case 'line':				$array =  self::getRow($index);					break;			case 'block':				$array = self::getBlock($index);					break;		}		return (count(array_diff(self::$numbers, $array)) == 0);	}		private final static function isSolvedGame()	{		for($i = 0; $i <= 8; $i++)		{			if(!self::isSolved('row', $i) || !self::isSolved('line', $i) || !self::isSolved('block', $i))			{				return false;			}		}		return true;	}		private final static function checkArray()	{		try		{			if(!is_array(self::$game) || count(self::$game) != 9)			{				throw new Exception("O array informado é inválido.");			}			foreach(self::$game as $key => $cols)			{				if(!is_array($cols) || count($cols) != 9 || !self::filterArray($cols) || !self::filterArray(self::getRow($key))|| !self::filterArray(self::getBlock($key)))				{					throw new Exception("O array informado é inválido.");				}				foreach($cols as $colKey => &$values)				{					$values = trim($values);					if(!preg_match("/^[1-9]{1}$/", $values))					{						if($values != NULL)						{							throw new Exception("Há valores incorretos no array ($array[{$key}][{$colKey}]).");						}					}				}			}		}		catch(Exception $e)		{			die($e->getMessage());		}		self::possibleValues();	}		private final static function solveGame()	{		$save = self::$game;		while(!self::isSolvedGame())		{			self::$game = $save;			for($line = 0; $line <= 8; $line++)			{				for($row = 0; $row <= 8; $row++)				{					if(isset(self::$possibles[$line][$row]))					{						if(count(self::$possibles[$line][$row]) == 1)						{							self::$game[$line][$row] = self::$possibles[$line][$row][0];						}						else						{							//self::$game[$line][$row] = self::$possibles[$line][$row][0];							//parei aqui						}					}				}			}		}	}			private final static function exportGame($type = NULL)	{		switch($type)		{			case 'json':				return json_encode(self::$game);					break;			case 'serialize':				return serialize(self::$game);					break;			case 'text':				return self::parseText(self::$game);					break;			case 'table':				return self::parseTable(self::$game);					break;			default:				return self::$game;		}	}	}?>

[Evandro Oliveira 331]

 

 

<?php class sudoku {	private static		$sudoku,		$l = 0,							//linhas		$c = 0,							//colunas		$q = 0,							//quadrantes		$ql = 0,						//linhas em cada quadrante		$qc = 0,						//colunas em cada quadrante		$sl,							//matrizes contendo os valores do sudoku em linha		$sc,							//matrizes contendo os valores do sudoku em coluna		$sq,							//matrizes contendo cada quadrante do sudoku		$val = null,					//matriz contendo os valores que preenchem o sudoku		$tentativa_e_erro = array();	//auto-explicativa			// método solucionador do sudoku	public static function resolve($sudoku = null) {		// caso não tenha recebido um sudoku válido, envia uma exceção		if(!is_array($sudoku)) throw new exception("Sudoku inválido: Nulo ou vazio.");		$celulas = 0;									// inicia um contador de células		foreach($sudoku as $l=>$linha)					// percorre as linhas			// caso a linha não seja um array(), envia uma exceção			if(!is_array($linha)) throw new exception("Sudoku recebido não é uma matriz bidimensional.");			else foreach($linha as $c=>$celula) $celulas++;			// senão, conta as células do sudoku		sudoku::$q = (integer)sqrt($celulas);						// descobre o número de quadrantes		sudoku::$ql = floor(sqrt(sudoku::$q));						// armazena o número de linhas por quadrante		sudoku::$qc = ceil(sqrt(sudoku::$q));						// armazena o número de colunas por quadrante		// verifica se as linhasXcolunas do quadrante satisfazem o total de linhasXcolunas do sudoku		if(sudoku::$ql * sudoku::$qc != sudoku::$q)		// caso falhe, envia uma exceção dizendo que é impossível montar o sudoku			throw new exception("Sudoku recebido não está em um formato válido.");		// verifica se o sudoku possui o mesmo número de colunas em cada linha		foreach($sudoku as $l=>$linha) if(count($linha) !== sudoku::$q)			// caso alguma linha possua um número diferente de colunas, uma exceção é disparada			throw new exception("Algumas linhas do sudoku possuem menos colunas.");		sudoku::$sudoku = $sudoku;						// envia o sudoku para dentro da classe		sudoku::leitura();								// alimenta algumas propriedades com base no sudoku recebido		if(sudoku::$val == null) {						// verifica se foram configurados os valores do sudoku			sudoku::$val = array();						// caso falso, prepara a propriedade que armazena os valores			// e preenche indo de 1 até N onde N é o número de quadrantes/linhas/colunas			for($i = 1; $i <= sudoku::$q; $i++) sudoku::$val[] = $i;		}		// efetua uma série de testes e, para cada vez que o sudoku é modificado, atualiza as informações na classe		while(sudoku::testes()) { sudoku::leitura(); }		return sudoku::$sudoku;							// retorna o sudoku provavelmente resolvido	}		// este método atualiza os dados dentro da classe	private static function leitura(){		// gera matrizes para receber as linhas, colunas e quadrantes 		sudoku::$sq = array(); sudoku::$sl = array(); sudoku::$sc = array();		// como as variáveis de quadrantes e colunas serão alimentadas célula a célula, precisamos criar		// N matrizes correspondentes à ordem do Sudoku		for($i = 0; $i < sudoku::$q; $i++) {			sudoku::$sq[$i] = array();			sudoku::$sc[$i] = array();		}		foreach(sudoku::$sudoku as $l=>$linha) {	// percorre as linhas			sudoku::$sl[$l] = $linha;				// joga a linha atual para uma propriedade específica			foreach($linha as $c=>$celula) {		// percorre as colunas da linha				sudoku::$sc[$c][$l] = $celula;		// alimenta a propriedade de colunas com a transposta da linha				sudoku::$sq[sudoku::coordParaQuadrante($l,$c)][] = $celula;	// alimenta a propriedade de quadrantes			}		}		imprime(sudoku::$sudoku);					// imprime o novo sudoku em tela para acompanharmos o andamento	}		private static function testes(){							// efetua 3 tipos de testes e retorna a efetividade deles		// percorre o sudoku e verifica se a célula não está preenchida com um valor válido		foreach(sudoku::$sudoku as $l=>$linha) foreach($linha as $c=>$celula) if(!in_array($celula,sudoku::$val)) {			if(sudoku::testaValor($l,$c)) return true;			// verifica se um único valor preenche uma coordenada			elseif(sudoku::testaCasa($l,$c)) return true;		// verifica se uma coordenada admite um único valor		}		return false;	}			// este método retorna em qual quadrante do sudoku uma coordenada está	private static function coordParaQuadrante($linha,$coluna){		return (floor($linha / sudoku::$ql) * sudoku::$ql) + (floor($coluna / sudoku::$qc));	}		// este método retorna um array das coordenadas do quadrante[ínidice] recebido	// é o processo inverso do método coordParaQuadrante	private static function quadranteParaCoord($quadrante,$indice){		$x = ($quadrante%sudoku::$ql) + sudoku::$ql * ($indice%sudoku::$ql);		$y = ($quadrante%sudoku::$qc) * sudoku::$qc + ($indice%sudoku::$qc);		return array($x,$y);	}		private static function testaValor($l,$c){				// verifica se a coordenada pode ser preenchida com apenas um valor		$lista = array(); $quad = sudoku::$sq[sudoku::coordParaQuadrante($l,$c)];		// cria a lista, e busca o quadrante da coordenada		foreach(sudoku::$val as $try) {						// percorre a lista de valores que preenchem o sudoku			if(												// se o valor não está nem na linha, nem na coluna, nem no quadrante				!in_array($try,sudoku::$sl[$l]) &&				!in_array($try,sudoku::$sc[$c]) &&				!in_array($try,$quad)) $lista[] = $try;		// adiciona-o na lista		}		if(count($lista) == 1) {							// se a lista possuir apenas um valor			sudoku::$sudoku[$l][$c] = $lista[0];			// insere o valor no sudoku			return true;									// retorna que o método efetuou alterações		}		sudoku::$sudoku[$l][$c] = $lista;					// senão, insere a lista no sudoku		return false;										// retorna que o método não encotrou um único valor	}		private static function testaCasa($l,$c){		// calucula o número de vizinhos de uma célula		$maxpontos = (sudoku::$qc - 1) * (sudoku::$ql - 1);				// soma a quantidade de linhas e colunas vizinhas		foreach(sudoku::$sudoku[$l][$c] as $try) {						// percorre cada valor possivel na célula			$pontos = 0;			// cria uma variável para 'medir' a probabilidade de uma célula ser única para um candidato			$ci = floor($c / sudoku::$qc) * sudoku::$qc;				// variável que posiciona o ponteiro no início do domínio/colunas			$li = floor($l / sudoku::$ql) * sudoku::$ql;				// variável que posiciona o ponteiro no início do domínio/linhas			// efetua I iterações correspondentes ao quadrante e lê cada valor da coluna onde está o ponteiro			for($i = 0; $i < sudoku::$qc; $i++) foreach(sudoku::$sc[$ci+$i] as $v)			// se as colunas vizinhas já foram preenchidas com o candidato, adiciona pontos				if($v === $try) $pontos++;			// efetua I iterações correspondentes ao quadrante e lê cada valor da linha onde está o ponteiro			for($i = 0; $i < sudoku::$ql; $i++) foreach(sudoku::$sl[$li+$i] as $v)			// se as linhas vizinhas já foram preenchidas com o candidato, adiciona pontos				if($v === $try) $pontos++;			if($pontos == $maxpontos) {						// verifica se todos os vizinhos já foram preenchidos com o valor testado				sudoku::$sudoku[$l][$c] = $try;				// preenche a célula com o valor encontrado				return true;								// indica que o método realizou alterações no sudoku			}		}	return false;											// indica que o método não realizou alterações no sudoku	}		// alimenta a propriedade val com uma lista válida para o sudoku	public static function setUp($items = null){		// se não foi recebida uma lista, envia uma exceção		if(!is_array($items)) throw new exception('O método setUp precisa receber uma lista [array()].');		foreach($items as $item)	// percorre cada item da lista para uma verificação minunciosa			// permite apenas números e valores, caso algo fora do parâmetro seja recebido, envia uma exceção			if(!is_integer($item) && !is_string($item)) throw new exception('Método setUp não recebeu uma lista válida.');		sudoku::$val = $items;		// atualiza a propriedade $val com a nova lista	}}/* * [1] Montagem da ordem de quadrantes: * 				Caso seja passado um sudoku de ordem NxN onde, N possua uma raíz quadrada exata *		Seus quadrantes serão matrizes quadradas de ordem N^1/2xN^1/2 onde é o caso de sudoku's *		9x9, 16x16. Caso contrário, os quadrantes serão formados por um número maior de linhas *		do que colunas, exemplo: *				um sudoku 6x6 resulta em quadrantes de ordem 3x2 *				um sudoku 12x12 resulta em quadrantes de ordem 4x3 * * [2] Domínios: * 				Um domínio é formado pelas linhas e colunas que compõem um quadrante e pelo próprio * 		quadrante *  * [3] Percorrendo um domínio: * 				Para percorrer um domínio, posicionamos o ponteiro na primeira célula do quadrante * 		por onde passa a coordenada, percorre-se o número de linhas correspondente ao quadrante e * 		também o número de colunas 				 */

 

 

 

fail

 

 

como devem ter percebido, ela deve ser utilizada através de try/catch para manipulação de erros

 

para valores não-seriais (números sequenciais de 1 a X), utilizar o método ::setUp(mixed $items) onde $items é um array contendo os valores que preenchem o sudoku