• Artigo

Este artigo foi traduzido por máquina.

Execução de teste

Resolver quebra-cabeças de sudoku usando a biblioteca do MSF

James McCaffrey

Baixar o código de exemplo

James McCaffreyUm quebra-cabeça Sudoku é um exemplo do que é chamado um problema de satisfação de restrição (CSP). Uma maneira de abordar o CSPs programaticamente é usar a biblioteca de Microsoft Solver Foundation (MSF). Embora seja altamente improvável que você realmente precisa resolver um quebra-cabeça Sudoku como parte de suas responsabilidades de trabalho normal, existem pelo menos três razões porque você pode querer ler este artigo. Em primeiro lugar, as técnicas apresentadas aqui podem ser usadas para resolver muitos problemas realistas. Em segundo lugar, este artigo irá apresentá-lo à biblioteca MSF e suas capacidades. E em terceiro lugar, você pode encontrar que resolver enigmas de Sudoku programaticamente é interessante e divertido.

Para ter uma idéia de onde este artigo é dirigido, olha para o programa de demonstração em Figura 1. O aplicativo de console do demo começa por configurar e exibir os dados para um típico Sudoku. Em seguida, ele programaticamente define restrições (condições exigidas) que são comuns a todos os enigmas de Sudoku e então configura as restrições de dados que são específicas para o quebra-cabeça. Então, nos bastidores, o demo usa a biblioteca MSF para resolver o enigma. O demo conclui exibindo a solução.

Sudoku usando o Solver Microsoft Foundation
Figura 1 Sudoku usando o Solver Microsoft Foundation

Este artigo pressupõe que você tem habilidades de programação pelo menos nível intermediário e uma vaga idéia de enigmas de Sudoku são, mas não assumir que sabe alguma coisa sobre problemas de satisfação de restrição ou a biblioteca MSF. O programa de demonstração é codificado usando c#, mas você deve ser capaz de Refatorar o demo para outras linguagens .NET sem muita dificuldade. Todo o código é apresentado aqui e também está disponível no download de código que acompanha este artigo no msdn.microsoft.com/magazine/msdnmag0814. Verificação de erros normal todos foi removido para manter as principais idéias claras.

O Solver Microsoft Foundation Biblioteca

A biblioteca de versão 3.1 do MSF está disponível como um download separado do código. O local do download tendeu a se mover ao longo do tempo, mas eu achei no bit.ly/1vayGh1. Eu prefiro usar as bibliotecas de 32-bit quando experimentando então eu cliquei no link, que me deu a opção de executar ou salvar o pacote de instalação do MicrosoftSolverFoundation.msi. Eu selecionei a opção Executar.

O assistente de instalação diz-lhe que você está instalando o Express Edition. MSF originalmente veio em duas versões, uma edição Express gratuita e uma edição de empresa para compra, mas o enterprise edition foi descontinuado. A biblioteca MSF é essencialmente não está mais sendo desenvolvida activamente, mas a atual versão 3.1 funciona bem para mim. Após a rápida mas um tanto desajeitado instalação processo terminar, o arquivo de biblioteca chave Microsoft.Solver.Foundation.dll é copiado para a sua máquina no diretório C:\Program Files (x86) \Reference Assemblies\­Microsoft\Framework\.NETFramework\v4.0.

Para criar o programa de demonstração, lançou o Visual Studio e selecionado o c# console aplicativo programa modelo e o nome SudokuSolver. O demo não tem significativa do Microsoft .NET Framework versão dependências assim qualquer versão relativamente recente do Visual Studio deve funcionar. Depois de carregado o código do modelo, no Solution Explorer janela renomeei o arquivo Program.cs para SudokuProgram.cs e Visual Studio então automaticamente renomeado classe Program. A estrutura geral do programa de demonstração, com algumas pequenas edições para economizar espaço, é apresentada em Figura 2.

Figura 2 estrutura geral do programa

using System;
using Microsoft.SolverFoundation.Services;
namespace SudokuSolver
{
  class SudokuProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin MS Solver Foundation Sudoku demo");
      Console.WriteLine("The problem is: ");
      int[][] data = new int[9][];
      data[0] = new int[] { 0, 0, 6,
        2, 0, 0,
        0, 8, 0 };
      data[1] = new int[] { 0, 0, 8,
        9, 7, 0,
        0, 0, 0 };
      data[2] = new int[] 
      { 0, 0, 4,
        8, 1, 0,
        5, 0, 0 };
      data[3] = new int[] 
      { 0, 0, 0,
        0, 6, 0,
        0, 0, 2 };
      data[4] = new int[] 
      { 0, 7, 0,
        0, 0, 0,
        0, 3, 0 };
      data[5] = new int[] 
      { 6, 0, 0,
        0, 5, 0,
        0, 0, 0 };
      data[6] = new int[] 
      { 0, 0, 2,
        0, 4, 7,
        1, 0, 0 };
      data[7] = new int[] 
      { 0, 0, 3,
        0, 2, 8,
        4, 0, 0 };
      data[8] = new int[] 
     { 0, 5, 0,
       0, 0, 1,
       2, 0, 0 };
      // all program logic here
      Console.WriteLine("End Solver Foundation Sudoku demo");
      Console.ReadLine();
    }
    static void AddDataConstraints(int[][] data,
      Model model, Decision[][] grid) { . . }
    static int NumberSolutions(SolverContext problem) { . . }
  }
} // ns

