Your goal is to create a Sudoku solver program that uses the hill-climbing algor
ID: 3917832 • Letter: Y
Question
Your goal is to create a Sudoku solver program that uses the hill-climbing algorithm to produce solutions for any given 9x9 Sudoku puzzle. Implement in Java programming language, as long as you are able to implement the hill-climbing algorithm completely. Your program should accept a matrix as an input (like the examples that I have included below) and return a formatted output that resembles a Sudoku layout. Text output is fine, or you may output to a file (or both). Your program should also display the intermediate steps to solving the puzzle (the program’s “thinking”, in a manner of speaking) in order to receive full credit. Use the following three Sudoku puzzles as testers to evaluate the accuracy of your algorithm. Easy Difficulty: [[8,_,_,9,_,3,_,_,1], [_,_,5,_,8,_,9,_,_], [_,3,_,_,_,_,_,6,_], [4,_,_,1,_,6,_,_,2], [_,6,_,_,_,_,_,4,_], [1,_,_,7,_,2,_,_,5], [_,7,_,_,_,_,_,9,_], [_,_,2,_,5,_,8,_,_], [9,_,_,4,_,1,_,_,3]]
Explanation / Answer
Program in java:
public class SudokuSolver {
public static void main(String[] args) {
Sudoku s = new Sudoku();
s.displaySudoku();
if(s.solveSudoku())
{
s.displaySudoku();
}
else
{
System.out.println("Unsuccessful");
}
}
}
class Sudoku
{
private int[][] sudoku;
private static final int UNASSIGNED = 0;
public Sudoku()
{
sudoku = new int[9][9];
}
public Sudoku(int sudoku[][])
{
this.sudoku= sudoku;
}
public boolean solveSudoku()
{
for(int row=0;row<9;row++)
{
for(int col=0;col<9;col++)
{
if(sudoku[row][col]==UNASSIGNED)
{
for(int number=1;number<=9;number++)
{
if(isAllowed(row, col, number))
{
sudoku[row][col] = number;
if(solveSudoku())
{
return true;
}
else
{
sudoku[row][col] = UNASSIGNED;
}
}
}
return false;
}
}
}
return true;
}
private boolean containsInRow(int row,int number)
{
for(int i=0;i<9;i++)
{
if(sudoku[row][i]==number)
{
return true;
}
}
return false;
}
private boolean containsInCol(int col,int number)
{
for(int i=0;i<9;i++)
{
if(sudoku[i][col]==number)
{
return true;
}
}
return false;
}
private boolean containsInBox(int row, int col,int number)
{
int r = row - row%3;
int c = col - col%3;
for(int i=r;i<r+3;i++)
{
for(int j=c;j<c+3;j++)
{
if(sudoku[i][j]==number)
{
return true;
}
}
}
return false;
}
private boolean isAllowed(int row, int col,int number)
{
return !(containsInRow(row, number) || containsInCol(col, number) || containsInBox(row, col, number));
}
public void displaySudoku()
{
for(int i=0;i<9;i++)
{
if(i%3==0 && i!=0)
{
System.out.println("---------------------------------- ");
}
for(int j=0;j<9;j++)
{
if(j%3==0 && j!=0)
{
System.out.print(" | ");
}
System.out.print(" " + sudoku[i][j] + " ");
}
System.out.println();
}
System.out.println(" __________________________________________ ");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.