Solving Sudoku Programmatically

3k views Asked by At

I'm attempting to solve a Sudoku puzzle using Java. Currently this class is unable to solve a Sudoku properly.

This class attempts to look for the 0s (blank spaces) within the 9x9 matrix and notes down the position of the 0 in a list for later referencing. Following which it will then use those positions to solve that one 0. Unfortunately, it does not seem to work as I'd 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 it solves the puzzle, it appends 66 positions for some weird reason. I can't seem to pinpoint the issue. Any help would be greatly appreciated!

This is the attempted solution that it 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);

    }

}
2

There are 2 answers

0
Stephen Donecker On

Your question in a nutshell "For the given input why do I get 66 appends when there are only 51 empty cells?"

Your current algorithm:

  • For each empty cell in the grid
  • Use the current state of the grid
  • Guess each number 1 to 9
  • Verify current guess as a possible solution in col, row, and box
  • Update grid state with possible solution
  • Continue trying each number to 9

To answer your question you are accepting all possible solutions as solutions for a particular cell given the current state of the grid. According to your algorithm it correctly results in 66 solutions.

What you could do is:

  • Record all possible solutions for each empty cell in the grid without grid updates
  • Determine all permutations of possible solutions for the grid
  • Loop through all permutations and verify each permutation set as a solution to the grid
0
Behzad On

This problem solved already as well by Backtracking algorithms:

Sudoku backtracking algorithm (Java)

Sudoku solving algorithm with back-tracking