//server/stuff/Sudoku Solver 2>
Main

Sudoku Solver 2

This solver uses solving order arrangement, variable history and a constrained grid, making it much more efficient in solving boards with more unknowns, as compared to my previous solver. In ambigious cases, it'll return the first solution. It's extremely efficient at solving cases where there are a large number of unknowns, such as

8.9...3.....7.1...5.........7.....263...9.......1...4..6.2....4....8.5...........
..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9
..........................9................9...1............9...3..4..6...9..1..5
...............................................1........3..5..........7..9......4
.....9..........9...5...4........3..3........4..................9.............5..
Note that except for the first one, I don't expect these new test cases to be human solvable. The second is supposed to be a "worst case" scenario for a brute force solver, and this constrained grid solver solves it in approximately 1% to 5% of the time (on average) it would take an iterative brute force solver. This massive speedup is by sorting the variables (from least to most complex) before starting to solve them, so less time is spent on the more complex variables due to early-out when the simpler variables leading to it invalidate the tree branch.

Update - Dec 30th, 2009: Variables are sorted according to complexity in their local 3x3 cells, then globally by relevance, which is a measure of how much a variable may be simplified by another variable. Example, a,b and c are adjacent variables solved in the order abc, with a=(1,2,3), b=(4,5,6) and c=(2,3,6), it would be more efficient to work with c after a, instead of c after b after a. This same concept is also extended to reorder the solving of 3x3 squares.

Input:
A puzzle

Output:
A printed version of the board
Number of variables eliminated by completing squares (relaxing constraints)
Number of remaining variables
A complexity measurement for each 3x3 box of the board
The order in which the boxes' variables will be solved (0 to 8)
Each variable in solving order, in the format: Number of possiblities, complexity of parent box, solving priority of parent box, followed by its possible values.
And last, hopefully, a solved board

Download exe + cpp

Show previous test cases 
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <ctime>
#include <windows.h>

using namespace std;

struct Var
{
    int x, y, bx, by;
    bool CanBe[9];
    int v[9];
    int vf[9];
    int vnum;
    
    int boxcomplexity;
    int boxpriority;
    
    Var(int x, int y)
    : x(x), y(y)
    {
        bx = (int)(x / 3);
        by = (int)(y / 3);
        for (int i = 0; i < 9; i++)
        {
            CanBe[i] = true;
        }
        vnum = 0;
    }
};

int varfield[10];
void ClearBitfields(int n[9][9], int bx[9], int by[9], int bo[3][3])
{
    for (int i = 0; i < 10; i++)
    {
        varfield[i] = 1 << i;
    }
    for (int i = 0; i < 9; i++)
    {
        bx[i] = by[i] = 0;
        bo[i / 3][i % 3] = 0;
    }
    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            if (n[x][y])
            {
                bx[x] |= varfield[n[x][y]];
                by[y] |= varfield[n[x][y]];
                bo[x / 3][y / 3] |= varfield[n[x][y]];
            }
        }
    }
}

//Returns the box number of a variable (9 possible boxes, 3x3 each)
int varbox(Var& v)
{
    int x = v.x / 3;
    int y = v.y / 3;
    
    return (3 * y) + x;
}

//Returns true if this variable is influenced by, or influences, a box
bool relatedbox(Var& v, int i)
{
    int x = v.x / 3;
    int y = v.y / 3;
    int bx = i % 3;
    int by = i / 3;
    
    return bx == x || by == y;
}

//Returns the number of permutations in a specified 3x3 box
int boxcomplexity(std::vector<Var>& vars, int box)
{
    int c = 1;
    for (int i = 0; i < vars.size(); i++)
    {
        if (varbox(vars[i]) == box) { c *= vars[i].vnum; }
    }
    for (int i = 0; i < vars.size(); i++)
    {
        if (varbox(vars[i]) == box) { vars[i].boxcomplexity = c; }
    }
    return c;
}

//Compares two variables, returns true if a should be calculated before b
bool cmpvar(Var& a, Var& b)
{
    int va = a.boxpriority;
    int vb = b.boxpriority;
    
    if (va != vb) { return va < vb; }
    
    int vc = a.boxcomplexity;
    int vd = b.boxcomplexity;
    if (vc != vd) { return vc < vd; }
    
    return a.vnum < b.vnum;
}

//Returns the number of possible values two variables share in common
//or 0, if they don't influence each other
int relvar(Var& a, Var& b)
{
    bool adj = false;
    int c = 0;
    if (a.x == b.x || a.y == b.y) { adj = true; }
    if ((int)(a.x / 3) == (int)(b.x / 3)) { adj = true; }
    if ((int)(a.y / 3) == (int)(b.y / 3)) { adj = true; }
    if (adj)
    {
        for (int i = 0; i < a.vnum; i++)
        {
            for (int j = 0; j < b.vnum; j++)
            {
                if (a.v[i] == b.v[j]) { c++; }
            }
        }
    }
    return c;
}

