Solution for Sudoku programs
I am trying to solve a Sudoku puzzle using Java. Currently this class cannot solve Sudoku correctly.
This class tries to find 0s (spaces) in a 9x9 matrix and marks the position of 0 in the list for later reference. After which it will use those positions to solve this 0. Unfortunately it doesn't seem to work as I hope.
Here is my 9x9 matrix that I used:
0 6 0 1 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0
There are 51 0s in this 9x9 matrix, however when she solves the puzzle she adds 66 positions for some strange reason. I can't seem to pinpoint the problem. Any help would be greatly appreciated!
This is the attempt she spits out:
9 6 3 1 8 4 7 5 0
4 7 8 3 9 5 6 2 0
2 5 0 7 6 0 8 9 1
8 9 5 4 3 7 2 1 6
1 2 6 8 5 0 3 0 9
7 3 0 9 2 1 5 8 4
5 8 9 0 7 3 4 6 2
3 1 7 2 4 6 9 0 8
6 4 2 5 1 8 0 7 3
code:
package com.dc.soduku;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Sudoku {
int[][] grid = new int[9][9];
int emptyCell = 0;
List<String> EmptyCells = new ArrayList<String>();
public Sudoku() {
for (int i = 0; i < 9; i++) {
for (int x = 0; x < 9; x++) {
Scanner scanner = new Scanner(System.in);
System.out.println("Row " + i + " Column " + x + " (Enter values from 1-9): ");
int temp = scanner.nextInt();
grid[i][x] = temp;
}
}
}
public Sudoku(int[][] gridInput) {
grid = gridInput;
}
public void emptyCellsChecker() {
int count = 0;
EmptyCells.clear();
for (int i = 0; i < 9; i++) {
for (int x = 0; x < 9; x++) {
if (grid[i][x] == 0) {
System.out.println("Blank at row " + i + " column " + x + ".");
count++;
EmptyCells.add(i + "," + x);
}
}
}
System.out.println("Total number of empty cells: " + count);
// System.out.print(mm.toString());
System.out.println((EmptyCells.get(1)).substring(0, 1));
System.out.println((EmptyCells.get(1)).substring(2, 3));
}
public void printSudoku() {
for (int i = 0; i < 9; i++) {
for (int x = 0; x < 9; x++) {
System.out.print(grid[i][x] + " ");
}
System.out.println("");
}
}
public void appendCell(int row, int col, int replacement) {
this.grid[row][col] = replacement;
}
public int getCell(int row, int col) {
return grid[row][col];
}
public boolean isEmpty() {
for (int i = 0; i < 9; i++) {
for (int x = 0; x < 9; x++) {
if (grid[i][x] == emptyCell) {
return true;
}
}
}
return false;
}
public boolean checkRow(int row, int guess) {
for (int i = 0; i < 9; i++) {
if (grid[row][i] == guess) {
return false;
}
}
return true;
}
public boolean checkColumn(int col, int guess) {
for (int i = 0; i < 9; i++) {
if (grid[i][col] == guess) {
return false;
}
}
return true;
}
public boolean checkBox(int row, int col, int guess) {
row = (row / 3) * 3;
col = (col / 3) * 3;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (grid[row + r][col + c] == guess) {
return false;
}
}
}
return true;
}
public boolean checkGuess(int row, int col, int guess) {
return (checkRow(row, guess) && checkColumn(col, guess) && checkBox(row, col, guess));
}
public void solve() {
int nEmptyCells = EmptyCells.size();
String tempR, tempC;
int tRow, tCol, counter = 0;
if (isEmpty() == false) {
System.out.println(
"Sudoku has no empty cells, you have either provided a solved sudoku or entered something incorrectly.");
} else {
for (int i = 0; i < nEmptyCells; i++) {
tempR = ((EmptyCells.get(i)).substring(0, 1));
tempC = ((EmptyCells.get(i)).substring(2, 3));
tRow = Integer.parseInt(tempR);
tCol = Integer.parseInt(tempC);
for (int v = 1; v < 10; v++) {
if (checkGuess(tRow, tCol, v) == true) {
this.grid[tRow][tCol] = v;
counter++;
System.out.println("Solved row " + tRow + " column " + tCol + " with " + v);
}
}
}
}
System.out.println("Total appended: " + counter);
}
}
source to share
This problem has already been solved using Backtracking algorithms:
Sudoku Backtracking Algorithm (Java)
source to share
Your question in a nutshell "For a given input, why am I getting 66 apps when there are only 51 blank cells?"
Your current algorithm:
- For every empty cell in the grid
- Use the current state of the grid
- Guess every number from 1 to 9
- Check current guess as possible solution in column, row and field
- Updating grid state with possible solution
- Keep trying every number until 9
To answer your question, you accept all possible solutions as cell-specific solutions, given the current state of the grid. As per your algorithm, it outputs 66 solutions correctly.
What can you do:
- Write down all possible solutions for each empty cell in the grid without updating the grid.
- Determine all permutations of possible solutions for the mesh
- Loop through all permutations and check each set of permutations as a grid solution
source to share