The result should be in recursive order. Look up the Wikipedia article on Sudoku
ID: 3704796 • Letter: T
Question
The result should be in recursive order.
Look up the Wikipedia article on Sudoku puzzles at: https./en.wikipedia.org/wiki/Sudoku We will use the standard 9 × 9 board with hints read from standard input. Your program should output the first solution discovered using a recursive algorithm that employs backtracking. Note that depending on the number and value of the hints, there may be more than one solution or no solutions possible. Generally, Sudoku puzzles have hints that result in only one solution. For this reason, your program should read 81 values from standard input containing the hints (numbers in the input sequence between 1 and 9, inclusive) and empties (zeros in the input sequence). The input should fill the rows left-to- ght then top-to-bottom. The values input should be taken from one of the many, easily available, Sudoku Puzzles (like the Wikipedia article) to be sure you will find a unique solution. otice that you can place the hints as a sequence in a white space delimited plain text file and read it as standard input to your program by using the following command line when launching your Java program java SudokuExplanation / Answer
==============================================================================
import java.util.Scanner;
import java.io.*;
public class Sudoku {
// Recursive method for solving sudoku.
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; // Sudoku solved.
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); // recursive
if (solved) return true;
else puzzle[myRow * 9 + myCol] = 0; // Backtrack
}
}
return false;
}
public static void main(String[] args) throws IOException {
// Checking Number of arguments passed at command line.
if(args.length != 2)
{
System.out.println("Wrong number of arguments:");
System.out.println("The syntax is : java Sudoku < hintsfile.txt");
System.exit(0);
}
String filename = args[1]; //First argument is '<' and Second argument is filename.
System.out.println("File Name: " + filename);
// Read sudoku hints file to Array
FileReader fileReader = new FileReader(filename);
Scanner sc = new Scanner(fileReader);
int[] puzzle = new int[81];
for (int i = 0; i < 81; i++) {
puzzle[i] = sc.nextInt();
}
sc.close(); //close input reader
if (solve(puzzle)) { //If solution is found
System.out.println("Sudoku Puzzle Solved: Solution is: ");
System.out.println("------------------------");
for (int i = 0; i < 81; i++) {
System.out.print(" " + puzzle[i]);
if ((i + 1) % 3 == 0) System.out.print(" |");
if (i != 0 && (i + 1) % 9 == 0) System.out.println();
if ((i + 1) % 27 == 0) System.out.println("------------------------");
}
} else { //Solution was not found.
System.out.println("Could not solve this puzzle");
}
}
}
=====================================================================
input file:
4 0 0 0 0 0 0 0 5
0 0 9 4 0 2 8 0 0
0 6 0 0 5 0 0 9 0
0 3 0 0 8 0 0 2 0
0 0 2 5 0 1 3 0 0
0 9 0 0 4 0 0 7 0
0 1 0 0 6 0 0 5 0
0 0 8 1 0 5 9 0 0
5 0 0 0 0 0 0 0 7
===============================================
Output:
File Name: hints.txt
Sudoku Puzzle Solved: Solution is:
------------------------
4 8 7 | 6 1 9 | 2 3 5 |
3 5 9 | 4 7 2 | 8 1 6 |
2 6 1 | 3 5 8 | 7 9 4 |
------------------------
1 3 4 | 7 8 6 | 5 2 9 |
6 7 2 | 5 9 1 | 3 4 8 |
8 9 5 | 2 4 3 | 6 7 1 |
------------------------
9 1 3 | 8 6 7 | 4 5 2 |
7 4 8 | 1 2 5 | 9 6 3 |
5 2 6 | 9 3 4 | 1 8 7 |
------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.