[...] a carefully designed application-program interface for Internet optimization services would do much to encourage development of client applications- Fourer, Goux
larsbeck

Optimization.Framework: Howto build a sudoku solver

by Lars on April 20, 2011

In our first tutorial we explain how you can use the framework in order to build a sudoku solver.

To download the source code click here

To see the source code click read the full article.

Credits to my brother Nils, who cut this video for me. I know this is a lot of work, thanks!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Common;
using Optimization;
using Optimization.Solver.Gurobi;

namespace Sudoku_Solver
{
    class Program
    {
        static void Main(string[] args)
        {
            var board = new Board();
            int dimension = 9;

            for (int i = 0; i < dimension; i++)
            {
                board.Columns.Add(new Column());
                board.Rows.Add(new Row());
                board.Squares.Add(new Square());
            }
            var squares = board.Squares.ToList();
            int k = 0;
            foreach (var column in board.Columns)
            {
                int j = 0;
                foreach (var row in board.Rows)
                {
                    var cell = new Cell();
                    column.Cells.Add(cell);
                    row.Cells.Add(cell);
                    board.Cells.Add(cell);
                    int val = ((k / (int)Math.Sqrt(dimension)) * (int)Math.Sqrt(dimension) + j / (int)Math.Sqrt(dimension));
                    squares[val].Cells.Add(cell);
                    j++;
                }
                k++;
            }

            var numbers = Enumerable.Range(1, dimension);
            var cellvariables = new VariableCollection("cellVariable", 0, 1, VariableType.Integer, board.Columns,
                                                       board.Rows, numbers);

            var model = new Model();

            board.Cells.ForEach(
                cell => model.AddConstraint(Expression.Sum(numbers.Select(number => cellvariables[cell.Column, cell.Row, number])) == 1)
                );

            board.Columns.ForEach(
                column =>
                    numbers.ForEach(
                    number =>
                        model.AddConstraint(Expression.Sum(column.Cells.Select(cell => cellvariables[cell.Column, cell.Row, number])) == 1)
                    )
                );

            board.Rows.ForEach(
                row =>
                    numbers.ForEach(
                    number =>
                        model.AddConstraint(Expression.Sum(row.Cells.Select(cell => cellvariables[cell.Column, cell.Row, number])) == 1)
                )
            );

            board.Squares.ForEach(
                square =>
                    numbers.ForEach(
                    number =>
                        model.AddConstraint(Expression.Sum(square.Cells.Select(cell => cellvariables[cell.Column, cell.Row, number])) == 1)
                    )
                );

            var columns = board.Columns.ToList();
            var rows = board.Rows.ToList();

            cellvariables[columns[0], rows[1], 7].LowerBound = 1;

            var solver = new GurobiSolver();
            var solution = solver.Solve(model);
            cellvariables.SetVariableValues(solution.VariableValues);

            board.Rows.ForEach(
                row =>
                {
                    board.Columns.ForEach(
                        column =>
                        numbers.ForEach(
                            number =>
                            {
                                if (cellvariables[column, row, number].Value == 1)
                                {
                                    Console.Write(number + " ");
                                }
                            }
                            )
                        );
                    Console.WriteLine();
                }

                );

            Console.Read();
        }
    }
}
  • Digg
  • del.icio.us
  • Facebook
  • Google Bookmarks
  • FriendFeed
  • LinkedIn
  • Live
  • MisterWong
  • MySpace
  • Netvibes
  • PDF
  • Twitter

Leave a Comment

Previous post:

Next post: