# Sudoku solver

Page 1 of 1

## 11 Replies - 2303 Views - Last Post: 16 July 2009 - 06:01 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=114481&amp;s=7d3e9699d9e0f0190a5902ba2a23329d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 dejandenib

Reputation: 0
• Posts: 28
• Joined: 10-June 09

# Sudoku solver

Posted 13 July 2009 - 03:11 AM

I need to make a program which solves a Sudoku 9x9. If there are multiple solutions, first should be outputed the lexicographically smallest,then lexicographically largest. I solved this in c++, but it's too slow. I found a solution in java which is very fast and finds lexicographically smallest, and with changing this for( k=1; k<10; k++ ) if( possible[i][j][k] ) to this for( k=9; k>0; k-- ) if( possible[i][j][k] ) it finds the lexicographically largest. Because i need this to be done in c++, and i don't know very much java, can somebody help me in translating this from java to c++ or help me optimize the c++ solution?
The input in c++ should be like this
....1....
.9..5.4.3
7.846.1.5
926.85...
1.......2
...62.591
8.9.723.6
6.2.9..4.
....4....
Output
564213978
291758463
738469125
926185734
175934682
483627591
849572316
652391847
317846259
And in java it reads and outputs in text files and the input should look like this: first the number of test cases then the sudoku board
input
1
000000014
000708000
000000000
104005000
000200830
600000000
500040000
030000700
000090001
output
857926314
341758692
962431578
184365927
795214836
623879145
519647283
436182759
278593461

Here is a little help how to test two solutions. INput this
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
So here is the code in c++
```#include <iostream>
using namespace std;

bool row[10][10],col[10][10],sqr[10][10];
int a[10][10];
bool row2[10][10],col2[10][10],sqr2[10][10];
int a2[10][10];
char c[9][10];
bool ok;

void red()
{
int i,j,k;
for (k=1;k<=9;k++)

for (i=1;i<=9;i++)
for (j=i+1;j<=9;j++)
if (a[k][i]!=0 && a[k][j]!=0 && a[k][i]==a[k][j]) ok=false;
}

void kolona()
{
int i,j,k;
for (k=1;k<=9;k++)

for (i=1;i<=9;i++)
for (j=i+1;j<=9;j++)
if (a[i][k]!=0 && a[j][k]!=0 && a[i][k]==a[j][k]) ok=false;
}

void sudoku(int f,int g,int h,int d)
{
int i,j,ii,jj;
for (i=f;i<=g-1;i++)
for (j=h;j<=d-1;j++)
if (a[i][j]==0) continue; else
{
for (ii=i+1;ii<=g;ii++)
for (jj=j+1;jj<=d;jj++)
if (a[ii][jj]==0) continue; else
if (a[i][j]==a[ii][jj] && i!=ii && j!=jj) ok=false;
}
}

{
int i,j,k;
for (i = 1; i < 10; ++i)
for (j = 1; j < 10; ++j)
{
if (a2[i][j] == 0)
{
for (k = 9; k > 0; --k)
{
if (!row2[i][k] && !col2[j][k] && !sqr2[(i-1)/3*3+(j-1)/3+1][k])
{
a2[i][j] = k;
row2[i][k] = true;
col2[j][k] = true;
sqr2[(i-1)/3*3+(j-1)/3+1][k] = true;
return true;
else
{
a2[i][j] = 0;
row2[i][k] = false;
col2[j][k] = false;
sqr2[(i-1)/3*3+(j-1)/3+1][k] = false;
}
}
}
if (k == 0)
return false;
}
}
return true;
}

bool nagore()
{
int i,j,k;
for (i = 1; i < 10; ++i)
for (j = 1; j < 10; ++j)
{
if (a[i][j] == 0)
{
for (k = 1; k < 10; ++k)
{
if (!row[i][k] && !col[j][k] && !sqr[(i-1)/3*3+(j-1)/3+1][k])
{
a[i][j] = k;
row[i][k] = true;
col[j][k] = true;
sqr[(i-1)/3*3+(j-1)/3+1][k] = true;
if (nagore())
return true;
else
{
a[i][j] = 0;
row[i][k] = false;
col[j][k] = false;
sqr[(i-1)/3*3+(j-1)/3+1][k] = false;
}
}
}
if (k == 10)
return false;
}
}
return true;
}

int main()
{

ok=true;

int i,j;

for (i = 0; i < 9; ++i)
cin >> c[i];
for (i = 1; i < 10; ++i)
{
for (j = 1; j < 10; ++j)
{
if (c[i-1][j-1]=='.')  {a2[i][j]=0; a[i][j]=0;} else
{ a[i][j] = c[i-1][j-1] - '0';  a2[i][j] = c[i-1][j-1] - '0'; }
row[i][a[i][j]] = true;
col[j][a[i][j]] = true;
sqr[(i-1)/3*3+(j-1)/3+1][a[i][j]] = true;
row2[i][a[i][j]] = true;
col2[j][a[i][j]] = true;
sqr2[(i-1)/3*3+(j-1)/3+1][a[i][j]] = true;
}
}
/*  red();
kolona();

sudoku(1,3,1,3);
sudoku(1,3,4,6);
sudoku(1,3,7,9);
sudoku(4,6,1,3);
sudoku(4,6,4,6);
sudoku(4,6,7,9);
sudoku(7,9,1,3);
sudoku(7,9,4,6);
sudoku(7,9,7,9);
*/
if (!ok) cout<<"IMPOSSIBLE";  else
{
nagore();
for (int i = 1; i < 10; ++i)
for (int j = 1; j < 10; ++j)
if (a[i][j]==0) {  cout<<"IMPOSSIBLE"; goto top; } else
{
for (i = 1; i < 10; ++i)
{
for (j = 1; j < 10; ++j)
cout << a[i][j];
cout << endl;
}

cout << endl;
for (int i = 1; i < 10; ++i)
for (int j = 1; j < 10; ++j)
if (a[i][j]!=a2[i][j])
{
for (i = 1; i < 10; ++i)
{
for (j = 1; j < 10; ++j)
cout << a2[i][j];
cout << endl;
}
break;
}
}}
top:  system ("PAUSE");
return 0;
}

```

