Tuesday, June 10, 2008

Project Euler p96 - solving sudoku

This is interesting one. Problem description:
-----------------------------------------------
Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.
`0 0 3  0 2 0  6 0 09 0 0  3 0 5  0 0 10 0 1  8 0 6  4 0 00 0 8  1 0 2  9 0 07 0 0  0 0 0  0 0 80 0 6  7 0 8  2 0 00 0 2  6 0 9  5 0 08 0 0  2 0 3  0 0 90 0 5  0 1 0  3 0 0===================4 8 3  9 2 1  6 5 79 6 7  3 4 5  8 2 12 5 1  8 7 6  4 9 35 4 8  1 3 2  9 7 67 2 9  5 6 4  1 3 81 3 6  7 9 8  2 4 53 7 2  6 8 9  5 1 48 1 4  2 5 3  7 6 96 9 5  4 1 7  3 8 2`

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.

The 6K text file, sudoku.txt (right click and 'Save Link/Target As...'), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.
-----------------------------------------------

Well, back to more understandable language like C# :-). Solution is done as semi brute-force, iterative method. Solution is quick enough - fifty puzzles are solved in just 122 ms. So this is it:

`class Program    {        static int[][][] ReadSudoku(string file)        {            StreamReader sr = new StreamReader(file);            int[][][] res = new int[50][][];            int row = 0;            int sud = -1;            string line;            while (!sr.EndOfStream)            {                line = sr.ReadLine();                if (line.ToLower().IndexOf("grid") > -1)                {                    row = 0;                    sud++;                    res[sud] = new int[9][];                }                else                {                    res[sud][row] = Array.ConvertAll(line.ToCharArray(), c =>                                     { return int.Parse(c.ToString()); });                    row++;                }            }            sr.Close();            return res;        }        static void ShowSudoku(int[][] sud)        {            string o;            o = sud.Aggregate("", (agg, next) =>            {                return agg +                    ((agg == "") ? "":"\n") +                    next.Aggregate("|", (agg2, next2) => {                         return agg2 + next2.ToString(); }) + "|";            });            o = "-----------\n" + o + "\n-----------";            o = o.Replace("0", ".");            Console.Write(o);        }        static bool ValueIsValid(int[][] grid, int val, int row, int col)        {            int regc, regr;            int lc, lr;            if (val == 0)                return false;            // checking row and column            for (int i = 0; i < 9; i++)                if ((grid[row][i] == val && i != col) ||                     (grid[i][col] == val && i != row))                    return false;                        // checking 3x3 region            regr = 3*(row / 3);            regc = 3*(col / 3);            for (int i = 0; i < 3; i++)            {                lc = regc + i;                for (int j = 0; j < 3; j++)                {                    lr = regr + j;                    if (lc != col || lr != row)                        if (grid[lr][lc] == val)                            return false;                }            }            return true;        }        static void CellWithMinValid(int[][] grid,                                     out int rowo,                                     out int colo)        {            int row = -1, col = -1;            int minvalid = 9;            int valcount;            for (int i = 0; i < grid.Length; i++)            {                for (int j = 0; j < grid[i].Length; j++)                {                    if (grid[i][j] == 0)                    {                        valcount = 0;                        for (int k = 1; k < 10; k++)                            if (ValueIsValid(grid, k, i, j))                                valcount++;                        if (valcount < minvalid)                        {                            minvalid = valcount;                            row = i;                            col = j;                        }                    }                    if (minvalid == 1) break;                }                if (minvalid == 1) break;            }            rowo = row;            colo = col;        }        static void SolveSudoku(int[][] grid)        {            int row, col;            int curval;            int iter;            bool force;            int[,] steps = new int[81, 2];            CellWithMinValid(grid, out row, out col);            grid[row][col] = 1;            steps[0, 0] = row;            steps[0, 1] = col;            force = false;            iter = 0;            while (row > -1)            {                curval = grid[steps[iter, 0]]                             [steps[iter, 1]];                if (ValueIsValid(grid, curval,                                 steps[iter, 0],                                 steps[iter, 1]) && !force)                {                    CellWithMinValid(grid, out row, out col);                    if (row != -1)                    {                        force = false;                        iter++;                        grid[row][col] = 1;                        steps[iter, 0] = row;                        steps[iter, 1] = col;                    }                }                else                {                    curval++;                    if (curval < 10)                    {                        grid[steps[iter, 0]]                            [steps[iter, 1]] = curval;                        force = false;                    }                    else                    {                        grid[steps[iter, 0]]                            [steps[iter, 1]] = 0;                        force = true;                        iter--;                    }                }            }        }        static void SolveAll(string file)        {            int[][][] sud = ReadSudoku(file);            int tot = 0;            for (int i = 0; i < sud.Length; i++)            {                SolveSudoku(sud[i]);                tot += (sud[i][0][0] * 100) +                     (sud[i][0][1] * 10) +                     (sud[i][0][2]);            }            Console.WriteLine("Answer to projectEuler {0}\nLast sudoku solution:\n",tot);            ShowSudoku(sud[49]);        }        static void Main(string[] args)        {            System.Diagnostics.Stopwatch sw =                 new System.Diagnostics.Stopwatch();            sw.Start();            SolveAll("C:\\ProjectEuler\\sudoku.txt");            sw.Stop();            Console.WriteLine("\n50-ty sudoku`s solved in {0} ms",                             sw.ElapsedMilliseconds);            Console.ReadLine();        }    }`

As always - have fun!.