Sudoku - Histórico de revisão

Suely: /* {{Ligações externas}} */

2010-08-24T13:15:19Z

← Edição anterior		Edição das 13h15min de 24 de agosto de 2010
Linha 143:		Linha 143:
	[[Categoria:Sudoku\| ]]		[[Categoria:Sudoku\| ]]
	[[Categoria:Cultura japonesa]]		[[Categoria:Cultura japonesa]]





	[[ja:数独]]		[[ja:数独]]

Suely: /* Matemática */

2010-08-19T20:00:16Z

Matemática

← Edição anterior		Edição das 20h00min de 19 de agosto de 2010
Linha 106:		Linha 106:

	== Matemática ==		== Matemática ==
	O problema geral de solucionar enigmas ''Sudoku'' em tabuleiros <math>n^2 \times n^2</math> de blocos <math>n \times n</math> é conhecido como [[NP-completo]]. http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf. Isto dá algumas indicações de porque o ''Sudoku'' é difícil de resolver. Contudo, em tabuleiros de tamanhos finitos o problema é finito e pode ser solucionado através de um [[autômato finito]] [[probabilidade\|probabilístico]] que conhece toda a [[Árvore (estrutura de dados)\|árvore do jogo]]. Solucionar enigmas ''Sudoku'' (assim como qualquer outro problema NP-difícil) pode ser expresso como um problema de preenchimento gráfico de cores. O objetivo do enigma em sua forma padrão é construir gráfico apropriado de nove colorações, informando parcialmente as nove colorações. O gráfico em questão tem 81 vértices, uma interpolação em cada célula da grade. Os vértices podem ser rotulados com os pares ordenados <math>(x,\, y)</math>, onde x e y são números inteiros entre 1 e 9. Neste caso, dois vértices distintos rotulados por <math>(x,\, y)</math> e <math>(x',\, y')</math> são conectados por uma borda se e apenas se <math>x = x'\ \lor y = y'\, \lor (\lceil x/3 \rceil = \lceil x'/3 \rceil \land \lceil y/3 \rceil = \lceil y'/3 \rceil)</math>.		O problema geral de solucionar enigmas ''Sudoku'' em tabuleiros <math>n^2 \times n^2</math> de blocos <math>n \times n</math> é conhecido como [[NP-completo]]. [http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf]. Isto dá algumas indicações de porque o ''Sudoku'' é difícil de resolver. Contudo, em tabuleiros de tamanhos finitos o problema é finito e pode ser solucionado através de um [[autômato finito]] [[probabilidade\|probabilístico]] que conhece toda a [[Árvore (estrutura de dados)\|árvore do jogo]]. Solucionar enigmas ''Sudoku'' (assim como qualquer outro problema NP-difícil) pode ser expresso como um problema de preenchimento gráfico de cores. O objetivo do enigma em sua forma padrão é construir gráfico apropriado de nove colorações, informando parcialmente as nove colorações. O gráfico em questão tem 81 vértices, uma interpolação em cada célula da grade. Os vértices podem ser rotulados com os pares ordenados <math>(x,\, y)</math>, onde x e y são números inteiros entre 1 e 9. Neste caso, dois vértices distintos rotulados por <math>(x,\, y)</math> e <math>(x',\, y')</math> são conectados por uma borda se e apenas se <math>x = x'\ \lor y = y'\, \lor (\lceil x/3 \rceil = \lceil x'/3 \rceil \land \lceil y/3 \rceil = \lceil y'/3 \rceil)</math>.

	O enigma é então completado designando-se um número inteiro entre 1 e 9 para cada interpolação, de tal maneira que os vértices que são unidos através de uma borda não tenham nenhum número inteiro igual designado neles. Uma grade de solução válida para o ''Sudoku'' é também um [[quadrado latino]]. Há significativamente menos soluções de grades de ''Sudoku'' válidas do que os quadrados latinos, porque o ''Sudoku'' impõe restrições de região adicionais. Apesar disso, o número de solução de ''Sudoku'' para uma grade padrão de 9×9 foram calculados em 2005 por Bertram Felgenhauer como sendo 6.670.903.752.021.072.936.960.<ref>http://www.afjarvis.staff.shef.ac.uk/sudoku/</ref> Este número é igual a <math>9! \times 72^2 \times 2^7 \times 27.704.267.971</math>, o último fator o qual é um [[número primo]]. O resultado é derivado através da lógica e [[computação]] [[força bruta]]. A derivação deste resultado foi simplificada consideravelmente por análises fornecidas por Frazer Jarvis e o número foi confirmado independentemente por Ed Russell. Russel e Jarvis também demonstraram de que quando as simetrias são levadas em conta, havia 5.472.730.538 soluções.<ref>http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html</ref> O número de soluções válidas para a variação do ''Sudoku'' de uma grade 16×16 é desconhecido.		O enigma é então completado designando-se um número inteiro entre 1 e 9 para cada interpolação, de tal maneira que os vértices que são unidos através de uma borda não tenham nenhum número inteiro igual designado neles. Uma grade de solução válida para o ''Sudoku'' é também um [[quadrado latino]]. Há significativamente menos soluções de grades de ''Sudoku'' válidas do que os quadrados latinos, porque o ''Sudoku'' impõe restrições de região adicionais. Apesar disso, o número de solução de ''Sudoku'' para uma grade padrão de 9×9 foram calculados em 2005 por Bertram Felgenhauer como sendo 6.670.903.752.021.072.936.960.<ref>http://www.afjarvis.staff.shef.ac.uk/sudoku/</ref> Este número é igual a <math>9! \times 72^2 \times 2^7 \times 27.704.267.971</math>, o último fator o qual é um [[número primo]]. O resultado é derivado através da lógica e [[computação]] [[força bruta]]. A derivação deste resultado foi simplificada consideravelmente por análises fornecidas por Frazer Jarvis e o número foi confirmado independentemente por Ed Russell. Russel e Jarvis também demonstraram de que quando as simetrias são levadas em conta, havia 5.472.730.538 soluções.<ref>http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html</ref> O número de soluções válidas para a variação do ''Sudoku'' de uma grade 16×16 é desconhecido.

