Consider a 6x6 matrix made up of 6 3x2 boxes. Given the starting numbers add the
ID: 3543031 • Letter: C
Question
Consider a 6x6 matrix made up of 6 3x2 boxes. Given the starting numbers add the digits 1-6 to the grid such that every row, column and 3x2 box contains every digit 1-6 once. Write a recursive backtracking program that will solve the puzzle. Read in the file from a file called puzzle.txt.
Your starting puzzle values must be read in from a file which contains 6 integer values for each row, and of course all 6 rows. Zero's 0's are to signify no starting value. So far this is my code except its for a 9x9 matrix. If someone could help me and change my code to be a 6x6 matrix and read in from a file puzzle.txt I would really appreciate it.
My code listed below. import java.util.Scanner;
public class Sudoku
{
public static void main(String[] args)
{
int[][] grid = readAPuzzle();
if (!isValid(grid))
System.out.println("Invalid input");
else if (search(grid)) {
System.out.println("The solution is found:");
printGrid(grid);
}
else
System.out.println("No solution");
}
public static int[][] readAPuzzle()
{
Scanner input = new Scanner(System.in);
System.out.println("Enter a Sudoku puzzle to be solved:");
int[][] grid = new int[9][9];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
grid[i][j] = input.nextInt();
return grid;
}
public static int[][] getFreeCellList(int[][] grid)
{
// Determine the number of free cells
int numberOfFreeCells = 0;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (grid[i][j] == 0)
numberOfFreeCells++;
int[][] freeCellList = new int[numberOfFreeCells][2];
int count = 0;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (grid[i][j] == 0)
{
freeCellList[count][0] = i;
freeCellList[count++][1] = j;
}
return freeCellList;
}
// Print the values
public static void printGrid(int[][] grid)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
System.out.print(grid[i][j] + " ");
System.out.println();
}
}
// Search for a solution
public static boolean search(int[][] grid)
{
int[][] freeCellList = getFreeCellList(grid); //Free cells
int k = 0; //Start from the first free cell
boolean found = false;
while (!found)
{
int i = freeCellList[k][0];
int j = freeCellList[k][1];
if (grid[i][j] == 0)
grid[i][j] = 1; // Start with 1
if (isValid(i, j, grid))
{
if (k + 1 == freeCellList.length)
{
found = true;
}
else
{
k++;
}
}
else if (grid[i][j] < 9)
{
grid[i][j] = grid[i][j] + 1;
}
else
{
while (grid[i][j] == 9)
{
grid[i][j] = 0;
if (k == 0) {
return false;
}
k--;
i = freeCellList[k][0];
j = freeCellList[k][1];
}
grid[i][j] = grid[i][j] + 1;
}
}
return true; // A solution is found
}
public static boolean isValid(int i, int j, int[][] grid)
{
for (int column = 0; column < 9; column++)
if (column != j && grid[i][column] == grid[i][j])
return false;
for (int row = 0; row < 9; row++)
if (row != i && grid[row][j] == grid[i][j])
return false;
for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)
if (row != i && col != j && grid[row][col] == grid[i][j])
return false;
return true; //The current value at grid[i][j] is valid
}
public static boolean isValid(int[][] grid)
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (grid[i][j] != 0 && !isValid(i, j, grid)) return false;
return true; // The fixed cells are valid
}
}
Explanation / Answer
import java.util.*;
import java.io.*;
class SudokuSolver
{
public static void main(String[] args) throws FileNotFoundException
{
int[][] grid = new int[6][6];
Scanner in = new Scanner(System.in);
System.out.print("Please enter your sudoku file name (include file extension): ");
String fileName = in.next();
File file = new File(fileName);
in.close();
Scanner scanner = new Scanner(new File("puzzle.txt"));
System.out.println("Your puzzle:");
printGrid(grid);
System.out.println();
solve(grid, 0, 0);
}
public static void printGrid(int[][] array)
{
System.out.println();
for(int j=0; j<array.length;j++)
{
for(int i=0;i<array.length;i++)
{
if(i==5)
{
System.out.println(array[j][i]);
}
else
{
System.out.print(array[j][i]);
}
}
}
}
public static boolean checkRow(int[][] grid, int row, int num )
{
for(int col =0; col<6; col++)
if(grid[row][col] == num)
return false ;
return true ;
}
public static boolean checkCol(int[][] grid, int col, int num)
{
for(int row = 0; row < 6; row++)
if(grid[row][col] == num)
return false ;
return true ;
}
public static boolean checkBox(int[][] grid, int row, int col, int num)
{
row = (row / 2) * 2 ;
col = (col / 3) * 3 ;
for( int r = 0; r < 2; r++ )
{
for( int c = 0; c < 3; c++ )
{
if(grid[row+r][col+c] == num )
return false ;
}
}
return true ;
}
public static void next(int[][] puzzle, int row, int col)
{
if(col<=4)
solve(puzzle,row,col+1);
else
solve(puzzle,row+1,0);
}
public static int solve(int[][] puzzle, int row, int col)
{
if(row>5)
{
System.out.println("Solution Found:");
printGrid(puzzle);
return 0;
}
if(puzzle[row][col] != 0)
{
next(puzzle,row,col);
}
else
{
for(int num = 1;num<7;num++)
{
if(checkRow(puzzle,row,num) && checkCol(puzzle,col,num) && checkBox(puzzle,row,col,num))
{
puzzle[row][col] = num;
next(puzzle,row,col);
}
}
puzzle[row][col] = 0;
}
return 0;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.