//Returns how many permutations of a box influence the contents of another box
float boxrel(std::vector<Var>& vars, int box, int boxrel)
{
    float vtotal = 1;
    float vshared = 1;
    for (int i = 0; i < vars.size(); i++)
    {
        if (varbox(vars[i]) == box)
        {
            int vn = 0;
            for (int x = 0; x < vars[i].vnum; x++)
            {
                vtotal++;
                for (int j = 0; j < vars.size(); j++)
                {
                    if (varbox(vars[j]) == boxrel &&
                        relvar(vars[i], vars[j]))
                    {
                        for (int y = 0; y < vars[j].vnum; y++)
                        {
                            if (vars[i].v[x] == vars[j].v[y])
                            {
                                vshared++;
                            }
                        }
                    }
                }
            }
        }
    }
    return vshared / vtotal;
}

//Returns true if value is a valid marker at x,y
bool CanSet(int n[9][9], int x, int y, int value)
{
    for (int i = 0; i < 9; i++)
    {
        if (n[i][y] == value) { return false; }
        if (n[x][i] == value) { return false; }
    }
    
    int BoxStartX = (int)(x / 3) * 3;
    int BoxStartY = (int)(y / 3) * 3;
    for (int ix = BoxStartX; ix < BoxStartX + 3; ix++)
    {
        for (int iy = BoxStartY; iy < BoxStartY + 3; iy++)
        {
            if (n[ix][iy] == value)
            {
                return false;
            }
        }
    }
    
    return true;
}

//Searches for and fills cells with only one possible value
//false if it doesn't find any
bool RelaxConstraints(int n[9][9])
{
    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            if (!n[x][y])
            {
                int v = -1;
                int num = 0;
                for (int i = 1; i < 10; i++)
                {
                    if (CanSet(n, x, y, i))
                    {
                        v = i;
                        num++;
                    }
                }
                if (num == 1)
                {
                    n[x][y] = v;
                    return true;
                }
            }
        }
    }
    return false;
}

void Print(int n[9][9])
{
    for (int y = 0; y < 9; y++)
    {
        for (int x = 0; x < 9; x++)
        {
            if (n[x][y] == 0) { cout << ' '; } else { cout << n[x][y]; }
            if ((x + 1) % 3 == 0 && x < 9 - 1) { cout << '|'; } else { cout << "  "; }
            if (x == 9 - 1)
            {
                cout << endl;
                if ((y + 1) % 3 == 0 && y < 9 - 1) { cout << "-------+-------+-------" << endl; }
            }
        }
    }
    cout << endl;
}

bool Solved(int n[9][9])
{
    for (int y = 0; y < 9; y++)
    {
        int Sum = 0;
        for (int x = 0; x < 9; x++)
        {
            Sum += n[x][y];
        }
        if (Sum != 45) { return false; }
    }
    
    for (int x = 0; x < 9; x++)
    {
        int Sum = 0;
        for (int y = 0; y < 9; y++)
        {
            Sum += n[x][y];
        }
        if (Sum != 45) { return false; }
    }
    
    for (int yoff = 0; yoff < 9; yoff += 3)
    {
        for (int xoff = 0; xoff < 9; xoff += 3)
        {
            bool Used[10] = { 0 };
            
            for (int ix = 0; ix < 3; ix++)
            {
                for (int iy = 0; iy < 3; iy++)
                {
                    int i = n[xoff + ix][yoff + iy];
                    if (Used[i]) { return false; }
                    Used[i] = true;
                }
            }
        }
    }
    
    for (int y = 0; y < 9; y++)
    {
        for (int x = 0; x < 9; x++)
        {
            if (n[x][y] == 0)
            {
                return false;
            }
        }
    }
    
    return true;
}

bool RecurseConfig(int n[9][9], int bx[9], int by[9], int bo[3][3], Var* vars, int cvar, int nvar)
{
    Var& v = vars[cvar];
    for (int i = 0; i < v.vnum; ++i)
    {
        int vf = v.vf[i];
        if ((bx[v.x] & vf) ||
            (by[v.y] & vf) ||
        (bo[v.bx][v.by] & vf))
        {
            continue;
        }
        
        n[v.x][v.y] = v.v[i];
        bx[v.x] |= vf;
        by[v.y] |= vf;
        bo[v.bx][v.by] |= vf;
        
        if (cvar < nvar - 1)
        {
            if (RecurseConfig(n, bx, by, bo, vars, cvar + 1, nvar))
            {
                return true;
            }
        }
        else if (Solved(n))
        {
            return true;
        }
        
        bx[v.x] ^= vf;
        by[v.y] ^= vf;
        bo[v.bx][v.by] ^= vf;
    }
    
    n[v.x][v.y] = 0;
    return false;
}

