First Project:

import java.util.*;

public class Sudoku1 {

/**

* Reads Sudoku Puzzle in the following format.

* Input will consist of 9 lines each containing nine digits, corresponding to the 81 squares in

* a Sudoku grid.

* If a value is a 0 it indicates a blank square; otherwise it indicates the number

* stored in the square.

*

* 4 0 0 0 0 0 0 0 0

* 0 0 0 0 0 1 0 0 8

* 1 2 0 0 3 0 0 7 9

* 0 0 0 8 0 0 4 0 0

* 0 9 0 0 0 0 0 0 0

* 0 0 0 6 0 0 5 0 7

* 0 8 0 0 0 0 0 6 0

* 0 0 5 0 0 4 0 3 0

* 0 0 3 0 1 0 0 0 0

*

* Output should be the solved puzzle, or some indication that it has "Could not solve this puzzle".

*/

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

int[] puzzle = new int[81];

for (int i = 0; i < 81; i++) {

puzzle[i] = input.nextInt();

}

if (solve(puzzle)) {

System.out.println("Puzzle Solved, here is the solution:");

for (int i = 0; i < 81; i++) {

System.out.print(puzzle[i] + "|");

if((i + 1) % 9 == 0)

System.out.println(" -+-+-+-+-+-+-+-+-+");

}

} else {

System.out.println("Could not solve this puzzle");

}

System.out.println();

}

public static boolean solve(int[] puzzle) {

boolean noEmptyCells = true;

int myRow = 0, myCol = 0;

for (int i = 0; i < 81; i++) {

if (puzzle[i] == 0) {

myRow = i / 9;

myCol = i % 9;

noEmptyCells = false;

break;

}

}

if (noEmptyCells) return true;

for (int choice = 1; choice <= 9; choice++) {

boolean isValid = true;

int gridRow = myRow / 3;

int gridCol = myCol / 3;

// check grid for duplicates

for (int row = 3 * gridRow; row < 3 * gridRow + 3; row++)

for (int col = 3 * gridCol; col < 3 * gridCol + 3; col++)

if (puzzle[row * 9 + col] == choice)

isValid = false;

// row & column

for (int j = 0; j < 9; j++)

if (puzzle[9 * j + myCol] == choice || puzzle[myRow * 9 + j] == choice) {

isValid = false;

break;

}

if (isValid) {

puzzle[myRow * 9 + myCol] = choice;

boolean solved = solve(puzzle);

if (solved) return true;

else puzzle[myRow * 9 + myCol] = 0;

}

}

return false;

}

}

Second Project: Input : Input will consist of a single integer r which specifies how many digits should be in the puzzle when it is finished. The maximum value for r is obviously 81 (i.e., a fully filled grid), and we'll use 25 as the lowest allowed value { any lower value entered should be set to 25 (you can actually go lower than 25, but it sometimes takes a while to generate a puzzle for r less than 25). Algorithm : You should use a branch-and-bound algorithm to solve this problem, in two different capacities. First, you should write a branch-and-bound method which when given a sudoku grid returns a boolean value indicating whether or not there is a unique solution. If you solved the previous project, then this should be a small modi cation to that project's algorithm. Once you have the checker working, you then must write another branch-and-bound method which, along with a random number generator, completely fills in a grid. Once you have a grid, you can start removing values from it and then check to see if you still have a puzzle with a unique solution. If you remove a value and find that there are more than two solutions, then you must put it back and try removing another one. Output : Your program should output two items. The puzzle , and the solution to your puzzle to the le XXX.ans