Na parte superior do código-fonte gerado pelo modelo Visual Studio , eu removi todos os desnecessários usando declarações, exceto aquele que faz referência o namespace de sistema de nível superior. Em seguida, adicionei uma referência para o arquivo DLL de biblioteca MSF e então adicionei um usando instrução que referencia a biblioteca para trazê-lo para o escopo.

Quase todo o trabalho é executado dentro do método Main. Dois métodos auxiliares, AddDataConstraints e NumberSolutions, são apenas as conveniências para manter o código dentro de Main um pouco mais arrumado. Após uma início-mensagem preliminar, o demo configura os dados de quebra-cabeças de Sudoku em uma matriz de matrizes-matriz de estilo.

Ao contrário de muitas linguagens, c# suporta uma matriz bidimensional de verdade, mas como você verá, a abordagem de matriz de matrizes é mais fácil trabalhar com. Mesmo se você é um programador experiente, se você frequentemente não trabalha com programação numérica, você não pode estar familiarizado com as técnicas de codificação de matriz. A matriz de dados demo é representada no Figura 3. Dados podem ser acessados por uma célula individual, ou por uma linha inteira, mas não por uma coluna inteira. Por exemplo, dados [0] [2] é a célula na linha 0 e coluna 2 e tem o valor 6, e dados [1] faz referência a toda a segunda linha. Não há nenhuma maneira conveniente para acessar uma coluna. O espaço em branco em células Figura 3 realmente tem valores 0 porque c# automaticamente inicializa as células da matriz de inteiros para todos 0s.

A matriz de dados do problema
Figura 3 a matriz de dados do problema

Configurando o problema

Depois que a matriz de dados problema foi criada, o programa de demonstração exibe os valores para o shell:

for (int r = 0; r < 9; ++r)  {
  for (int c = 0; c < 9; ++c)  {
    if (data[r][c] == 0)
      Console.Write(" _");
    else
      Console.Write(" " + data[r][c]);
  }
  Console.WriteLine("");
}

Aqui, os limites do laço são codificadas como 9. Na minha opinião, especialmente com programas de demonstração, às vezes é melhor manter as coisas simples, ao invés de tornar o código mais geral. Em seguida, o demo faz o primeiro uso do código do MSF:

SolverContext problem = SolverContext.GetContext();
Model model = problem.CreateModel();
Decision[][] grid = new Decision[9][];
for (int r = 0; r < 9; ++r)
  grid[r] = new Decision[9];

Trabalhando com o MSF biblioteca tem uma sensação um pouco diferente porque o código foi desenvolvido em um ambiente de pesquisa-desenvolvimento de híbridos. Você pode pensar das duas primeiras linhas como uma magia Inca­tação para criar um objeto CSP. Ao invés de trabalhar com um único objeto, como você provavelmente está acostumado, a biblioteca MSF tende a usar vários objetos tais como o problema e modelo aqui.

O objeto da grade é uma matriz de matrizes-matriz de estilo onde cada célula é um objeto de decisão. Você pode pensar de um objeto de decisão como um encapsulamento de uma resposta. Ou dito de outra forma, para resolver um quebra-cabeças Sudoku, você precisa determinar 9 x 9 = 81 valores. Cada um desses valores é representado por um objeto de decisão e o demo armazena-los em uma matriz.

Neste ponto, a matriz de grade tem sem instância objetos de decisão. O demo instancia cada célula da seguinte forma:

for (int r = 0; r < 9; ++r)
  for (int c = 0; c < 9; ++c)
    grid[r][c] = new Decision(Domain.IntegerRange(1, 9),
      "grid" + r + c);
for (int r = 0; r < 9; ++r)
  model.AddDecisions(grid[r]);

