Sudoku backtracking algorithm

Question

First of all, I'll state that this is a university assignment so I'm not asking for someone to write the code for me I just need to be pointed in the right direction. :)

Ok, so I need to write an algorithm to solve any (solvable) sudoku board of arbitrary size. I've written a recursive function that can solve any 9x9 board quickly (~1ms) but when I do larger boards (16x16) that are hard to solve it struggles.. I've had one test going for 20 minutes and it can't seem to solve it. It can solve easy 16x16 puzzles or even a blank 16x16 board so I don't think it's the dimensions that are the problem.. it's more likely to be the algorithm that is the problem I think.

Anyway, this is the basic logic of my program..

• I have a 3D vector that stores the possible values of my every square
• When a value is placed in a square then it is removed from the possible values of the surrounding square, row and column that it's in

Then my solve function is basically:

bool solve() {

    if (there are no unfilled squares)
        return true

    if (the board is unsolvable - there are empty squares that have no possible values)
        return false

    while (there are empty squares)
    {
        int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square

        if (squaresFilled == 0)
            break;
    }

    //exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess

    while (there are empty squares that have choices left) {

        find the square with the least number of choices

        if (the square with the least number of choices has 0 choices)
            return false; //not solvable.

        remove that choice from the 3D vector (vector that has the choices for each square)
        make a copy of the board and the 3D choices vector

        fill the square with the choice

        if (solve())
            return true; //we're done

        restore the board and choices vector 
        //the guess didn't work so keep looping and make a new guess with the restored board and choices -- the choice we just made has been removed though so it won't get made again.

    }

    return false; //can't go any further
}

Is there anything inefficient about this? Is there any way I could get it to work better? I'm guessing that a 16x16 board takes so long is because the decision tree for it is so large for a board that isn't filled in very much. It's weird though, because a 9x9 board will solve really fast.

Any ideas or suggestions would be absolutely awesome. If there's any information I've missed let me know too!

Recondite

I suggest you look into the dancing links algorithm, it is an interesting approach to solve these types of problems. (Completely different from your approach though.) – Pyrography

You algorithm is exponential, so it's not surprising that adding one extra degree of difficulty makes it run for a long time. By chance (i.e. running time/degree of difficulty of the problem + cpu/ram speed + program design) you're on the cuff. Meaning, your computer can handle e^f(81) but not e^f(256). Not surprising - if the first is 1ms, that means your computer handles around e^f(81) op/ms, which means it will take e^f(256) / e^f(81) ms for the second. That figure can be around e^170ms, which is longer than the universe has existed. – Ephram

f is just a gross estimate function, and the estimations should be considered an underestimate because I didn't take into account base change - your program is exponential with a variant base as well as exponent (~9^81 theoretical choices vs. ~16^256), and because the larger you get you'll lose speed, e.g. caching. – Ephram

@Pyrography I'd like to try and fix my original algorithm before completely changing it but thanks for the link, if I get desperate I might give it a shot! :) – Recondite

@davin.. ah that does make sense then. I really thought that I implemented the algorithm well though but I guess I might need to completely rethink it? – Recondite

Peter Norvig has also written a piece on solving Sudokus (only 9x9 though, but maybe helpful anyways): norvig.com/sudoku.html – Nedranedrah

Answer 1

Between filling the squares with only one choice and going full recursive on the board there are more advanced actions you can do. Lets take that "region" is one row, or one column, or one square region (3x3 or 4x4).

Tactic 1

If there are K squares in a region that can take only identical K numbers (for instance two squares that can take only 2 an 5, or three squares that can take only 1, 7 and 8) then all other squares in that region can't take those specific numbers. You need to iterate each region to weed out "taken" numbers, so you can find a square with only one logical choice (for instance third square with 2, 4 and 5 logically can take only 4, or fourth square with 1, 3, 7 and 8 logically can take only 3).

This has to bi solved with iteration if you consider the following example. A region has squares with this possible numbers:

A: 1 2 3
B: 2 3
C: 2 3 4 5
D: 4 5
E: 4 5

The algorithm should detect that squares D and E hold numbers 4 and 5, so 4 and 5 are excluded from other squares in the region. The algorithm then detects that squares B and C hold numbers 2 and 3, and so excludes them from other squares. This leaves square A with only number 1.

Tactic 2

If a number occurs in the region in only one square then logically that square holds that number.

Tactic 3

Tactics 1 and 2 are only special cases of Tactic 3 having K squares with only K identical numbers. You can have K squares and a set of K numbers and those K squares can hold any subset of those K numbers. Consider the following example of a region:

A: 1 2
B: 2 3
C: 1 3
D: 1 2 3 4

Squares A, B and C can hold only numbers 1, 2 and 3. That's K for K. That means that any other square can't logically hold these numbers, which leaves square D with only number 4.

Tactic 2 is special case of Tactic 3 when K = N - 1.

Tactic 4

Take advantage of regions overlap. Suppose that some number can exist only in certain squares of the region. If all those squares belong to another overlapping region then that number should be excluded from all other squares in this other region.

Tactic 5

Cache results. All regions should have a "dirty" flag that denotes that something in the region has changed from the last time the region is processed. You don't have to process the region with this flag not set.

---

Human beings use all those tactics, and really hate to guess a number, because backtracking is a real pain. Actually, the difficulty of a board is measured with the minimum number of guesses one has to make to solve the board. For most "extreme" boards one good guess is enough.

Reginareginald

But those techniques are human-like techniques. Is it more efficient to use those methods whenever possible? – Zoltai

I tailored the answer to OP's question. For the question "which Sudoku algorithm is fastest" there is ralu's answer. – Reginareginald

Answer 2

Fast algorhitm for solving sudoku is Algorithm X by Donald Knuth. You represent solving sudoku as exact cover problem and then use Algorithm X for solving EC problem. Then use DLX as efficient implementation of Algorithm X.

There is great explanation on wikipedia on how to apply exact cover for solving sudoku.

I can tell you that DLX is extremely fast fost solving sudoku in is commonly used in fastest algorhitm.

http://www.setbb.com/phpbb/index.php?mforum=sudoku is great forum whit probably best sudoku programmers.

Melainemelamed

Answer 3

I dont know if you have seen this link before. Also it may not be comparable to dancing links algorithm in efficiency as it uses naive form of backtracking. Anyway it works. See if it can be useful for you!

Also may be you can add a few lines for solving 'easy' squares. http://edwinchan.wordpress.com/2006/01/08/sudoku-solver-in-c-using-backtracking/

Poplar

Answer 4

You're algorithm looks fine. The problem is that you are using a brute-force approach, and therefore your running time is (number of characters)^(size of board) - so for 9x9 there are 9^9=387420489 and for 16x16 the running time is 16^16=18446744073709551616. you can see the difference.

Try finding a Dynamic programing approach

• If you are a first\second year student, just stay with what you have (and check correctness). Your teacher won't expect more.

Mecke

Really? My algorithm is brute force? I thought it was slightly better, is it not a backtracking algorithm? I guess I need to do some googling. Unfortunately I am a 2nd year student who's expected to be able to solve 16x16 puzzles in under 30 seconds. :( – Recondite

Answer 5

There is no need to treat the cells with only one possible number as special. You already visit the cells with the fewest number of possibilities first.

Also: when you "remove that choice from the 3D vector", you could also remove it from the other cells on the same {row, columns,box}. Bitmasks will probably fit in in nicely. (but the backtracking will become a bit harder)

Elizbeth

Answer 6

as @ralu mentioned, the fastest algorithm to solve sudoku is using DLX. below is a program i wrote in the past. it can solve 4*4 sudoku within 1 second.

suppose the input is like:

--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-


#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

const int INF=1<<30;
const int N=4;
const int MAXR=N*N*N*N*N*N+10;
const int MAXC=N*N*N*N*4+10;
const int SIZE=MAXR*MAXC/N/N;

int n,m;
int mat[MAXR][MAXC],r,c,ans;
int L[SIZE],R[SIZE],U[SIZE],D[SIZE],S[MAXC],C[SIZE],RH[SIZE],O[MAXC];
int a[MAXR];
char b[MAXR];
char s[N*N+10][N*N+10];
int head,cnt;

