nubela

package utils;

import java.util.*;

/**
 * This class would auto generate a 9x9 sudoku puzzler
 */
public class PuzzleGenerator {

	int[][] grid_array = new int[9][9];
	int[][] fixed_slots = new int[9][9];

	public static void main(String[] args) {

	}

	public void generatePuzzle() {

		/*
		 * To generate a puzzle, we need to create a puzzle with numbers placed
		 * such that there is only a single solution.
		 *
		 * 1) Randomly generate a slot, find the possible numbers to be placed
		 * on it.
		 *
		 * 2) Randomly choose a number and place on it, find the number of
		 * possible solutions, if == 1 , we got a puzzle.
		 *
		 * 3) Repeat 1->2 till we find the puzzle.
		 */
		int num_of_sltns;
		do {
			num_of_sltns = numOfSolutions();
			if (num_of_sltns == 0) {
				fixed_slots = new int[9][9];
			} else if (num_of_sltns == 2) {
				int[] random_slot = generateRandomSlot();
				LinkedList<Integer> values_for_slot = possibleValuesInGrid(random_slot);
				int random_value = randomValueFromLinkedList(values_for_slot);
				fixed_slots[random_slot[0]][random_slot[1]] = random_value;
			}
		} while (num_of_sltns != 1);
	}

	private int randomValueFromLinkedList(LinkedList<Integer> llist) {
		Random rand = new Random();
		int random_ptr = rand.nextInt(llist.size());
		return (int) llist.get(random_ptr);
	}

	public int[] generateRandomSlot() {
		// generate a slot that isn't used.
		int[] ret = new int[2];
		Random rand = new Random();
		int x, y;
		do {
			x = rand.nextInt(9);
			y = rand.nextInt(9);
		} while (fixed_slots[x][y] == 0);
		ret[0] = x;
		ret[1] = y;
		return ret;
	}

	public LinkedList<Integer> possibleValuesInGrid(int[] grid_posi) {
		return this.possibleValuesInGrid(grid_posi, fixed_slots);
	}

	public LinkedList<Integer> possibleValuesInGrid(int[] grid_posi,
			int[][] fixed_slots) {

		/*
		 * we have 3 basic constraints.
		 *
		 * 1. unique in the 3x3 grid 2. unique in the row 3. unique in the
		 * column
		 */

		LinkedList<Integer> avail = new LinkedList<Integer>();
		avail.add(1);
		avail.add(2);
		avail.add(3);
		avail.add(4);
		avail.add(5);
		avail.add(6);
		avail.add(7);
		avail.add(8);
		avail.add(9);

		// minigrid

		int x_offset = miniGridXOffset(getMiniGrid(grid_posi));
		int y_offset = miniGridYOffset(getMiniGrid(grid_posi));

		int i = 0;
		int j = 0;
		while (i <= 2) {
			while (j <= 2) {
				if ((fixed_slots[x_offset + i][y_offset + j] != 0)
						&& (avail
								.contains((Integer) fixed_slots[x_offset + i][y_offset
										+ j])))
					avail.remove((Integer) fixed_slots[x_offset + i][y_offset
							+ j]);
				j++;
			}
			i++;
		}

		// row; y remains the same.

		i = 0;
		while (i < 9) {
			if ((fixed_slots[i][grid_posi[1]] != 0)
					&& (avail.contains((Integer) fixed_slots[i][grid_posi[1]])))
				avail.remove((Integer) fixed_slots[i][grid_posi[1]]);
			i++;
		}

		// column; x remains the same

		i = 0;
		while (i < 9) {
			if ((fixed_slots[grid_posi[0]][i] != 0)
					&& (avail.contains((Integer) fixed_slots[grid_posi[0]][i]))) {
				avail.remove((Integer) fixed_slots[grid_posi[0]][i]);
			}
			i++;
		}

		return avail;

	}

	public int miniGridXOffset(int x) {
		if ((x == 1) || (x == 4) || (x == 7)) {
			return 0;
		} else if ((x == 2) || (x == 5) || (x == 8)) {
			return 3;
		} else if ((x == 3) || (x == 6) || (x == 9)) {
			return 6;
		}
		return -1;
	}

	public int miniGridYOffset(int x) {
		if ((x == 1) || (x == 2) || (x == 3)) {
			return 0;
		} else if ((x == 4) || (x == 5) || (x == 6)) {
			return 3;
		} else if ((x == 7) || (x == 8) || (x == 9)) {
			return 6;
		}
		return -1;
	}

	public int getMiniGrid(int[] grid_posi) {

		/*
		 * Each grid contains 3x3 smaller mini grids.
		 *
		 * We get the grid_posi, and return the corresponding minigrids.
		 */

		// [1][2][3]
		// [4][5][6]
		// [7][8][9]
		if (grid_posi[0] <= 2) {
			// 1, 4, 7
			if (grid_posi[1] <= 2) {
				return 1;
			} else if (grid_posi[1] <= 5) {
				return 4;
			} else if (grid_posi[1] <= 8) {
				return 7;
			}
		} else if (grid_posi[0] <= 5) {
			// 2, 5, 8
			if (grid_posi[1] <= 2) {
				return 2;
			} else if (grid_posi[1] <= 5) {
				return 5;
			} else if (grid_posi[1] <= 8) {
				return 8;
			}
		} else if (grid_posi[0] <= 8) {
			// 3, 6, 9
			if (grid_posi[1] <= 2) {
				return 3;
			} else if (grid_posi[1] <= 5) {
				return 6;
			} else if (grid_posi[1] <= 8) {
				return 9;
			}
		}
		return 0;
	}

	public int numOfSolutions() {
		// we only return 3 cases.
		// 0 for 0 sltns.
		// 1 for exactly 1 unique sltn.
		// 2 for more than 1.
		return 1;
	}

	private boolean inFixedSlots(int[] slot) {
		if (fixed_slots[slot[0]][slot[1]] != 0)
			return true;
		return false;
	}

}