Hi.
This is a sudoku solver that reads in 81 integers from a file, with zeroes standing in for blanks. When I run the program, it goes into an infinite loop, or at least what I'm convinced is one..I haven't outruled that it may just be taking an extremely long time to do this task, but because the program continues to run for 10+ minutes, I think that something is happening that would prevent this code from terminating:
import java.util.ArrayList;
import java.util.Scanner;
import java.io.*;
public class Solver
{
public static void main(String[] args)
{
//read in from a file
try
{
FileInputStream fstream = new FileInputStream("C:\\PYTHON5000\\puzzle3.txt");
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String str;
for(int q = 0; q < 81; q++)
{
str = br.readLine();
arr[q] = Integer.valueOf(str).intValue();
}
in.close();
}
catch (Exception e){System.err.println("Error: " + e.getMessage());}
//tempLog contains indices of grid members which have been modified
//and distinguishes guesses not part of the original puzzle from the numbers given in the puzzle
ArrayList tempLog = new ArrayList();
tempLog.add(-1); //initial useless value added so it doesn't complain when I remove the last element
for(int i = 0; i < 81; i++)
{
//skip over members of the grid that are part of the original puzzle (Not blank && Not entered as a guess)
if(arr[i] != 0 && !tempLog.contains(i))
{
continue;
}
//if we guessed this value and encounter it again, we increment the guessed value by one (note initial condition of for loop)
else if(tempLog.contains(i))
{
for(int k = arr; k <= 9; k++)
{
//increase it's value until it meets the constraints; break at that point, we're done
arr[i] = k;
if(checkConstraints(i))
break;
//if numbers one through nine can't meet the constraints, an error was made earlier in the puzzle, reset to blank and go back one
else if(!checkConstraints(i) && k == 9)
{
tempLog.remove(i);
arr[i] = 0;
i--;
}
}
}
//blank encountered, start guess and check procedure
else if(arr[i] == 0)
{
//log as a guess in tempLog
tempLog.add(i);
for(int k = 1; k <= 9; k++)
{
//enter numbers until constaints are met, break at that point
arr[i] = k;
if(checkConstraints(i))
break;
//nothing fits, mistake occurred, earlier, reset to blank and go backwards
else if(!checkConstraints(i) && k == 9)
{
tempLog.remove(i);
arr[i] = 0;
i--;
}
}
}
}
//print out the answer
for(int i = 1; i <= 9; i++) {
System.out.println( );
for(int k = 1; k <= 9; k++) {
System.out.print(arr[k*i]);
}
}
}
//use math properties to find all the indices of a row given the index of a single row member
public static int[] loadRow(int now)
{
int k = 0;
int[] nowIndices = new int[9];
int currentRow = (((now-1) - ((now-1) % 9)) / 9) + 1;
for(int i = 9*currentRow; i > ((9*currentRow) - 9); i--)
{
nowIndices[k] = i;
k++;
}
return nowIndices;
}
//find all indices of a certain column given the index of a single column member
public static int[] loadCol(int now)
{
int currentCol;
int[] nowIndices = new int[9];
if(now % 9 == 0)
currentCol = 9;
else
currentCol = now % 9;
int originalValue = nowIndices[0] = currentCol;
for(int i = 1; i < 9; i++)
{
currentCol = originalValue;
int multiplier = 9 * i;
currentCol += multiplier;
nowIndices[i] = currentCol;
}
return nowIndices;
}
//given an index, find the 3x3 box it is contained in, and return all of their indices
public static int[] loadBox(int now)
{
int[][] boxs = {
{1,2,3,10,11,12,19,20,21},
{4,5,6,13,14,15,22,23,24},
{7,8,9,16,17,18,25,26,27},
{28,29,30,37,38,39,46,47,48},
{31,32,33,40,41,42,49,50,51},
{34,35,36,43,44,45,52,53,54},
{55,56,57,64,65,66,73,74,75},
{58,59,60,67,68,69,76,77,78},
{61,62,63,70,71,72,79,80,81}};
for(int i = 0; i < 9; i++) {
for(int k = 0; k < 9; k++) {
if(boxs[i][k] == now)
return boxs[i];
}
}
//THIS POINT SHALL NEVER BE REACHED, extra return keeps compiler quiet
int[] ERROR = {-99, -99};
return ERROR;
}
//check a row, col, or box for doubles. Zeroes are acceptable. param regionIndices is the indices of a region, loaded by any of the 3 "load" methods above
public static boolean checkRegion(int[] regionIndices)
{
int[] regionMembers = new int[9];
for(int i = 0; i < 9; i++)
{
//THE PROBLEM MAY BE HERE, but I don't know..off by one error?
regionMembers[i] = arr[regionIndices[i] - 1];
}
//check for doubles, zeroes are acceptable
for(int j = 0; j < 9; j++) {
for(int k = 0; k < 9; k++) {
if(regionMembers[j] == regionMembers[k] && regionMembers[j] != 0)
return false;
}
}
return true;
}
//load current conditions and check all constraints
public static boolean checkConstraints(int now)
{
int[] nowRow = loadRow(now);
int[] nowCol = loadCol(now);
int[] nowBox = loadBox(now);
return ( checkRegion(nowRow) && checkRegion(nowCol) && checkRegion(nowBox) );
}
private static int[] arr = new int[81];
}