int node(int up,int down,int left,int right) {
    U[cnt]=up;D[cnt]=down;L[cnt]=left;R[cnt]=right;
    D[up]=U[down]=L[right]=R[left]=cnt;
    return cnt++;
}

void init() {
    cnt=0;
    head=node(0,0,0,0);
    for (int i=1;i<=c;i++) {
        C[i]=node(cnt,cnt,L[head],head);
        S[i]=0;
    }
    for (int i=1;i<=r;i++) {
        int rowh=-1;
        for (int j=1;j<=c;j++) if (mat[i][j]) {
            if (rowh==-1) {
                rowh=node(U[C[j]],C[j],cnt,cnt);
                RH[rowh]=i;
                C[rowh]=C[j];
                S[j]++;
            }
            else {
                int k=node(U[C[j]],C[j],L[rowh],rowh);
                RH[k]=i;
                C[k]=C[j];
                S[j]++;
            }
        }
    }
}

void remove(int col) {
    L[R[col]]=L[col];
    R[L[col]]=R[col];
    for (int i=D[col];i!=col;i=D[i])
        for (int j=R[i];j!=i;j=R[j]) {
            U[D[j]]=U[j];
            D[U[j]]=D[j];
            S[C[j]]--;
        }
}

void resume(int col) {
    for (int i=U[col];i!=col;i=U[i])
        for (int j=L[i];j!=i;j=L[j]) {
            S[C[j]]++;
            U[D[j]]=j;
            D[U[j]]=j;
        }
    L[R[col]]=col;
    R[L[col]]=col;
}

bool dfs(int k) {
    if (R[head]==head) {
        ans=k;
        return true;
    }
    int mins=INF,cur=0;
    for (int i=R[head];i!=head;i=R[i])
        if (S[i]<mins) {
            mins=S[i];
            cur=i;
        }
    remove(cur);
    for (int i=D[cur];i!=cur;i=D[i]) {
        O[k]=RH[i];
        for (int j=R[i];j!=i;j=R[j])
            remove(C[j]);
        if (dfs(k+1)) return true;
        for (int j=L[i];j!=i;j=L[j])
            resume(C[j]);
    }
    resume(cur);
    return false;
}

void makegraph() {
    r=0;
    for (int i=0;i<N*N;i++)
        for (int j=0;j<N*N;j++) {
            int t=(i/N)*N+(j/N);
            int p=i*N*N+j;
            if (s[i][j]=='-') {
                for (int k=1;k<=N*N;k++) {
                    r++;
                    mat[r][i*N*N+k]=1;
                    mat[r][N*N*N*N+j*N*N+k]=1;
                    mat[r][2*N*N*N*N+t*N*N+k]=1;
                    mat[r][3*N*N*N*N+p+1]=1;
                    a[r]=p;
                    b[r]='A'+k-1;
                }
            }
            else {
                int k=s[i][j]-'A'+1;
                r++;
                mat[r][i*N*N+k]=1;
                mat[r][N*N*N*N+j*N*N+k]=1;
                mat[r][2*N*N*N*N+t*N*N+k]=1;
                mat[r][3*N*N*N*N+p+1]=1;
                a[r]=p;
                b[r]=s[i][j];
            }
        }
}

int main() {
    freopen("sudoku.txt","r",stdin);
    freopen("sudoku_sol.txt","w",stdout);
        for (int i=0;i<N*N;i++)
            scanf("%s",s[i]);
        memset(mat,0,sizeof(mat));
        makegraph();
        c=N*N*N*N*4;

        init();
        ans=INF;
        dfs(0);
        for (int i=0;i<ans;i++)
            for (int j=i+1;j<ans;j++)
                if (a[O[i]]>a[O[j]]) swap(O[i],O[j]);

        for (int i=0;i<ans;i++) {
            printf("%c",b[O[i]]);
            if ((i+1)%(N*N)==0) printf("\n");
        }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

u can have a try :)

Hanan

R, S, b, k, a, p... use some real variable names! – Payne