Att lösa en Sudoku i C#

Jag satt på bussen hem igår och skulle lösa dagens Sudoku i Metro. Jag löser inte Sudoku särskilt ofta, men hur svårt kan det vara? Det visade sig svårare än jag trodde…

Jag slutade snart med att lösa Sudokun och började i stället fundera över en lösningsalgoritm. Innan jag var hemma så hade jag en fungerande prototyp och under kvällen kunde jag inte låta bli att skriva om algoritmen några gånger och försöka få den elegantare. Här blev resultatet.

// Recursive function to solve a Sudoku.
static bool Solve(ref int[] s,int p, int v)
{
    s[p] = v;                                   // Enter value v in cell p.
    while (p < 81 && s[p] > 0) p++;             // Move forward to an empty cell.
    if (p == 81) return true;                   // If no more cells, we are finished.

    bool[] n = new bool[10];                    // Lets calculate allowed numbers in the cell.
    for (int i = 0; i < 9; i++)                 // For each of the 9 neighbouring cells,
        n[s[p/27*27 + i/3*9 + p%9/3*3 + i%3]] = // in the same box as p,
        n[s[p/9*9 + i]] =                       // in the same row as p,     
        n[s[p%9 + 9*i]] = true;                 // in the same col as p; disallow the number. 
          
    for (int i = 1; i <= 9; i++)                // Now we try the allowed numbers. 
        if (!n[i] && Solve(ref s, p, i))        // If number is allowed, try solving again.
            return true;                        // Return success if solved.;
                
    s[p] = 0;                                   // If all allowed colours are tested,
    return false;                               // empty the cell and go back.
}

Sudokun sparas in en int[81]-array där noll representerar en tom ruta. Rutorna är numrerade radvis.

Det som jag är nöjd över är raderna som beräknar tillåtna nummer för en tom ruta: Givet en position p (0-80)och en delta-position i (0-9) så har jag gjort tre formler som hittar cellerna i samma rad, kolumn och box som p. Allt med lite heltalsdivion och modulus-räkning.

Programmet läser från standard input och skriver till standard output.