and the code in java

```
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.awt.*;
import java.awt.geom.*;

class C
{
PrintStream ps;

public String toString()
{
return "C";
}

public class Board
{
public int b[][];
public boolean possible[][][];

public Board()
{
b = new int[9][9];
possible = new boolean[9][9][10];

for( int i=0; i<9; i++ )
{
Arrays.fill( b[i], 0 );
for( int j=0; j<9; j++ )
{
Arrays.fill( possible[i][j], true );
}
}
}

public Board( Board old )
{
b = new int[9][9];
possible = new boolean[9][9][10];

for( int i=0; i<9; i++ ) for( int j=0; j<9; j++ )
{
b[i][j] = old.b[i][j];
for( int k=0; k<10; k++ )
{
possible[i][j][k] = old.possible[i][j][k];
}
}
}

public void makemove( int ii, int jj, int digit )
{
int i, j;

b[ii][jj] = digit;

for( int k=1; k<10; k++ ) possible[ii][jj][k] = false;

for( i=0; i<9; i++ )
{
possible[i][jj][digit] = false;
possible[ii][i][digit] = false;
}

int basei = (ii/3)*3;
int basej = (jj/3)*3;
for( i=0; i<3; i++ )for( j=0; j<3; j++ )
{
possible[basei+i][basej+j][digit] = false;
}
}

public void settle()
{
int i, j, k;

// This isn't necessary - it runs fast enough - but if you wanted to
// speed it up, here y'go.

boolean changed = true;
int counts[] = new int[10];
while( changed )
{
changed = false;

for( i=0; i<9; i++ )for( j=0; j<9; j++ )
{
int count = 0;
int which = 0;
for( k=1; k<10; k++ ) if( possible[i][j][k] )
{
++count;
which = k;
}

if( count == 1 )
{
makemove( i, j, which );
changed = true;
}
}

for( i=0; i<9; i++ )
{
Arrays.fill( counts, 0 );
for( j=0; j<9; j++ ) for( k=1; k<10; k++ )
{
if( possible[i][j][k] ) ++counts[k];
}

for( k=1; k<10; k++ ) if( counts[k]==1 )
{
for( j=0; j<9; j++ ) if( possible[i][j][k] )
{
makemove( i, j, k );
changed = true;
}
}
}

for( j=0; j<9; j++ )
{
Arrays.fill( counts, 0 );
for( i=0; i<9; i++ ) for( k=1; k<10; k++ )
{
if( possible[i][j][k] ) ++counts[k];
}

for( k=1; k<10; k++ ) if( counts[k]==1 )
{
for( i=0; i<9; i++ ) if( possible[i][j][k] )
{
makemove( i, j, k );
changed = true;
}
}
}

int di, dj;
for( i=0; i<9; i+=3 ) for( j=0; j<9; j+=3 )
{
Arrays.fill( counts, 0 );
for( di=0; di<3; di++ )for( dj=0; dj<3; dj++ )for( k=1; k<10; k++ )
{
if( possible[i+di][j+dj][k] ) ++counts[k];
}

for( k=1; k<10; k++ ) if( counts[k]==1 )
{
for( di=0; di<3; di++ )for( dj=0; dj<3; dj++ )if( possible[i+di][j+dj][k] )
{
makemove( i+di, j+dj, k );
changed = true;
}
}
}
}
}

public void addline( String digits, int i )
{
int j;
for( j=0; j<digits.length(); j++ )
{
int digit = (int)(digits.charAt(j)-'0');
if( digit > 0 )makemove( i, j, digit );
}
}

public void print()
{
int i, j;
for( i=0; i<9; i++ )
{
for( j=0; j<9; j++ )
{
ps.print( b[i][j] );
}
ps.println();
}

/*
for( i=0; i<9; i++ )
{
for( j=0; j<9; j++ )
{
ps.print( "[" );
for( int k=1; k<10; k++ )
{
ps.print( possible[i][j][k] ? (""+k) : " " );
}
ps.print( "] " );
}
ps.println();
}
*/
}

public Board findsolution( int ii, int jj )
{
Board solution = null;
int k;

if( ii==9 )
{
solution = this;
}
else
{
int newi, newj;
if( jj==8 )
{
newi = ii+1;
newj = 0;
}
else
{
newi = ii;
newj = jj+1;
}

if( b[ii][jj] > 0 )
{
solution = findsolution( newi, newj );
}
else
{
for( k=1; k<10 && solution==null; k++ ) if( possible[ii][jj][k] )
{
Board newboard = new Board( this );
newboard.makemove( ii, jj, k );
newboard.settle();
solution = newboard.findsolution( newi, newj );
}
}
}

return solution;
}
};

public void doit() throws Exception
{
ps = new PrintStream( new FileOutputStream( "C.sol" ) );
DecimalFormat df = new DecimalFormat( "0.00" );
String tokens[];
int i, j, k;

int nCases = Integer.parseInt( br.readLine().trim() );

while(nCases-->0)
{
Board b = new Board();
for( i=0; i<9; i++ )
{
}

b.settle();

b.findsolution( 0, 0 ).print();
ps.println();
}

br.close();
ps.close();
}

public static void main( String args[] ) throws Exception
{
(new C()).doit();
}
}
```

