A 9×9 sudoku solver in C. The algorithm incorporates backtracking. Backtracking is a great technique to use when the problem is NP complete and the state space isn’t huge. It takes only a few seconds to solve a hard 9×9 sudoku puzzle on a 1.4GHz machine. The program in txt can be found here. Sadly I can only upload image files so the file is a PDF.

The program first reads in the sudoku puzzle from a file named “myfile.txt”. The algorithm begins by recursively fills up the puzzle, and if no feasible input can be found for an empty block before a solution is reached, it returns to the previous empty block and attempts with another feasible input. The heuristic is very straighforward, it just ensures the input does not appear in the same row, the same column, and the same square.

An important lesson I learnt after is that for NP complete problems, if brute force isn’t working, that’s because you’re not using enough, or you just need more hardware.

### Like this:

Like Loading...

*Related*

#1 by

joxion November 22, 2007 - 1:19 amvery thx for this code. useful!

#2 by

Brandonon January 26, 2008 - 9:40 pmThe code is helpful for a class I am taking to get the idea of backtracking to solve NP problems. However I don’t know if this is a problem or not, but I attempted to give it a puzzle to complete and it was unable to do so. It was capable of placing 6 digits in locations but only 3 of which are in correct locations. Any suggestions?

#3 by

Fazlay Rabbion March 17, 2008 - 7:19 pmThanx for your code. It helps me to solve the 8 queens problem and gives me the implementation of backtracking.

#4 by

nadiaon April 18, 2008 - 8:35 am#include

//#include

//#include

int i,j,k,a[10,10],o,x[100],y[100];

void display();

int getnum();

void solve(int [],int [],int);

int check(int ,int );

void main()

{

clrscr();

printf(“\n\nEnter the elements of SUDOKU in rowwise.\n[ Enter '0' if element is absent. ]“);

for(i=1;i<=9;i++)

for(j=1;j<=9;j++)

scanf(“%d”,&a[i][j]);

printf(“\n\nEntered SUDOKU\n\n”);

display();

printf(“\nEnter any key for solution….\n”);

getch();

o=getnum();

solve(x,y,1);

}

int getnum()

{

int c=0;

for(i=1;i<=9;i++)

{

for(j=1;j<=9;j++)

{

if(a[i][j]==0)

{

c++;

x[c]=i;

y[c]=j;

}

}

}

return(c);

}

void display()

{

for(i=1;i<=9;i++)

{

for(j=1;j<=9;j++)

{

if(a[i][j]!=0)

printf(” %d”,a[i][j]);

else

printf(” “);

}

printf(“\n\n”);

}

}

void solve(int p[100],int q[100],int n)

{

for(k=1;k<=9;k++)

for(i=p[n];i<=p[n];i++)

for(j=q[n];j<=q[n];j++)

{

a[i][j]=k;

if(n<0)

solve(p,q,n++);

int ch=check(1,0);

if(ch!=0)

{

display();

getch();

//exit(0);

}

}

}

}

int check(int n,int r)

{

int f=0,cont=0;

if(r==1)

{

for(k=1;k<=9;k++)

{

for(i=n;i<=n;i++)

for(j=1;j<=9;j++)

{

if(k==a[i][j])

f++;

}

if(f!=1)

return(0);

else

cont++;

f=0;

}

if(cont!=9)

return(0);

else if(n==9)

check(1,0);

else

check(n++,1);

}

else

{

for(k=1;k<=9;k++)

{

for(i=1;i<=9;i++)

for(j=n;j<=n;j++)

{

if(k==a[i][j])

f++;

}

if(f!=1)

return(0);

else

cont++;

f=0;

}

if(cont!=9)

return(0);

else if(n!=9)

check(n++,1);

}

}

#5 by oduikq bqjkl on July 10, 2008 - 1:03 am

ofxkq diyonfuk jlxmikzen xbspjnmv velqdg lemu dnqohguxt

#6 by

georgeon February 6, 2009 - 6:19 pmYour “input_value” can definitely be waaay simpler.

Try something like this:

/*Returns 1 if n is allowed in position [a,b] of sudoku[9][9]

and 0 if not*/

int can_put_n_here(int n, int sdku[][9] ,int a, int b)

{

int i;

for(i=0; i<9; ++i){

if(sdku[a][i]==n || sdku[i][b]==n || sdku[3*(a/3)][3*(b/3)+9*(i/3)+(i % 3)]==n)

return(0);

}

return(1);

}

For a given n, a and b and for a given 9X9 matrix sdku,

it checks if n is allowed to be put in the position[a][b].

