I need to write a Sudoku solver in java the program should t

I need to write a Sudoku solver in java.

the program should take an input file text file like this:

XX81XX5XX96XX8XXXXX5XX36X98XX7X69X12XX68X73XX81X45X6XX42X67XX8XXXXX4XX63XX5XX87XX

the \"X\" denote the empty cell, which we need to fil out.

How do i wirte the sudoku solver? please show rough code since Im not the greatest in JAVA ;)

Solution

Pre-condition:

# Read input grid (this is in matrix form)
# Grid has 9x9 cells. Cell is represented by (x,y)
# Each cell contains a value from 1 to 9.
# Empty cells are contain the value \'0\'

Algorithm:

1# solve(cell)
2# If cell not empty, call solve(nextCell)
3# If cell is empty (grid[cell.x][cell.y] == 0)
4# Add value v (v belongs to 1-9)
5# Check if v is valid for cell
6# if not valid, continue to #4
7# If valid, call solve(nextCell)
8# If sudoku solved, return true
9# Else return false

Explanation:

Working rough code:

package com.example;

public class Sudoku {

// dimension of input
static int N = 9;

// sample input
static int grid[][] = { { 0, 0, 8, 1, 0, 0, 5, 0, 0 }, //
{ 9, 6, 0, 0, 8, 0, 0, 0, 0 }, //
{ 0, 5, 0, 0, 3, 6, 0, 9, 8 }, //
{ 0, 0, 7, 0, 6, 9, 0, 1, 2 }, //
{ 0, 0, 6, 8, 0, 7, 3, 0, 0 }, //
{ 8, 1, 0, 4, 5, 0, 6, 0, 0 }, //
{ 4, 2, 0, 6, 7, 0, 0, 8, 0 }, //
{ 0, 0, 0, 0, 4, 0, 0, 6, 3 }, //
{ 0, 0, 5, 0, 0, 8, 7, 0, 0 } };

/**
* Class to abstract the representation of a cell. Cell => (x, y)
*/
static class Cell {

int row, col;

public Cell(int row, int col) {
super();
this.row = row;
this.col = col;
}

@Override
public String toString() {
return \"Cell [row=\" + row + \", col=\" + col + \"]\";
}
};

/**
* Utility function to check whether @param value is valid for @param cell
*/

static boolean isValid(Cell cell, int value) {

if (grid[cell.row][cell.col] != 0) {
throw new RuntimeException(
\"Cannot call for cell which already has a value\");
}

// if v present row, return false
for (int c = 0; c < 9; c++) {
if (grid[cell.row][c] == value)
return false;
}

// if v present in col, return false
for (int r = 0; r < 9; r++) {
if (grid[r][cell.col] == value)
return false;
}

// if v present in grid, return false

// to get the grid we should calculate (x1,y1) (x2,y2)
int x1 = 3 * (cell.row / 3);
int y1 = 3 * (cell.col / 3);
int x2 = x1 + 2;
int y2 = y1 + 2;

for (int x = x1; x <= x2; x++)
for (int y = y1; y <= y2; y++)
if (grid[x][y] == value)
return false;

// if value not present in row, col and bounding box, return true
return true;
}

// simple function to get the next cell
// read for yourself, very simple and straight forward
static Cell getNextCell(Cell cur) {

int row = cur.row;
int col = cur.col;

// next cell => col++
col++;

// if col > 8, then col = 0, row++
// reached end of row, got to next row
if (col > 8) {
// goto next line
col = 0;
row++;
}

// reached end of matrix, return null
if (row > 8)
return null; // reached end

Cell next = new Cell(row, col);
return next;
}

// everything is put together here
// very simple solution
// must return true, if the soduku is solved, return false otherwise
static boolean solve(Cell cur) {

// if the cell is null, we have reached the end
if (cur == null)
return true;

// if grid[cur] already has a value, there is nothing to solve here,
// continue on to next cell
if (grid[cur.row][cur.col] != 0) {
// return whatever is being returned by solve(next)
// i.e the state of soduku\'s solution is not being determined by
// this cell, but by other cells
return solve(getNextCell(cur));
}

// this is where each possible value is being assigned to the cell, and
// checked if a solutions could be arrived at.
  
// if grid[cur] doesn\'t have a value
// try each possible value
for (int i = 1; i <= 9; i++) {
// check if valid, if valid, then update
boolean valid = isValid(cur, i);

if (!valid) // i not valid for this cell, try other values
continue;

// assign here
grid[cur.row][cur.col] = i;

// continue with next cell
boolean solved = solve(getNextCell(cur));
// if solved, return, else try other values
if (solved)
return true;
else
grid[cur.row][cur.col] = 0; // reset
// continue with other possible values
}

// if you reach here, then no value from 1 - 9 for this cell can solve
// return false
return false;
}

public static void main(String[] args) {
boolean solved = solve(new Cell(0, 0));
if (!solved) {
System.out.println(\"SUDOKU cannot be solved.\");
return;
}
System.out.println(\"SOLUTION\ \");
printGrid(grid);
}

// utility to print the grid
static void printGrid(int grid[][]) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++)
System.out.print(grid[row][col]);
System.out.println();
}
}
}

Hope, it helped you.The rough code is just to help you and it\'s for a test purpose.If you need more optimized version of code or any further help in this question.Please contact us again,we will love to help you.