float Solve(int n[9][9], bool print)
{
    vector<Var> vars;
    
    LARGE_INTEGER start_hf, end_hf, frequency, time;
    QueryPerformanceCounter(&start_hf);
    QueryPerformanceFrequency(&frequency);
    
    int c = 0;
    while (RelaxConstraints(n))
    {
        c++;
    }
    if (print)
    {
        cout << c << " variables eliminated by completing squares." << endl;
    }
    
    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            if (!n[x][y])
            {
                Var v(x, y);
                for (int i = 0; i < 9; i++)
                {
                    v.CanBe[i] = CanSet(n, x, y, i+1);
                    if (v.CanBe[i])
                    {
                        v.v[v.vnum++] = i+1;
                    }
                }
                if (v.vnum == 1)
                {
                    n[x][y] = v.v[0];
                }
                else
                {
                    vars.push_back(v);
                }
            }
        }
    }
    if (!vars.size()) { return 0; }
    if (print)
    {
        cout << vars.size() << " variables." << endl;
    }
    
    if (print) { cout << "Box complexity:"; }
    
    int minc = 0;
    int bestbox = 0;
    for (int i = 0; i < 9; i++)
    {
        int c = boxcomplexity(vars, i);
        if (print) { cout << ' ' << c; }
        if (i == 0 || c < minc) { minc = c; bestbox = i; }
    }
    if (print) { cout << endl; }
    
    std::vector<int> boxorder;
    std::vector<int> boxorderout;
    int prevboxout = bestbox;
    for (int i = 0; i < 9; i++)
    {
        if (i != bestbox) { boxorder.push_back(i); }
    }
    boxorderout.push_back(bestbox);
    
    while (boxorder.size())
    {
        int besti = -1;
        float best = 0;
        for (int i = 0; i < boxorder.size(); i++)
        {
            float r = 0;
            for (int z = 0; z < boxorderout.size(); z++)
            {
                r += boxrel(vars, boxorder[i], boxorderout[z]);
            }
            if (r > best || besti == -1)
            {
                best = r;
                besti = i;
            }
        }
        if (besti == -1 || best < 0.01f)
        {
            besti = 0;
        }
        prevboxout = boxorder[besti];
        boxorderout.push_back(prevboxout);
        boxorder.erase(boxorder.begin() + besti);
    }
    
    if (print)
    {
        cout << "Box order: ";
        for (int i = 0; i < 9; i++)
        { cout << boxorderout[i] << ' '; }
        cout << endl;
    }
    
    for (int i = 0; i < vars.size(); i++)
    {
        int vb = varbox(vars[i]);
        for (int j = 0; j < 9; j++)
        {
            if (boxorderout[j] == vb)
            {
                vars[i].boxpriority = j; break;
            }
        }
    }
    
    if (print) { cout << endl; }
    
    if (vars.size())
    {
        std::sort(vars.begin(), vars.end(), cmpvar);
    }
    
    if (vars.size() && print)
    {
        cout << "Possibilities, box complexity, box priority" << endl;
        for (int i = 0; i < vars.size(); i++)
        {
            cout << vars[i].vnum << ' ' << vars[i].boxcomplexity << ' ' << vars[i].boxpriority;
            for (int j = 0; j < vars[i].vnum; j++)
            {
                cout << ' ' << vars[i].v[j];
            }
            cout << endl;
        }
        cout << endl;
    }
    
    int bx[9];
    int by[9];
    int bo[3][3];
    ClearBitfields(n, bx, by, bo);
    for (int i = 0; i < vars.size(); i++)
    {
        for (int j = 0; j < vars[i].vnum; j++)
        {
            vars[i].vf[j] = varfield[vars[i].v[j]];
        }
    }
    
    if (vars.size()) { RecurseConfig(n, bx, by, bo, &vars[0], 0, vars.size()); }
    
    QueryPerformanceCounter(&end_hf);
    time.QuadPart = end_hf.QuadPart - start_hf.QuadPart;
    float t = 1000.0f * (double)time.QuadPart / (double)frequency.QuadPart;
    if (print)
    {
        cout << "Solved in " << t << "ms." << endl;
        
        Print(n);
    }
    for (int j = 0; j < vars.size(); j++)
    {
        if (!vars[j].CanBe[n[vars[j].x][vars[j].y]-1])
        {
            if (print)
            {
                cout << "Error in solving " << endl;
                cout << vars[j].x << endl;
                cout << vars[j].y << endl;
                cout << n[vars[j].x][vars[j].y] << endl;
                cout << vars[j].CanBe[n[vars[j].x][vars[j].y]-1] << endl;
            }
            t = -1;
        }
    }
    return t;
}

int main()
{
    
    while (cin)
    {
        char str[9 * 9 + 1] = { 0 };
        
        int strptr = 0;
        char c;
        cout << "Input sudoku" << endl;
        while (strptr < 81 && cin >> c)
        {
            bool ischr = false;
            if (c >= '0' && c <= '9') { ischr = true; }
            if (c == '.') { ischr = true; }
            if (ischr) //(c != ' ' && c != '|' && c != '-' && c != '+' && c != ',' && c != '\"' && c != '\'')
            {
                str[strptr++] = c;
            }
        }
        str[strptr] = '\0';
        
        
        int n[9][9] = { 0 };
        for (int y = 0; y < 9; y++)
        {
            for (int x = 0; x < 9; x++)
            {
                char c = str[y * 9 + x];
                if (c != '.') { n[x][y] = c - '0'; }
            }
        }
        Print(n);
        Solve(n, true);
    }
    
    return 0;
}