domingo, 31 de maio de 2015

Sudokando (Em novo andamento)

No segmento da postagem de 9 de Abril ultimo (que é conveniente reler para completar o que se segue) fui desafiado para trazer aqui uma solução completa de um problema de SUDOKU. Tendo arrastado essa hipótese durante algum tempo, fui novamente confrontado com a utilidade de uma demonstração. Recorri por isso à consulta da seccão própria do Correio da Manhã (cujos problemas "DIFÍCEIS" têm, em termos de SUDOKU,  qualidade qie  pode acompanhar os "HARD" também diariamente publicados pelo "New York Times") e trabalhei exactamente um recente (dia 29 ou 30 do corrente). Foi um esforço meramente demonstrativo, lúdico e não competitivo, não demonstrando nem pretendendo demonstrar a melhor via de solução - já que, para os puristas da modalidade, o que se apresenta pode estar longe de ser a melhor aproximação, a mais expedita, a mais moderna ou elegante... mas que respondeu ao fim em vista, e que era a prometida e explicada resolução de um  problema dito "difícil".
O problema [1]: 
 a2d68a / c6a3a1a / b1a8a9b / b7a9a3b / a1e4a / b4a2a5b / b8a3a2b / a5a1a9c / a73d9a

1)      Aplicação do tabuleiro (ou quadro) de eliminações Ostermiller colocando os algarismos originais a PRETO e escolhendo CINZA para os deduzidos.
2)      Não existem SOLITÁRIOS, designando-se como tal qualquer algarismo que se apresente SOZINHO numa dada casa de um quadro de eliminação e que, obviamente, já faz parte da solução porque só pode ser o "dono" dessa casa.

3)      Procura de EXCEPÇÕES [2]:       
  •                           1 é excepção na C5 e por isso L1C5=1; 
  •                           2 é excepção na L2 e por isso L2C9=2
  •                                             2 é também excepção no B6 e por isso L4C8=2;
  •                                             9 é excepção no B2 e por isso L1C4=9;
  •                                            3, 4, 5, 6, 7 e 8 não são excepções em qualquer L, C ou B
 4)      Apareceu um SOLITÁRIO em L1C3 e por isso exploram-se os SOLITÁRIOS de cima a baixo enquanto aparecerem 
  •                                               L1C3=5
  •                                           L2C3=9
5)      O 5 passou a ser excepção na L2 donde L2C5=5
6)      Em B8 existe uma QUADRA 46, 457, 467, 4567 que só afecta B8, o que nos permite eliminar todos os algarismos desta quadra nas restantes casas. Fica
  •                          L9C3=2,8                   
  •                          L9C6=2,8
7)      Forma-se assim um PAR 2,8 na L9  o que nos permite limpar todos os 2 e 8 nessa L9
8)      Mas… nessa L9 o 5 surge como EXCEPÇÃO donde L9C9=5
9)      Agora, voltando a trabalhar de cima para baixo, nota-se o 5 como EXCEPÇÃO em B3, donde L3C8=5
10)   E o PAR 6,7 na  C8 faz os seus estragos excepcionando L8C8 que fica L8C8=3
11)   Em C7 é o 1 que passa a excepção, donde L9C7=1, o que arrasta (também por excepções na L7) a L7C1=1 e L7C2=9.
12)   Pelo  encravamento encontrado parece altura de fazer UMA ITERAÇÃO. Seja adoptada a HIPÓTESE L2C7=4 (sendo preterida L2C7=7). No quadro Ostermiller pode passar-se para qualquer outra cor, diferente das até agora aplicadas (geralmente na 1ª iteração uso o azul, na segunda o vermelho e na 3º o verde, isto por razões mais de visibilidade que de clubismo).
13)   L2C2=8 e L2C1=7 fechando L2
14)   L4C3=6 (SOLITARIO), L6C2=3, L3C2=4  fechando C2.
15)   L5C3=2, L9C3=6 fechando C3
16)   L1C1=3, L3C1=6 fechando  B1. Passamos a ter vários pontos por onde começar… Começando de cima para baixo… L1C9=7, L1C6=4 o que fecha L1, L3C9=3 o que fecha  B3.
17)   L9C1=4, L8C1=2 o que fecha B7, L9C5=6, L5C5=7, L8C5=4 o que fecha C5, L8C9=8, L8C7=7 o que fecha L8, L7C8=6, L7C9=, L4C9=1, L5C7=8 o que fecha C7, L6C8=7 o que fecha C8,
L6C4=8, L6C1=9, L6C9=6, L6C6=1 o que fecha L6, L5C1=5, L5C4=3, L5C6=6 e L5C9=9, o que fecha L5, C9 e B6.
18)   Ainda teremos um pouco para avançar e esperar boas e más surpresas (não esqueçamos que estamos em campo iterativo e a nossa escolha no passo 12 poderá não ter sido a melhor… Vejamos!)
19)   L4C1=8  e fecha B4, L4C6=5, L4C4=4 e fecha B5, L7C6=7, L7C4=5 o que fecha L7  e, em suspense, L3C6=2… uff! Parece que "passamos" sem necessidade de voltar atrás.