Suely: /* Matemática */

2010-08-19T19:59:46Z

Matemática

← Edição anterior		Edição das 19h59min de 19 de agosto de 2010
Linha 106:		Linha 106:

	== Matemática ==		== Matemática ==
	O problema geral de solucionar enigmas ''Sudoku'' em tabuleiros <math>n^2 \times n^2</math> de blocos <math>n \times n</math> é conhecido como [[NP-completo]].~~<ref>~~http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf~~</ref>~~ Isto dá algumas indicações de porque o ''Sudoku'' é difícil de resolver. Contudo, em tabuleiros de tamanhos finitos o problema é finito e pode ser solucionado através de um [[autômato finito]] [[probabilidade\|probabilístico]] que conhece toda a [[Árvore (estrutura de dados)\|árvore do jogo]]. Solucionar enigmas ''Sudoku'' (assim como qualquer outro problema NP-difícil) pode ser expresso como um problema de preenchimento gráfico de cores. O objetivo do enigma em sua forma padrão é construir gráfico apropriado de nove colorações, informando parcialmente as nove colorações. O gráfico em questão tem 81 vértices, uma interpolação em cada célula da grade. Os vértices podem ser rotulados com os pares ordenados <math>(x,\, y)</math>, onde x e y são números inteiros entre 1 e 9. Neste caso, dois vértices distintos rotulados por <math>(x,\, y)</math> e <math>(x',\, y')</math> são conectados por uma borda se e apenas se <math>x = x'\ \lor y = y'\, \lor (\lceil x/3 \rceil = \lceil x'/3 \rceil \land \lceil y/3 \rceil = \lceil y'/3 \rceil)</math>.		O problema geral de solucionar enigmas ''Sudoku'' em tabuleiros <math>n^2 \times n^2</math> de blocos <math>n \times n</math> é conhecido como [[NP-completo]]. http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf. Isto dá algumas indicações de porque o ''Sudoku'' é difícil de resolver. Contudo, em tabuleiros de tamanhos finitos o problema é finito e pode ser solucionado através de um [[autômato finito]] [[probabilidade\|probabilístico]] que conhece toda a [[Árvore (estrutura de dados)\|árvore do jogo]]. Solucionar enigmas ''Sudoku'' (assim como qualquer outro problema NP-difícil) pode ser expresso como um problema de preenchimento gráfico de cores. O objetivo do enigma em sua forma padrão é construir gráfico apropriado de nove colorações, informando parcialmente as nove colorações. O gráfico em questão tem 81 vértices, uma interpolação em cada célula da grade. Os vértices podem ser rotulados com os pares ordenados <math>(x,\, y)</math>, onde x e y são números inteiros entre 1 e 9. Neste caso, dois vértices distintos rotulados por <math>(x,\, y)</math> e <math>(x',\, y')</math> são conectados por uma borda se e apenas se <math>x = x'\ \lor y = y'\, \lor (\lceil x/3 \rceil = \lceil x'/3 \rceil \land \lceil y/3 \rceil = \lceil y'/3 \rceil)</math>.

	O enigma é então completado designando-se um número inteiro entre 1 e 9 para cada interpolação, de tal maneira que os vértices que são unidos através de uma borda não tenham nenhum número inteiro igual designado neles. Uma grade de solução válida para o ''Sudoku'' é também um [[quadrado latino]]. Há significativamente menos soluções de grades de ''Sudoku'' válidas do que os quadrados latinos, porque o ''Sudoku'' impõe restrições de região adicionais. Apesar disso, o número de solução de ''Sudoku'' para uma grade padrão de 9×9 foram calculados em 2005 por Bertram Felgenhauer como sendo 6.670.903.752.021.072.936.960.<ref>http://www.afjarvis.staff.shef.ac.uk/sudoku/</ref> Este número é igual a <math>9! \times 72^2 \times 2^7 \times 27.704.267.971</math>, o último fator o qual é um [[número primo]]. O resultado é derivado através da lógica e [[computação]] [[força bruta]]. A derivação deste resultado foi simplificada consideravelmente por análises fornecidas por Frazer Jarvis e o número foi confirmado independentemente por Ed Russell. Russel e Jarvis também demonstraram de que quando as simetrias são levadas em conta, havia 5.472.730.538 soluções.<ref>http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html</ref> O número de soluções válidas para a variação do ''Sudoku'' de uma grade 16×16 é desconhecido.		O enigma é então completado designando-se um número inteiro entre 1 e 9 para cada interpolação, de tal maneira que os vértices que são unidos através de uma borda não tenham nenhum número inteiro igual designado neles. Uma grade de solução válida para o ''Sudoku'' é também um [[quadrado latino]]. Há significativamente menos soluções de grades de ''Sudoku'' válidas do que os quadrados latinos, porque o ''Sudoku'' impõe restrições de região adicionais. Apesar disso, o número de solução de ''Sudoku'' para uma grade padrão de 9×9 foram calculados em 2005 por Bertram Felgenhauer como sendo 6.670.903.752.021.072.936.960.<ref>http://www.afjarvis.staff.shef.ac.uk/sudoku/</ref> Este número é igual a <math>9! \times 72^2 \times 2^7 \times 27.704.267.971</math>, o último fator o qual é um [[número primo]]. O resultado é derivado através da lógica e [[computação]] [[força bruta]]. A derivação deste resultado foi simplificada consideravelmente por análises fornecidas por Frazer Jarvis e o número foi confirmado independentemente por Ed Russell. Russel e Jarvis também demonstraram de que quando as simetrias são levadas em conta, havia 5.472.730.538 soluções.<ref>http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html</ref> O número de soluções válidas para a variação do ''Sudoku'' de uma grade 16×16 é desconhecido.