O construtor de decisão aceita dois parâmetros. O primeiro descreve o tipo de dados de uma resposta. Aqui, cada resposta é um número inteiro entre 1 e 9. O segundo parâmetro é um nome não-opcional como uma seqüência de caracteres. Estes nomes devem ser exclusivos, então o demo programaticamente atribui nomes "grid00", "grid01" e assim por diante para cada um dos objetos de decisão de 81. Depois que os objetos de decisão tem sido instanciados, deve ser adicionados ao objeto de modelo. O método AddDecisions pode aceitar um único objeto de decisão ou uma matriz de objetos de decisão, portanto, o demo passa das nove linhas da matriz de grade. Uma alternativa seria usar dois loops aninhados, como este:

for (int r = 0; r < 9; ++r)
    for (int c = 0; c < 9; ++c)
      model.AddDecisions(grid[r][c]);

Adicionando restrições genéricas

Há três conjuntos de restrições genéricas que são comuns a todos os enigmas de Sudoku. Primeiro, os valores em cada linha devem ser diferentes. Em segundo lugar, os valores de cada coluna devem estar diferentes. E em terceiro lugar, os valores em cada cubo de 3 x 3 sub devem ser diferentes. Cuidar-se do primeiro conjunto de restrições é fácil:

Console.WriteLine("Creating generic row constraints");
for (int r = 0; r < 9; ++r)
  model.AddConstraint("rowConstraint" + r, 
  Model.AllDifferent(grid[r]));

O método AddConstraint aceita um nome de restrição, seguido por uma restrição. Aqui, os nomes são "rowConstraint0", "rowConstraint1" e assim por diante. O demo usa o método diferente para criar uma restrição. Em palavras, para cada uma das nove linhas, adicione uma restrição que todos os valores na linha devem ser diferentes.

Adicionar a restrição de coluna genérico requer um pouco mais de esforço:

Console.WriteLine("Creating generic column constraints");
for (int c = 0; c < 9; ++c)
{
  for (int first = 0; first < 8; ++first)
    for (int second = first + 1; second < 9; ++second)
      model.AddConstraint("colConstraint" + c + first + second,
        grid[first][c] != grid[second][c]);
}

Porque uma coluna inteira não pode ser acessada diretamente, o demo funciona em cada coluna separadamente. Coluna 0, a primeira vez através de dois loops aninhados internas define a restrição nomeada "colConstraint001" como grade [0] [0]! = grade [1] [0]. A segunda iteração define "colConstraint002" como grade [0] [0]! = grade [2] [0]. Para resumir, o diferente método aceita que um conjunto de objetos de decisão como uma matriz e nos bastidores gera desigualdades explícitas. Em situações onde os objetos de decisão não estão em uma matriz (como os valores da coluna), você deve explicitamente gerar as desigualdades.

De longe a parte mais complicada do programa demo é configurar as restrições que especificar que todos os valores em cada um dos nove 3 x 3 cubos sub devem ser diferentes. Que código é apresentado em Figura 4. Tenha paciência comigo — o código não é quase tão complexo como parece.

Figura 4 configurar as restrições de cubo sub

Console.WriteLine("Creating generic sub-cube constraints");
for (int r = 0; r < 9; r += 3) {
  for (int c = 0; c < 9; c += 3) {
    for (int a = r; a < r + 3; ++a) {
      for (int b = c; b < c + 3; ++b) {
        for (int x = r; x < r + 3; ++x) {
          for (int y = c; y < c + 3; ++y) {
            if ((x == a && y > b) || (x > a))
            {
              model.AddConstraint("cubeConstraint" + a + b + x + y,
                grid[a][b] != grid[x][y]);
            }
          } // y
        } // x
      } // b
    } // a
  } // c
} // r

Considere o cubo secundário no canto inferior esquerdo do Figura 3. As restrições necessárias para esse cubo secundário são:

grid[6][0] != grid[6][1]
grid[6][0] != grid[6][2]
grid[6][0] != grid[7][0]
...
grid[8][1] != grid[8][2]

Existem 8 + 7 + 6 +... + 1 = 36 restrições para esse cubo sub, e então há 9 * 36 = 324 total desigualdades de restrições de nove cubo sub. Agora, isso seria possível para listar cada um usando copiar-colar e um pouco de paciência, mas uma abordagem programática é mais rápida.

No código, os dois loops exteriores estabelecem um canto superior esquerdo de cada cubo sub. Nos quatro laços mais íntimos, as células são representadas como grade [a] [b]! = grade [x] [y]. Se você olhar só para os índices no exemplo e imagem, que são apenas comuns inteiros, você obtém:

60 and 61
60 and 62
...
81 and 82

Observe que em cada caso, há uma restrição de desigualdade quando ab < XY. As intimidades quatro loops iterar sobre a, b, x, e y para gerar todos os possíveis pares de índices e a condição se-então cria uma restrição na grade e grade [a] [b] [x] [y] só quando ab < XY.