20)   L3C4=7, L9C4=2 e L9C6=8 … e aí temos a solução completa:
325|914|687;
789|653|412;
641|782|953;
867|495|321;
512|376|849;
934|821|576;
198|537|264;
256|149|738;
473|268|195.

NOTA SOBRE ITERAÇÕES: E se tivesse aparecido um ERRO? Ou nos tínhamos enganado pelo caminho (o que sempre pode suceder, e nisso o “tabuleiro” ou “quadro” Ostermiller é um auxiliar precioso), ou a escolha feita na iteração NÃO TINHA SIDO A ACERTADA ou ainda O SUDOKU NÃO TEM SOLUÇÃO, porque essa situação também pode existir (embora não seja presente, a não ser por erro ou gralha, nos problemas propostos aos aficionados da modalidade, por muito “diabólicos” que possam ser (designação corrente  par os "muito difíceis" na terminologia francesa!).
No segundo caso, certamente o mais provável, teríamos de voltar atrás para modificar a opção (ou opções feitas)  feitas e  refazer todos os passos dedutivos a partir daí [3].. Até nisso o quadro de Ostermiller auxilia: recordemos que ao fazer a escolha para a iteração (ou tentativa, se lhe quiserem dar outro nome) mudamos a cor dos novos algarismos para VERMELHO. O quadro permite APAGAR UMA COR e se dermos essa instrução ele vai anular todos os passos “A VERMELHO” e colocar o problema exactamente como estava antes da iteração.

Isto é particularmente útil quando for preciso fazer várias iterações sucessivas, mudando a cor dos algarismos para cada iteração que se fizer. Compreende-se bem que uma iteração simples que corresponda a uma escolha entre dois algarismos dá lugar a DUAS ALTERNATIVAS, para DUAS ITERAÇÕES teremos 4 alternativas (22) e para TRES ITERAÇÕES como já tive de usar num “sudoku” HARD do New York Times, talvez por inépcia minha (admito que um “mestre” o resolvesse em duas penadas, sem recurso a isso), a 8 alternativas (23).  Similarmente uma, duas ou três iterações de 1 entre 3 algarismos levará a 3, 9 e 27 alternativas. Não me consta que seja preciso ir tão longe na imitação de Sisifo.

Aliás alguns cultores de linhas fundamentalistas do SUDOKU, que eu conheço, teriam levado o nosso caso mais longe. Com o argumento de que tivemos sorte na escolha iniciariam um processo de “prova real”, ou seja, fariam mesmo a OUTRA ALTERNATIVA com uma dupla finalidade: provar que ela não iria mesmo dar solução e afastar a situação, que pode existir, de estarmos perante um problema de SUDOKU com duas ou mais soluções possíveis. Aliás até no final de um problema podem surgir duas soluções quando linhas ou colunas apresentem possibilidades conjugadas  e não contraditórias do tipo
__ __ __ XY __ __ YX__ __
­­­­­__ __ __ YX __ __ XY__ __

Se nada for ditado pelo restante problema é fácil de ver que estas possibilidades conduzem às duas soluções possíveis  e diferentes
­_ _ _ X _ _ Y _ _            _ _ _ Y _ _ X _ _
_ _ _ Y _ _ X _ _            _ _ _ X _ _ Y _ _

Como isto já vai longo e cumpri o prometido e até demonstrei que o “tabuleiro Ostermiller” não é batota porque não afasta o conhecimento e aplicação das regras do SUDOKU e até os favorece, não vou enveredar pelo processo de verificação do “outro caminho da tentativa”, como prática  de "fundamentalismo sodukista". Mas, para quem o queira fazer, vou deixar aqui a situação do tabuleiro Ostermiller como estava antes dessa escolha que levou a uma solução não garanto se pelo melhor caminho mas sem necessidade de voltar atrás [4]:

2347
234
5
9
1
247
6
8
247
478
48
9
6
5
3
47
1
2
23467
2346
1
247
8
247
9
5
247
568
68
7
458
9
14568
4
2
168
235689
1
26
3578
67
5678
78
4
6789
3689
368
4
378
2
1678
5
67
16789
1
9
8
457
3
4567
2
67
467
346
5
26
1
467
9
478
3
4678
246
7
3
248
46
2468
1
9
5

Recordemos que na casa L2C7 se adoptou o 4 e não o 7. Quem quiser prosseguir a verificação terá de adoptar o 7 e desprezar o 4 e…  continuar a partir daí. Boa viagem! [4]



[1] Na notação sintética proposta neste blog a 10 de Maio de 2013, usando minúsculas de acodo com sugestão então formulada (e bem) por um Leitor.
[2] Um algarismo é EXCEPÇÃO numa dada figura (assim chamando às linhas L, colunas C e blocos B) quando  o quadro mostre que só existe nessa figura UMA ÚNICA POSSIBILIDADE de caber. Passa a fazer parte da solução nessa figura ocupando como "dono" a casa em que se encontra. Ver o exemplo do DOIS na L2 deste problema!
[3] Havendo várias iterações há que cuidadosamente estabelecer a regra de montagem e a regra de retorno, que deve efectuar exactamente os passos da linha de montagem mas em sentido inverso. Por exemplo: consideremos um sucessão de 3 iterações  XYZ todas duais (i.e. em que houve opções entre dois algarismos X1 e X2, etc) e  em que só a 7ª tentativa resultou. O esforço todo feito chamando A todo o trabalho realizado até à iteração X pode esquematizar-se por:
» A » AX1 » AX1Y1 » AX1Y1Z1 (1ª Tentativa) » AX1Y1Z2 (2ª Tentativa) » AX1Y2Z1 (3ª Tentativa) » AX1Y2Z2 (4ª Tentativa) » AX2Y1Z1 (5ª Tentativa) » AX2Y1Z2 (6ª Tentativa) » AX2Y2Z1 (7ª Tentativa) que, como admitimos, nos levou à solução... porque se essa mesmo não desse só nos restaria uma 8ª Tentativa (AX2Y2Z2)... e se essa finalmente não desse ou teria havido erro do solucionador ou o SUDOKU seria IMPOSSÍVEL por não ter solução!
[4] O quadro realizado acima mostra um QUADRO DE ELIMINAÇÂO como pode ser construído para proceder a eliminações manuais (e muitos solucionadores o fazem). O quadro de Ostermiller  nada mais é que um quadro desta natureza  em que as eliminações em linhas, colunas e blocos saso automaticamente feitas, poupando trabalho e evitando omissões e erros. Mais uma vez se demonstra que o quadro automatizado é uma vantagem mas que não foge a técnicas conhecidas de solução "convencional" destes problemas.

sexta-feira, 8 de maio de 2015

O lavatório de Pilatos

Vivemos no faz-de-conta, vitimados pelo mal pior do que o das palmeiras (ao menos os bichos dessas são vermelhos!) dos "orgulhos de Esquerda". Vilipendiamos o vizinho de sector, denegrimos os que estão nas respectivas fileiras, deixamos que polulem leões nos coliseus sem protestar contra isso, aceitamos o vandalismo sem nos importarmos (vandalismo de todos os feitios e formas), praticamos orgulhosamente não ir votar, esquecemo-nos de que ganhar não é apenas ganhar mas também é fazer os adversários perder. Superioridade moral, mesmo que não a mereçam, é apanágio de um pensamento de Direita (a Esquerda e a Direita existem, não caiam na esparrela embaladora e ela própria arrogante de o negar ou mesmo, no 1º grau, de o questionar). E não me venham depois chorar sobre o leite derramado. A questão é sempre saber até que ponto cada um de nós colaborou no derrame. Até por aquiescência.

quinta-feira, 7 de maio de 2015

O p

O meu problema não é apenas (mas também é) o que ele escreve. O meu mais sério problema é como pôde chegar aí.

sexta-feira, 1 de maio de 2015

O faz-de-conta e o pagodiano pasmado ou a invocação do cavalo de D.Fuas




Um PM de tutano liberal (que SD se apregoará mas que de real SD o tanas!) de cravo ao peito tentando apossar-se de uma data e de, ao sabor e lucro do momento, fantasiar assim aquilo que a outros os dele censuravam, um bando de super-tendeiros a também querer usurpar-se do Dia do Trabalhador, invocando o benefício do povo para reduzir momentaneamente alguns lucros e macaquear o movimento populo-consumista originado por Aleksandre Kleine (espero que assim se escreva em bom neerlandês) e de muito Pagode a tudo abrir a boca, atento, venerador e obrigado, entre comentários de futebol, raspadinhas, escândalos, revistas cor-de-rosa, grandes títulos nas primeiras páginas e desalfaios nas ultimas, com anúncios relax nos entremeios, assim vamos nós. Ainda não é "cantando e rindo" e espero bem que nem quase o chegue a ser, desde que saibamos nós fazer greve a tempo como a do cavalo de D.Fuas atrás de bichezas enganadoras.

Jaculatória:

Hoje, 1º de Maio, nada compro. Não sirvo nem levarei a que alguém me sirva, salvo através de serviços necessariamente continuados ou de emergência. Amen!

(gravura: cortesia a www.escolovar.com)