Skip to content

Instantly share code, notes, and snippets.

@khult

khult/Attempt to Solve Sudoku Puzzles

Created June 23, 2015 23:49
Show Gist options
  • Save khult/3ecf7a4e29b4c747e26a to your computer and use it in GitHub Desktop.
Save khult/3ecf7a4e29b4c747e26a to your computer and use it in GitHub Desktop.
Download ZIP
Java Examples
Raw
Attempt to Solve Sudoku Puzzles
//Kristofer Hult
//Algorithms Project 4
package sudokuSolver;
import java.util.*;
import java.io.*;
public class sudokuSolver {
private static int[][] board;
private static int[][] domainSize;
private static boolean[][][] domain;
static final int empty = 0;
static final int success = -100;
static final int fail = -1;
static long calls = 0;
static void displaySudoku() {
for (int i = 0; i < 9; i++) {
System.out.println(" -------------------------------------");
for (int j = 0; j < 9; j++) {
if (board[i][j]>0) System.out.print(" | " + board[i][j]);
else System.out.print(" | ");
}
System.out.println(" |");
}
System.out.println(" -------------------------------------");
}
static int next(int pos) {
// pos: the last four bits are column number and the next four bits are row number.
// look for next open position
// fix for some java compilers which handle -1 as bit vector wrong.
if (pos == -1) {
if (board[0][0] == empty) return 0;
else pos = 0;
}
int col = pos&15;
int row = (pos >> 4)&15;
while (true) {
++col;
if (col >= 9) { col = 0; row++; }
if (row >= 9) return success; // no more open positions
if (board[row][col] <= empty) return (row << 4)+col;
}
}
static int updatedNext() {
// returns the position with the least feasible values.
int N = 10;
int bestPos = 0;
int num;
boolean found = true;
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (board[i][j] == 0) {
found = false;
num = numberIsFeasible(i, j);
if (num <= 1) {
N = num;
bestPos = (i << 4)+j;
break;
}
else if (num < N) {
N = num;
bestPos = (i << 4)+j;
}
}
}
}
if (found) return success; // No more open positions
return bestPos;
}
static boolean feasible (int row, int col, int k) {
// check if k is feasible at position <row, col>
for (int i = 0; i < 9; i++) {
if (board[i][col] == k) return false; // used in the same column
if (board[row][i] == k) return false; // used in the same row
}
int row0 = (row/3)*3;
int col0 = (col/3)*3;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
if (board[i+row0][j+col0] == k) return false; // used in the same region
return true;
}
static int numberIsFeasible(int row, int col) {
// This function is made to allow for less calls to feasible().
int count = 0;
for (int k=0; k<9; k++) {
if (domain[row][col][k]) count++;
}
return count;
}
static void removeNumberFromDomain(int row, int col, int k) {
// Removes k from the domain when it is in another row or column
for(int i=0; i<9; i++) {
domain[i][col][k-1] = false;
domain[row][i][k-1] = false;
}
int row0 = (row/3)*3;
int col0 = (col/3)*3;
for (int i=0; i<3; i++) for (int j=0; j<3; j++) {
domain[i+row0][j+col0][k-1] = false;
}
}
static void updateDomain(int row, int col, int k) {
// Updates all the domains for when k is in another row or column
for(int i=0; i<9; i++) {
domain[i][col][k-1] = feasible(i, col, k);
domain[row][i][k-1] = feasible(row, i, k);
}
int row0 = (row/3)*3;
int col0 = (col/3)*3;
for (int i=0; i<3; i++) for (int j=0; j<3; j++) {
domain[i+row0][j+col0][k-1] = feasible(i+row0, j+col0, k);
}
}
static int backtrack (int pos) {
// backtrack procedure
calls++;
if (pos == success) return success;
// pos: the last four bits are column number and the next four bits are row number.
int col = pos&15;
int row = (pos >> 4)&15;
// Tries all of the values in the domain for the position.
for (int k = 1; k <= 9; k++) if (domain[row][col][k-1]) {
// removes k from domain of all incident cells.
board[row][col] = k;
removeNumberFromDomain(row, col, k);
// System.out.println("["+row+","+col+"]="+k);
if (backtrack(updatedNext()) == success) return success;
else {
// Restore Domain if there is no answer
board[row][col] = 0;
updateDomain(row, col, k);
}
}
board[row][col] = empty;
return fail;
}
public static void main(String[] args) {
board = new int[9][9];
domainSize = new int[9][9];
domain = new boolean[9][9][9];
// read in a puzzle
try {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Please enter sudoku puzzle file name: ");
String filename = read.readLine();
Scanner scanner = new Scanner(new File(filename));
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) { // while(scanner.hasNextInt())
board[i][j] = scanner.nextInt();
domainSize[i][j] = (board[i][j]>0)? 1 : 9;
}
System.out.println("Read in:");
displaySudoku();
}
catch(Exception ex){
ex.printStackTrace();
}
// Initialize the domain for each position
for(int i=0; i<9; i++) for (int j=0; j<9; j++) for (int k=0; k<9; k++) {
if (feasible(i, j, k+1)) {
domain[i][j][k] = true;
} else domain[i][j][k] = false;
}
// Solve the puzzle by backtrack search and display the solution if there is one.
if (backtrack(updatedNext()) == success) {
System.out.println("\nSolution:");
displaySudoku();
} else {
System.out.println("no solution");
}
System.out.println("recursive calls = "+calls);
}
}
Raw
Enumerate
// In eclipse, class name and file name must be the same.
// Each class has a separate file.
// Kristofer Hult
public class enumerate {
// all runs start at "main"
public static void main(String[] args) {
enumerateSubsets(5);
enumerateCombinations(2, 5);
enumerate5Permutations();
}
// enumerate all subsets of the set { 1, 2, ..., n }, where n < 32.
public static void enumerateSubsets (int n) { //does not need to be modified. can already sets up to 63
// Pre: n < 64
System.out.println("All subsets of " + n + " numbers:");
for (int x = 0; x < (1 << n); x++) {
System.out.print("{");
for (int j = 1; j <= n; j++)
if ((x & (1 << (j-1))) != 0)
System.out.print(j + ", ");
System.out.print("}\n");
}
}
// print the first n elements of the array x as a set.
public static void printArray(int x[], int n) {
System.out.print("{");
System.out.print(x[0]);
for (int i = 1; i < n; i++)
System.out.print(", " + x[i]);
System.out.print("}\n");
}
// print all k-combinations of n elements.
public static void enumerateCombinations (int k, int n) {
int x[] = new int[100]; // k <= 100
System.out.println("All " + k + "-combinations of " + n + " numbers:");
for (int j = 0; j < k; j++) x[j] = j+1;
while (true) {
printArray(x, k);
if (nextCombination(x, k, n) == false) break;
}
}
// modify the array x to generate the next k-combination from x.
// In general, the first k-combination of n elements is { 1, 2, ..., k }
// and the last k-combination is { n-k+1, n-k+2, ..., n }.
public static boolean nextCombination (int x[], int k, int n) {
if (nextCombinationRecursive(k - 1, x, k, n) == false) return false;
else
return true;
}
public static boolean nextCombinationRecursive (int j, int x[], int k, int n) {
if (j < 0 || j > k) return false;
if (x[j] <= (n - k + j)) {
x[j]++;
for (int i = 1; i < k - j; i++)
x[i+j] = x[j]+i;
return true;
}
return nextCombinationRecursive(j - 1, x, k, n);
}
public static void nextPermutation(int x[], int n){
{
int i, j;
// Find the largest index i such that x[i] < x[i + 1]. If no such index
// exists, the permutation is the last permutation.
for (i = x.length - 2; i >= 0; i--) {
if (x[i] < x[n])
break;
}
if (i < 0) {
System.out.println("End");
return;
}
// Find the largest index l such that a[k] < a[l]. Since k + 1 is such
// an index, l is well defined and satisfies k < l.
for (j = x.length - 1; j > i; j--) {
if (x[j] > x[i])
break;
}
// Swap a[k] with a[l].
swap(x, i++, j);
// Reverse the sequence from a[k + 1] up to and including the final
// element a[n].
for (j = x.length - 1; j > i; i++, j--) {
swap(x, i, j);
}
}
}
public static void swap(int [] array, int t, int y) {
array[t] ^= array[y];
array[y] ^= array[t];
array[t] ^= array[y];
}
// This is an awkward method to print all 5! permutations of 5 elements.
public static void enumerate5Permutations () {
// Pre: n = 5
System.out.println("All permutations of 5 numbers:");
for (int x1 = 1; x1 <= 5; x1++)
for (int x2 = 1; x2 <= 5; x2++) if (x1 != x2)
for (int x3 = 1; x3 <= 5; x3++) if (x3 != x1 && x3 != x2)
for (int x4 = 1; x4 <= 5; x4++) if (x4 != x1 && x4 != x2 && x4 != x3)
for (int x5 = 1; x5 <= 5; x5++)
if (x5 != x1 && x5 != x2 && x5 != x3 && x5 != x4) {
System.out.print("[ ");
System.out.print(x1+", "+x2+", "+x3+", "+x4+", "+x5);
System.out.print("]\n");
}
}
}
Raw
Sorting
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Random;
import java.util.Arrays;
public class sorting {
private static int[] arr;
private static int[] arrCopy;
private static BufferedReader read;
private static Random randomGenerator;
private static int size;
private static int random;
private static int n;
public static void insertSort(int low, int high){
for(int i=1; i < arr.length; i++){
int tempA=arr[i];
int j;
for(j = i-1; j>=0 && tempA > arr[j];j--){
arr[j+1]=arr[j];
}
arr[j+1]=tempA;
}
}
public static boolean isSorted(int low, int high){
for(int i=1; i< arr.length; i++){
if(arr[i-1] >= arr[i] ){
return false;
}
}
return true;
}
private static void printArray() {
System.out.print("[" + arr[0]);
for(int i=1; i<size; i++) {
System.out.print(", " + arr[i]);
}
System.out.println("]");
}
public static void buildheap(){
n=arr.length-1;
for(int i=n/2;i>=0;i--){
heapify(i);
}
}
public static void heapify(int i){
int largest;
int left=2*i;
int right=2*i+1;
if(left <= n && arr[left] > arr[i]){
largest=left;
}
else{
largest=i;
}
if(right <= n && arr[right] > arr[largest]){
largest=right;
}
if(largest!=i){
exchange(i,largest);
heapify(largest);
}
}
public static void exchange(int i, int j){
int t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
public static void heapsort(){
buildheap();
for(int i=n;i>0;i--){
exchange(0, i);
n=n-1;
heapify(0);
}
}
private static void mergesort(int low, int high) {
// Check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
int middle = low + (high - low) / 2;
// Sort the left side of the array
mergesort(low, middle);
// Sort the right side of the array
mergesort(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
private static void mergesortA(int low, int high) {
// Check if low is smaller then high, if not then the array is sorted
if( arr.length < 100){
insertSort(low, high);
}
if (low < high) {
// Get the index of the element which is in the middle
int middle = low + (high - low) / 2;
// Sort the left side of the array
mergesortA(low, middle);
// Sort the right side of the array
mergesortA(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
private static void mergesortB(int low, int high) {
// Check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
boolean test = isSorted(low, high);
int middle = low + (high - low) / 2;
// Sort the left side of the array
if(test=false)
{mergesortB(low, middle);
// Sort the right side of the array
mergesortB(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
}
private static void mergesortC(int low, int high) {
if( arr.length < 100){
insertSort(low, high);
}
// Check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
boolean test = isSorted(low, high);
int middle = low + (high - low) / 2;
// Sort the left side of the array
if(test=false) {
mergesortC(low, middle);
// Sort the right side of the array
mergesortC(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
}
private static void merge(int low, int middle, int high) {
// Copy both parts into the arrCopy array
for (int i = low; i <= high; i++) {
arrCopy[i] = arr[i];
}
int i = low;
int j = middle + 1;
int k = low;
// Copy the smallest values from either the left or the right side back
// to the original array
while (i <= middle && j <= high) {
if (arrCopy[i] <= arrCopy[j]) {
arr[k] = arrCopy[i];
i++;
} else {
arr[k] = arrCopy[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
arr[k] = arrCopy[i];
k++;
i++;
}
}
private static void quicksort(int low, int high) {
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = arr[(high+low)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
// Recursion
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
private static void quicksortA(int low, int high) {
int i = low, j = high;
int middle=low+(high-low)/2;
// Get the pivot element from the middle of the list
int pivot = arr[(((high+low)/2)+middle)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
// Recursion
if (low < j)
quicksortA(low, j);
if (i < high)
quicksortA(i, high);
}
private static void quicksortB(int low, int high) {
int i = low, j = high, i2=i+1, i3=i+2;
int j1=(high-low)/2, j2=(high-low)/3;
int mid1 =(high+low)/2;
int mid2 =(i2+i3)/2;
int mid3 =(j1+j2)/2;
int midPivot= (((mid1+mid2)/2)+mid3)/2;
// Get the pivot element from the middle of the list
int pivot = arr[midPivot];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
// Recursion
if (low < j)
quicksortB(low, j);
if (i < high)
quicksortB(i, high);
}
private static void quicksort1(int low, int high) {
if( arr.length < 100){
insertSort(low, high);
}
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = arr[(high+low)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
// Recursion
if (low < j)
quicksort1(low, j);
if (i < high)
quicksort1(i, high);
}
private static void quicksort2(int low, int high) {
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = arr[(high+low)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
boolean test = isSorted(low, high);
if(test=false) {
// Recursion
if (low < j)
quicksort2(low, j);
if (i < high)
quicksort2(i, high);
}
}
private static void quicksort3(int low, int high) {
int i = low, j = high;
int middle=low+(high-low)/2;
// Get the pivot element from the middle of the list
int pivot = arr[(((high+low)/2)+middle)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
// Recursion
if (low < j)
quicksort3(low, j);
if (i < high)
quicksort3(i, high);
}
private static void quicksort4(int low, int high) {
int i = low, j = high, i2=i+1, i3=i+2;
int j1=(high-low)/2, j2=(high-low)/3;
int mid1 =(high+low)/2;
int mid2 =(i2+i3)/2;
int mid3 =(j1+j2)/2;
int midPivot= (((mid1+mid2)/2)+mid3)/2;
// Get the pivot element from the middle of the list
int pivot = arr[midPivot];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
// Recursion
if (low < j)
quicksort4(low, j);
if (i < high)
quicksort4(i, high);
}
private static void quicksort5(int low, int high) {
int i = low, j = high;
int middle=low+(high-low)/2;
if( arr.length < 100){
insertSort(low, high);
}
// Get the pivot element from the middle of the list
int pivot = arr[(((high+low)/2)+middle)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
boolean test = isSorted(low, high);
if(test=false) {
// Recursion
if (low < j)
quicksort5(low, j);
if (i < high)
quicksort5(i, high);
}
}
private static void quicksort6(int low, int high) {
if( arr.length < 100){
insertSort(low, high);
}
int i = low, j = high, i2=i+1, i3=i+2;
int j1=(high-low)/2, j2=(high-low)/3;
int mid1 =(high+low)/2;
int mid2 =(i2+i3)/2;
int mid3 =(j1+j2)/2;
int midPivot= (((mid1+mid2)/2)+mid3)/2;
// Get the pivot element from the middle of the list
int pivot = arr[midPivot];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (arr[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (arr[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i < j) {
exchange(i, j);
i++;
j--;
} else if (i == j) { i++; j--; }
}
boolean test = isSorted(low, high);
if(test=false) {
// Recursion
if (low < j)
quicksort6(low, j);
if (i < high)
quicksort6(i, high);
}
}
public static void main(String[] args) {
read = new BufferedReader(new InputStreamReader(System.in));
randomGenerator = new Random();
try
{
System.out.print("Please enter array size : ");
size = Integer.parseInt(read.readLine());
System.out.print("Please enter the random range : ");
random = Integer.parseInt(read.readLine());
// create array
arr = new int[size];
arrCopy = new int[size];
// fill array
for(int i=0; i<size; i++) {
arr[i] = arrCopy[i] = randomGenerator.nextInt(random);
}
if (size < 101) {
System.out.println("Initial array:");
printArray();
}
long start = System.currentTimeMillis();
Arrays.sort(arr);
if (size < 101) printArray();
long finish = System.currentTimeMillis();
System.out.println("Arrays.sort: " + (finish-start) + " milliseconds.");
// Heap sort
start = finish;
heapsort();
if (size < 101) printArray();
finish = System.currentTimeMillis();
System.out.println("heapsort: " + (finish-start) + " milliseconds.");
// Quick sort
start = finish;
for(int i=0; i<size; i++) arr[i] = arrCopy[i];
quicksort(0, size-1);
if (size < 101) printArray();
finish = System.currentTimeMillis();
System.out.println("quicksort: " + (finish-start) + " milliseconds.");
// Merge sort, which destroys arrCopy[].
start = finish;
for(int i=0; i<size; i++) arr[i] = arrCopy[i];
mergesort(0, size-1);
if (size < 101) printArray();
finish = System.currentTimeMillis();
System.out.println("mergesort: " + (finish-start) + " milliseconds.");
}
catch(Exception ex){
ex.printStackTrace();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment