5 Replies - 2704 Views - Last Post: 19 September 2010 - 06:12 PM Rate Topic: -----

#1 C++ Programmer  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 20
  • View blog
  • Posts: 548
  • Joined: 12-June 08

Sudoku Solver Problem

Posted 19 September 2010 - 04:20 PM

My friend and I were trying to make a Sudoku Solver in Java using the brute force algorithm and we can't seem to get it to finish the algorithm it keeps getting stuck in an infinite loop at the do while loop.

Here is the code

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Sudoku {
	
	static BufferedReader input;
	static int[][] board = new int[9][9];
	static boolean[][] given = new boolean[9][9];
	
	public static void main(String[] args) throws IOException {
		if(args.length != 1) {
			System.err.println("Usage: java Sudoku <file>");
		} else {
			input = new BufferedReader(new FileReader(args[0]));
			Solve();
		}
	}
	
	public static void Solve() throws IOException {
		for(int r = 0;r<9;r++) {
			for(int c = 0;c<9;c++) {
				board[r][c] = Integer.parseInt(Character.toString((char)input.read()));
				if(board[r][c] != 0) {
					given[r][c] = true;
				} else {
					given[r][c] = false;
				}
			}
		}
		input.close();
		PrintBoard(board);
		for(int x = 0;x<9;x++) {
			for(int y = 0;y<9;y++) {
				if(board[x][y] == 0) {
					do {
						if(CheckMove(board,x,y)) {
							break;
						}
						System.out.println(board[x][y]);
						if(y != 0 && board[x][y] == 9 && board[x][y] != 0 && !given[x][y-1]) {
							y -=2;
							break;
						}
						board[x][y] = board[x][y+1];
					} while(!CheckMove(board,x,y));
				}
			
			}
			
		}
		PrintBoard(board);
		
	}
	
	public static void PrintBoard(int[][] board) {
		for (int r = 0; r < 9; r++) {
			for (int c = 0; c < 9; c++) {
				System.out.print(board[r][c] + " ");
			}
			System.out.println();
		}
	}
	
	public static boolean CheckMove(int[][] board, int r, int c) {
		for(int x = 0;x<3;x++) {
			if(r%3 == 0) {
				for(int y = 0;y < 3;y++) {
					if(board[r-y][x+c] == (board[r][c])) {
						return false;
					}
				}
			} else if((r-1)%3 == 0) {
				for(int y = 0;y < 3;y++) {
					if(board[r+y][x+c] == (board[r][c])) {
						return false;
					}
				}
			} else {
				if(board[r][c] == (board[r][c])) {
					return false;
				}
				
			}
		}
		
		for(int y = 0;y < 9;y++) {
			if(board[y][c] == (board[r][c]) && y != r) {
				return false;
			}
		}
		
		for(int x = 0;x < 9;x++) {
			if(board[r][x] == (board[r][c]) && x != c) {
				return false;
			}
		}
		return true;
	}
	
	
}



EDIT: Sorry wrong forum :(

This post has been edited by C++ Programmer: 19 September 2010 - 04:23 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Sudoku Solver Problem

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,103
  • Joined: 27-December 08

Re: Sudoku Solver Problem

Posted 19 September 2010 - 04:53 PM

Moved to Java Help. Please reserve the Programmers subforums for topical, non-help related discussion.
Was This Post Helpful? 0
  • +
  • -

#3 C++ Programmer  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 20
  • View blog
  • Posts: 548
  • Joined: 12-June 08

Re: Sudoku Solver Problem

Posted 19 September 2010 - 05:02 PM

Thank you. I realized I was in the wrong forum just as I hit post topic.
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

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

Reputation: 8343
  • View blog
  • Posts: 31,890
  • Joined: 06-March 08

Re: Sudoku Solver Problem

Posted 19 September 2010 - 05:50 PM

and what is the question ?
Was This Post Helpful? 0
  • +
  • -

#5 C++ Programmer  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 20
  • View blog
  • Posts: 548
  • Joined: 12-June 08

Re: Sudoku Solver Problem

Posted 19 September 2010 - 05:56 PM

Well, what we really need is a way to check the rows, columns and boxes for repeats of the number in the cell we are checking. Can you give me some psuedocode for this? I am not asking for the code to do this, I am just asking for directions on how I would accomplish this.
Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

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

Reputation: 8343
  • View blog
  • Posts: 31,890
  • Joined: 06-March 08

Re: Sudoku Solver Problem

Posted 19 September 2010 - 06:12 PM

View PostC++ Programmer, on 19 September 2010 - 06:56 PM, said:

Well, what we really need is a way to check the rows, columns and boxes for repeats of the number in the cell we are checking. Can you give me some psuedocode for this? I am not asking for the code to do this, I am just asking for directions on how I would accomplish this.

first row, column and region should be abstracted
it is useless, or a waste of time, to check for region, column, row

you need to simply check for sudoku 9 group entity
so a Sudoku problem should be serialized into 27 group entities which are 9 columns, 9 rows, 9 regions. No need to make for loops to check by row, column, region you are erratic doing that and wasting your time. You need 27 Sudoku group wich are
Grid[0][0], Grid[0][1], Grid[0][2],... Grid[0][8]
...
Grid[0][0], Grid[1][0], Grid[2][0],... Grid[8][0]
...
and the region
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1