This post has been edited by dejandenib: 13 July 2009 - 08:07 AM

Is This A Good Question/Topic? 0

## Replies To: Sudoku solver

### #2 ayman_mastermind

• human.setType("geek");

Reputation: 127
• Posts: 1,860
• Joined: 12-December 08

## Re: Sudoku solver

Posted 13 July 2009 - 03:54 AM

### #3 rishabhsharma

• D.I.C Regular

Reputation: 10
• Posts: 342
• Joined: 26-March 09

## Re: Sudoku solver

Posted 13 July 2009 - 04:19 AM

You can refer http://www.dreaminco...snippet3447.htm

### #4 dejandenib

Reputation: 0
• Posts: 28
• Joined: 10-June 09

## Re: Sudoku solver

Posted 13 July 2009 - 08:10 AM

Anybody?

### #5 dejandenib

Reputation: 0
• Posts: 28
• Joined: 10-June 09

## Re: Sudoku solver

Posted 13 July 2009 - 06:44 PM

Can somebody help me?

### #6 pbl

• There is nothing you can't do with a JTable

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Sudoku solver

Posted 13 July 2009 - 06:55 PM

rishabhsharma, on 13 Jul, 2009 - 03:19 AM, said:

Thanks for quoting my code
But has nothing to do
Writting a Sudoku solver by logic is a challenging problem (and a lot more efficient)
You could pass throught all standard mechanisms and even display them when you solve the problem
You can have a GUI and the user can clik on a button for a "hint"
This is really challenging
At the end when only a few squares are still to fill you can use the brute force as the code shown here.