Adicionando restrições específicas do problema

Depois que as restrições genéricas foram criadas e adicionadas ao modelo, o programa de demonstração adiciona as restrições que definem o quebra-cabeça Sudoku específico. O quebra-cabeça do demo tem 27 valores fixos, então você poderia usar a força bruta, da seguinte forma:

model.AddConstraint("v02", grid[0][2] == 6);
model.AddConstraint("v03", grid[0][3] == 2);
...
model.AddConstraint("v86", grid[8][6] == 2);

Não há nada de errado com uma abordagem de força bruta, mas porque os dados já foram colocados em uma matriz, é fácil transferir os valores usando uma chamada de método definido pelo programa auxiliar como este:

AddDataConstraints(data, model, grid);
where the helper is defined as:
static void AddDataConstraints(int[][] data, Model model, 
  Decision[][] grid)
{
  for (int r = 0; r < 9; ++r) {
    for (int c = 0; c < 9; ++c) {
      if (data[r][c] != 0) {
        model.AddConstraint("v" + r + c,
          grid[r][c] == data[r][c]);
      }
    }
  }
}

Observe o estranho acoplamento entre os objetos de modelo e de decisão. Código da biblioteca escrito por desenvolvedores para desenvolvedores que provavelmente referenciou os objetos de decisão (resposta) ao longo das linhas de model.grid[r][c]. O estilo incomum da biblioteca de MSF me levou cerca de três exemplos para se sentir confortável com isso.

Resolvendo o quebra-cabeça

Com tudo no lugar, o programa de demonstração pode resolver o enigma com este código:

Console.WriteLine("Solving. . . ");
int numSolutions = NumberSolutions(problem);
Console.WriteLine("There is/are " + 
  numSolutions + " Solution(s)");
Solution solution = problem.Solve();

O método NumberSolutions é um definido pelo programa auxiliar que é chamado para verificar se existem soluções de zero (que significa restrições conflitantes foram definidas de alguma forma) ou mais de uma solução:

static int NumberSolutions(SolverContext problem)
{
  int ct = 0;
  Solution soln = problem.Solve();
  while (soln.Quality == SolverQuality.Feasible) {
    ++ct;
    soln.GetNext();
  }
  return ct;
}

O método MSF resolver faz exatamente isso, colocando as respostas reais para os objetos de decisão, que são o objeto de modelo, que é associado por referência ao objeto SolverContext. Como um efeito colateral, o objeto de solução tem um campo de qualidade que pode ser um dos oito valores, incluindo realista e inviável. O método GetNext solução não retorna um valor explícito, mas modificar o campo de qualidade. Donculpe a mim para o projeto MSF.

A demo de Sudoku conclui exibindo as respostas armazenadas nos objetos de decisão dentro da matrix de grade:

for (int r = 0; r < 9; ++r) {
    for (int c = 0; c < 9; ++c) {
      double v = grid[r][c].GetDouble();
      Console.Write(" " + v);
    }
    Console.WriteLine("");
  }
  Console.WriteLine("End Solver Foundation Sudoku demo");
  Console.ReadLine();
} // Main

O método GetDouble extrai o valor de resposta do objeto de decisão. Lembre-se que respostas foram definidas para ser inteiros no intervalo de 1 a 9. No entanto, não há nenhum método Integer. GetInteger para que valores de resposta são implicitamente convertidos para o tipo double. Porque todos eles terminam com ponto-zero, quando exibido eles aparecem como inteiros, mesmo que eles são o tipo double.

Conclusão

O tipo de CSP descrito neste artigo é realmente um problema de otimização combinatória. Ou seja, o objetivo é encontrar a combinação de valores que tem o menor número de erros restrição. As informações aqui apresentadas devem permitir que você use a biblioteca MSF para resolver muitos problemas de otimização combinatória prático, que você pode se deparar.

Eu tenho uma confissão. O namorado da minha irmã me apresentou a Sudoku em uma viagem de família para Palm Springs há alguns anos. Ele consistentemente bate em mim sempre que competimos por tempo em Sudoku, palavras cruzadas ou qualquer coisa. Ele não sabe que é possível resolver qualquer quebra-cabeça Sudoku com esse código. Estou ansioso para nossa próxima viagem em família. Eu vou ter meu laptop.

Dr. James McCaffrey funciona para Microsoft Research em Redmond, Wash. Ele trabalhou em vários produtos Microsoft, incluindo o Internet Explorer e Bing. Contactá-lo no jammc@microsoft.com.

Agradecemos ao seguinte especialista técnico pela revisão deste artigo: Kirk Olynyk (Microsoft Research)