Suely: /* {{Ligações externas}} */

2010-08-19T19:58:23Z

← Edição anterior		Edição das 19h58min de 19 de agosto de 2010
Linha 137:		Linha 137:
	== {{Ligações externas}} ==		== {{Ligações externas}} ==
	*[http://www.sudoku.szhk.sk \|4º Campeonato Mundial de Sudoku, em 24-27 de abril de 2009 na Eslováquia]		*[http://www.sudoku.szhk.sk \|4º Campeonato Mundial de Sudoku, em 24-27 de abril de 2009 na Eslováquia]
	*[http://www.wikipedia.org Wikipédia]]		*[http://www.wikipedia.org Wikipédia]

Suely: /* O Sudoku Mais Difícil do Mundo */

2010-08-19T19:58:05Z

O Sudoku Mais Difícil do Mundo

← Edição anterior		Edição das 19h58min de 19 de agosto de 2010
Linha 114:		Linha 114:
	== O Sudoku Mais Difícil do Mundo ==		== O Sudoku Mais Difícil do Mundo ==

	Um cientista finlandês [http://colunas.epoca.globo.com/vidautil/2010/08/19/o-sudoku-mais-dificil-do-mundo ~~Revista Época~~ ]] afirma ter criado o sudoku mais difícil de resolver do planeta. Sudoku é um quebra-cabeça numérico muito popular como passatempo.		Um cientista finlandês [http://colunas.epoca.globo.com/vidautil/2010/08/19/o-sudoku-mais-dificil-do-mundo ] afirma ter criado o sudoku mais difícil de resolver do planeta. Sudoku é um quebra-cabeça numérico muito popular como passatempo.

	O matemático Arto Inkala levou três meses para chegar a esse sudoko, a partir de um programa de computador que ele desenvolveu.		O matemático Arto Inkala levou três meses para chegar a esse sudoko, a partir de um programa de computador que ele desenvolveu.

Suely: /* O Sudoku Mais Difícil do Mundo */

2010-08-19T19:57:24Z

O Sudoku Mais Difícil do Mundo

← Edição anterior		Edição das 19h57min de 19 de agosto de 2010
Linha 114:		Linha 114:
	== O Sudoku Mais Difícil do Mundo ==		== O Sudoku Mais Difícil do Mundo ==

	Um cientista finlandês afirma ter criado o sudoku mais difícil de resolver do planeta. Sudoku é um quebra-cabeça numérico muito popular como passatempo.		Um cientista finlandês [http://colunas.epoca.globo.com/vidautil/2010/08/19/o-sudoku-mais-dificil-do-mundo Revista Época ]] afirma ter criado o sudoku mais difícil de resolver do planeta. Sudoku é um quebra-cabeça numérico muito popular como passatempo.

	O matemático Arto Inkala levou três meses para chegar a esse sudoko, a partir de um programa de computador que ele desenvolveu.		O matemático Arto Inkala levou três meses para chegar a esse sudoko, a partir de um programa de computador que ele desenvolveu.

Suely: /* O Sudoku Mais Difícil do Mundo */

2010-08-19T19:56:09Z

O Sudoku Mais Difícil do Mundo

← Edição anterior		Edição das 19h56min de 19 de agosto de 2010
Linha 125:		Linha 125:

	Quer se arriscar? Aqui o Sudoku Mais Difícil do Mundo:		Quer se arriscar? Aqui o Sudoku Mais Difícil do Mundo:
	[[Image:Sudoku_mega_dificil.jpg\|~~thumb~~\|200px\|Um enigma ''Sudoku'' nonomino]]		[[Image:Sudoku_mega_dificil.jpg\|frame\|200px\|center\|Um enigma ''Sudoku'' nonomino]]

	== {{Ver também}} ==		== {{Ver também}} ==

Suely: /* O Sudoku Mais Difícil do Mundo */

2010-08-19T19:55:31Z

O Sudoku Mais Difícil do Mundo

← Edição anterior		Edição das 19h55min de 19 de agosto de 2010
Linha 125:		Linha 125:

	Quer se arriscar? Aqui o Sudoku Mais Difícil do Mundo:		Quer se arriscar? Aqui o Sudoku Mais Difícil do Mundo:
	[Image:		[[Image:Sudoku_mega_dificil.jpg\|thumb\|200px\|Um enigma ''Sudoku'' nonomino]]

	== {{Ver também}} ==		== {{Ver também}} ==
	{{correlatos		{{correlatos

Suely: /* {{Ver também}} */

2010-08-19T19:54:28Z

@@ Linha 112: / Linha 112: @@
 {{ref-section}}
 == {{Ver também}} ==
 {{correlatos

Suely: /* Variantes */

2010-08-19T19:52:33Z

Variantes

← Edição anterior		Edição das 19h52min de 19 de agosto de 2010
Linha 87:		Linha 87:

	== Variantes ==		== Variantes ==
	[[~~Ficheiro~~:~~Nonomino Sudoku~~.~~svg~~\|thumb\|200px\|Um enigma ''Sudoku'' nonomino]]		[[Image:Sudoku5_copy.jpg\|thumb\|200px\|Um enigma ''Sudoku'' nonomino]]

	Apesar de a grade 9×9 com regiões 3×3 ser de longe a mais conhecida, diversas variações abundam: amostras do enigma podem ser grades de 4×4 com regiões 2×2; grades 5×5 regiões [[pentaminó]] tem sido publicadas sob o nome ''Logi-5''; o [[World Puzzle Championship]] apresentou anteriormente grades 6×6 com regiões 2×3 e grades 7×7 com 6 regiões [[heptominó]] e com regiões desconexas. ''Daily SuDoku'' apresenta novas grades 4×4, 6×6, e mais simples 9×9 todos os dias com ''Daily SuDoku for Kids (Sudoku diário para crianças)''.<ref>http://www.dailysudoku.co.uk/sudoku/index.shtml</ref> Mesmo as grades 9×9 não são sempre padrões, com a [[Ebb]] publicando regularmente alguns com regiões [[nonominó]] (também conhecido como variação quebra-cabeça); o Campeonato Estadunidense de Enigmas de 2005 tinha um ''Sudoku'' com regiões em [[paralelogramo]] que circundavam a parte exterior do enigma, como-se a grade fosse uma [[arruela]] quadrada. Grades maiores também são possíveis, com o ''Daily SuDoku's'' 12×12 ''Monster SuDoku'', o ''Times'' igualmente oferece um com grade 12×12 ''Dodeka sudoku'' com 12 regiões cada uma sendo 4×3, o sítio Conceptis Puzzles oferece gratuitamente um puzzle 12×12 (''Mega Sudoku'') por semana, a ''Dell'' regularmente publica 16×16 ''Number Place Challenger'' (a variação 16×16 geralmente utiliza 1 até G ao invés do 0 até o F utilizado em notações [[hexadecimal\|hexadecimais]]), e a ''Nikoli'' oferece o enorme 25×25 ''Sudoku the Giant''.		Apesar de a grade 9×9 com regiões 3×3 ser de longe a mais conhecida, diversas variações abundam: amostras do enigma podem ser grades de 4×4 com regiões 2×2; grades 5×5 regiões [[pentaminó]] tem sido publicadas sob o nome ''Logi-5''; o [[World Puzzle Championship]] apresentou anteriormente grades 6×6 com regiões 2×3 e grades 7×7 com 6 regiões [[heptominó]] e com regiões desconexas. ''Daily SuDoku'' apresenta novas grades 4×4, 6×6, e mais simples 9×9 todos os dias com ''Daily SuDoku for Kids (Sudoku diário para crianças)''.<ref>http://www.dailysudoku.co.uk/sudoku/index.shtml</ref> Mesmo as grades 9×9 não são sempre padrões, com a [[Ebb]] publicando regularmente alguns com regiões [[nonominó]] (também conhecido como variação quebra-cabeça); o Campeonato Estadunidense de Enigmas de 2005 tinha um ''Sudoku'' com regiões em [[paralelogramo]] que circundavam a parte exterior do enigma, como-se a grade fosse uma [[arruela]] quadrada. Grades maiores também são possíveis, com o ''Daily SuDoku's'' 12×12 ''Monster SuDoku'', o ''Times'' igualmente oferece um com grade 12×12 ''Dodeka sudoku'' com 12 regiões cada uma sendo 4×3, o sítio Conceptis Puzzles oferece gratuitamente um puzzle 12×12 (''Mega Sudoku'') por semana, a ''Dell'' regularmente publica 16×16 ''Number Place Challenger'' (a variação 16×16 geralmente utiliza 1 até G ao invés do 0 até o F utilizado em notações [[hexadecimal\|hexadecimais]]), e a ''Nikoli'' oferece o enorme 25×25 ''Sudoku the Giant''.