If it is, it returns 1. If it is not, it returns 0.

#7 by Boss Resurfacing on September 6, 2009 - 9:00 pm

Off topic – Help with PM?

lost password

Boss Resurfacing

Boss Resurfacing

#8 by

narendra umateon April 23, 2010 - 4:45 pm[compact code for input_value]

int input_value(int ipos,int jpos,int value)

{

for(int k=0;k<9;k++)

if(outputArray[k][jpos]==value||outputArray[ipos][k]==value)

return 0;

int istart=(ipos/3)*3;

int jstart=(jpos/3)*3;

for(int i=istart;i<istart+3;i++)

for(int j=jstart;j<jstart+3;j++)

if(outputArray[i][j]==value)

return 0;

return value;

}

[also insert 'return 0;' before 2nd end bracket of the function backtrack]

saying this because my code worked well on ubuntu gcc but solaris was acting funny. so adding insert 0 explicitly does not hurt at all.

great code by the way helped me a lot. thanks

#9 by

Anandon September 30, 2010 - 6:59 pmI am unable to find the source code. Would you please let me know where the code is?

#10 by

vitalon December 15, 2010 - 7:13 amjust click on “here” in the text…

… The program in txt can be found –>here<– …

#11 by

Meon January 14, 2011 - 4:37 amHow can i see the code? Clicking on “here”… doesn`t work..

#12 by

Cyruson April 4, 2011 - 10:15 am//

// The following code is public domain (written in 2005 by Nick Smallbone)

// It can be found at http://www.8325.org/sudoku/

//

// It works by keeping track of which numbers can be used to fill the remaining

// cells in each row, column and block. It then will only fill a cell with a

// number that is valid for that row, column and block.

// On every recursion, it chooses the cell with the least possible number

// available to choose from. This has the rather nice effect that impossible

// cells are noticed straight away without any special cases, and cells with

// only one possibility are filled in straight away.

#include

#include

using namespace std;

FILE*input;

input=fopen(“input.txt”,”r”);

while((fscanf(input,”%d”,&ary[i])) !=EOF){

printf(“%d “,ary[i]);

i++ ;

}

// The size of the Sudoku game

static const unsigned blockSize = 3;

static const unsigned gridSize = blockSize * blockSize;

//

// Some functions for representing sets as bitfields

// (counting from 0)

//

typedef unsigned long bitfield;

// No bit we’ll be using is above this

static const bitfield maskMax = 1 << gridSize;

// A bitfield with all bits set

static const bitfield allSet = maskMax – 1;

// Returns the size of the set

static unsigned bitCount(bitfield bits) {

unsigned result = 0;

bitfield mask = 1;

while(mask != maskMax) {

if (bits & mask)

result++;

mask *= 2;

}

return result;

}

// Returns a bitfield representing {num}

static inline bitfield bitFor(unsigned num) {

return 1 << (num – 1);

}

class Puzzle {

// The value of any empty cell (i, j) comes from

// rows[i] & cols[j] & blocks[i/3][j/3]

bitfield rows[gridSize];

bitfield cols[gridSize];

bitfield blocks[blockSize][blockSize];

// This contains invalid if the cell is empty,

// its value otherwise.

unsigned cells[gridSize][gridSize];

public:

// This number is invalid, and represents an empty cell

static const unsigned invalid = gridSize + 1;

Puzzle() {

// Better initialise the arrays

unsigned i, j;

for (i = 0; i < gridSize; i++) rows[i] = allSet;

for (i = 0; i < gridSize; i++) cols[i] = allSet;

for (i = 0; i < blockSize; i++)

for (j = 0; j < blockSize; j++)

blocks[i][j] = allSet;

for (i = 0; i < gridSize; i++)

for (j = 0; j < gridSize; j++)

cells[i][j] = invalid;

}

// Return the set of values which could be at (i, j)

inline bitfield candidates(unsigned i, unsigned j) {

assert(cells[i][j] == invalid);

return rows[i] & cols[j] &

blocks[i/blockSize][j/blockSize];

}

// Fill in the cell at (i, j)

inline void set(unsigned i, unsigned j, unsigned n) {

bitfield bit = bitFor(n);

// Check this is a valid value for the cell

assert((candidates(i, j) & bit) != 0);

// No other cells in the row, column or block

// can now have this value

rows[i] &= ~bit;

cols[j] &= ~bit;

blocks[i/blockSize][j/blockSize] &= ~bit;

cells[i][j] = n;

}

// Erase the cell at (i, j)

inline void unset(unsigned i, unsigned j, unsigned n) {

bitfield bit = bitFor(n);

// Make sure it was already set

assert(cells[i][j] == n);

rows[i] |= bit;

cols[j] |= bit;

blocks[i/blockSize][j/blockSize] |= bit;

cells[i][j] = invalid;

}

// Find the cell with the lowest number of candidates

// in the specified rectangular area.

// It searches in iMin <= i < iMax

// and jMin <= j < jMax

// Return false if the grid is full.

bool findMin(unsigned iMin, unsigned iMax, unsigned jMin, unsigned jMax,

unsigned &outI, unsigned &outJ)

{

bool found = false;

unsigned count = 0;

for (unsigned i = iMin; i < iMax; i++)

for (unsigned j = jMin; j < jMax; j++)

if (cells[i][j] == invalid &&

(!found || bitCount(candidates(i, j)) < count))

{

count = bitCount(candidates(i, j));

outI = i;

outJ = j;

found = true;

}

return found;

}

// Returns the value of a certain cell, or invalid

inline unsigned getCell(unsigned i, unsigned j) { return cells[i][j]; }

};

// Tries to solve the puzzle in-place. It returns true if it could fill in

// all the squares between iMin and iMax and jMin and jMax, false otherwise.

// If destructive is false it will reverse all its changes once it

// finds a solution or gives up.

// If checkBlocks is true it will try to fill in each 3×3 block separately

// before it starts – if it can't do that then it can't solve the puzzle

bool solve(Puzzle &puzzle, unsigned iMin, unsigned iMax,

unsigned jMin, unsigned jMax, bool destructive, bool checkBlocks)

{

// Check that each block can be filled if we've been asked to

if (checkBlocks) {

for (unsigned i = 0; i < blockSize; i++)

for (unsigned j = 0; j < blockSize; j++)

if (!solve(puzzle,

i*blockSize, i*blockSize + blockSize,

j*blockSize, j*blockSize + blockSize,

false, false))

return false;

}

// Guess a good cell to brute-force with

unsigned i;

unsigned j;

if (!puzzle.findMin(iMin, iMax, jMin, jMax, i, j))

// We must have finished

return true;

// Iterate through the possible values this cell could have

unsigned num = 1;

unsigned mask = bitFor(num);

while(mask != maskMax) {

if (puzzle.candidates(i, j) & mask) {

// Try this number

puzzle.set(i, j, num);

bool solved = (solve(puzzle, iMin, iMax, jMin, jMax,

destructive, checkBlocks));

// Reverse the changes if needed

if (!solved || !destructive)

puzzle.unset(i, j, num);

if (solved)

return true;

}

// Advance to the next number

mask *= 2;

num++;

}

// None of the possibilities for cell (i,j) work

return false;

}

// Reads in a puzzle from standard input

void readPuzzle(Puzzle &p) {

for (unsigned i = 0; i < gridSize; i++) {

for (unsigned j = 0; j > c;

if (c >= ’1′ && c > endl;

}

}

// Prints out a (hopefully) completed puzzle

void printPuzzle(Puzzle &p) {

for (unsigned i = 0; i < gridSize; i++) {

for (unsigned j = 0; j < gridSize; j++) {

if (p.getCell(i, j) == p.invalid)

cout << " ";

else

cout << p.getCell(i, j);

}

cout << endl;

}

}

// Solve and print out a puzzle

void outputSolution(Puzzle &p) {

if (solve(p, 0, gridSize, 0, gridSize, true, true))

printPuzzle(p);

}

int main() {

Puzzle p;

readPuzzle(p);

outputSolution(p);

system ("pause");

return 0;

}

Does anyone can teach me how to put file*input and how to write the code inside this program..

#13 by

manikon August 17, 2011 - 6:57 amcn u plzz explain backtrack function a bit in detail…i could not understand it…how backtracking is occuring…??

#14 by

kjhon December 21, 2011 - 4:58 pmwhat do i need to do if i want to chenge the range of thevalid number from 1-9 to 0-8.

#15 by Hung on May 18, 2013 - 6:22 am

Wow, fantastic blog layout! How long have you been blogging for?

you make blogging look easy. The overall look of your

web site is wonderful, let alone the content!

#16 by tablettegraphique123.net on July 3, 2013 - 9:33 am

These are really enormous ideas in concerning blogging.

You have touched some pleasant things here.

Any way keep up wrinting.

#17 by

maddyon July 18, 2013 - 7:17 pmsir..ur prgm is just brilliant … could u please explain the scanning its own square in the input_value() and backtack() in a bit more detail