Because here we solve a Sudoku by the brute force tryng all possibilities... not really a challenge and kind of useless as there is no "pedagogic" approach trying to teach the user on how to do it... and every Sudoku book has the answer at the back so kind of useless

Now if I look at the original post what is your real problem ? You want us to translate de C++ in Java or the Java in C++ ?

### #7 mostyfriedman

• The Algorithmi

Reputation: 728
• Posts: 4,473
• Joined: 24-October 08

## Re: Sudoku solver

Posted 13 July 2009 - 07:20 PM

this could be done in a few lines in Prolog

### #8 malerv

Reputation: 13
• Posts: 100
• Joined: 01-July 09

## Re: Sudoku solver

Posted 13 July 2009 - 08:04 PM

dejandenib don't you just post your homework subject?

### #9 pbl

• There is nothing you can't do with a JTable

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Sudoku solver

Posted 13 July 2009 - 08:14 PM

malerv, on 13 Jul, 2009 - 07:04 PM, said:

dejandenib don't you just post your homework subject?

if it is the case, ask your teacher to find less boaring and useless subjects

### #10 dejandenib

Reputation: 0
• Posts: 28
• Joined: 10-June 09

## Re: Sudoku solver

Posted 16 July 2009 - 11:53 AM

I want this to be translated from java in c++. OK. I'll explain some more. This are two different solutions with different input and output, but with very little changes, the input and output will be the same( but i don't know java and i can't make this changes alone). Maybe this changes can make some more experienced programmer, but to make it more simple, i'm asking you just to rewrite the java into c++

This post has been edited by dejandenib: 16 July 2009 - 12:01 PM

### #11 pbl

• There is nothing you can't do with a JTable

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Sudoku solver

Posted 16 July 2009 - 05:01 PM

dejandenib, on 16 Jul, 2009 - 10:53 AM, said:

I want this to be translated from java in c++. OK. I'll explain some more. This are two different solutions with different input and output, but with very little changes, the input and output will be the same( but i don't know java and i can't make this changes alone). Maybe this changes can make some more experienced programmer, but to make it more simple, i'm asking you just to rewrite the java into c++

You will have more chances to succeed in the C++ forum
I can easily take C++ and translate it into Java but the inverse would take me more time and do not see any challenge into it
Are here to help you with Java not C++. Post in the C++ forum

### #12 malerv

Reputation: 13
• Posts: 100
• Joined: 01-July 09

## Re: Sudoku solver

Posted 16 July 2009 - 06:01 PM

But I think that they will be asking you to think by yourself too.