[dejandenib]

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
this reads from standard input
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;
	 }
}
	 
	 
	 
	 
	 
	 
	 
	  
bool nadole()
{
  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;
			if (nadole())
			  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;	 
  nadole();
	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 
{
	BufferedReader br;
	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
	{
		br = new BufferedReader( new FileReader( "C.in" ) );
		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.addline( br.readLine().trim(), 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

[ayman_mastermind]

Please post your code within code tags Thanks.

[rishabhsharma]

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

[dejandenib]

Anybody?

[dejandenib]

Can somebody help me?

[pbl]

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

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

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++ ?

[mostyfriedman]

this could be done in a few lines in Prolog

[malerv]

dejandenib don't you just post your homework subject?

[pbl]

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

[dejandenib]

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

[pbl]

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

[malerv]

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