0

Am searching for an efficient algorithm for generating solved Sudoku given the size(rows and column) of the board as input.

i have written a program but its performing badly when the number of rows and column exceeds 40 (ie 40 x 40 matrix ).

import java.util.Scanner;

public class Main {
	
	public static int [][]board;
	public static int n=0;
	public static int m=0;

	public static boolean isValid(int row,int matrix,int value){
// Checks vertically
		for(int i=0;i<n;i++){
			if(board[i][0]==value)
				return false;
			else if(board[i][0]==0){
				i=n;
			}
		}		
//No need to check horizontally 

//checks  the m x m blocks
		for(int i=matrix;i<matrix+m;i++){
			for(int j=0;j<m;j++)
				if(board[i][j]==value)
					return false;
				else if(board[i][j]==0){
					j=m;
					i=n;
				}									
		}		
		return true;
	}
	
	private static void fillData(int row, int j) {		
		for(int i=0;i<n;i++){			
			board[row][i]=j%(n+1)+(j/(n+1));
			j++;
		}		
	}
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);		
		int matrix=0;
		int count=0;
		m=sc.nextInt();		
		n=(int) Math.pow(m, 2);
		board=new int[n][n];				
		for(int i=0;i<n;i++){
			count++;
/* For a 9x9 board , matrix values will be 0,3,6  which are the row index of the 3x3 boxes */
			if(count==(m+1)){
				count=1;
				matrix+=m;
			}

			for(int j=1;j<=n;j++){
				if(isValid(i,matrix,j)){
					fillData(i,j);
					j=n+1;
				}
			}								
		}
		for (int k = 0; k < n; k++) {
			for(int j=0;j<n;j++)
				System.out.print(board[k][j]+" ");
			System.out.println();
		}		
	}	
}

Let me know if there are any optimizations that i can make or any algorithm that performs well

2
Contributors
1
Reply
2
Views
8 Years
Discussion Span
Last Post by BestJewSinceJC
0

Well, just for the hell of it, I'm going to write a Sudoku program also. It might take me a few days since I have other things to do this week and I don't know how to play the game yet. Lol. Could you post your input that's taking a long time to run? Also, I'm not sure I understand how you're getting input to begin with. Unless you redirected stdin to a file, it looks like its from the keyboard.


edit: Also, you realize you can probably find hundreds of Suduko programs written in Java online, right?

second edit: After some initial reading, this looks like it is going to be harder than I thought... you're definitely better off getting help by searching the web for some better algorithms than waiting on me. And I don't understand how your code works either... does it work correctly (on smaller puzzles)?

edit (yet again :) ):
Are you using a brute force algorithm to solve this? Such as http://decibel.ni.com/content/docs/DOC-2391

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.