Question

complete sudoku problem

//***************************************************************

// D.S. Malik

//

// This class specifies the functions to solve a sudoku problem.

//***************************************************************

class sudoku

{

public:

sudoku();

//default constructor

//Postcondition: grid is initialized to 0

sudoku(int g[][9]);

//constructor

//Postcondition: grid = g

void initializeSudokuGrid();

//Function to promt the user to specify the numbers of the

//partially filled grid.

//Postcondition: grid is initialized to the numbers

// specified by the user.

void initializeSudokuGrid(int g[][9]);

//Function to initialize grid to g

//Postcondition: grid = g;

void printSudokuGrid();

//Function to print the sudoku grid.

bool solveSudoku();

//Funtion to solve the sudoku problem.

//Postcondition: If a solution exits, it returns true,

// otherwise it returns false.

bool findEmptyGridSlot(int &row, int &col);

//Function to determine if the grid slot specified by

//row and col is empty.

//Postcondition: Returns true if grid[row][col] = 0;

bool canPlaceNum(int row, int col, int num);

//Function to determine if num can be placed in

//grid[row][col]

//Postcondition: Returns true if num can be placed in

// grid[row][col], otherwise it returns false.

bool numAlreadyInRow(int row, int num);

//Function to determine if num is in grid[row][]

//Postcondition: Returns true if num is in grid[row][],

// otherwise it returns false.

bool numAlreadyInCol(int col, int num);

//Function to determine if num is in grid[row][]

//Postcondition: Returns true if num is in grid[row][],

// otherwise it returns false.

bool numAlreadyInBox(int smallGridRow, int smallGridCol,

int num);

//Function to determine if num is in the small grid

//Postcondition: Returns true if num is in small grid,

// otherwise it returns false.

private:

int grid[9][9];

};

#include <iostream>

#include "sudoku.h"

using namespace std;

sudoku::sudoku()

{

cout << "Write the definition. ." << endl;

}

sudoku::sudoku(int g[][9])

{

cout << "Write the definition." << endl;

}

void sudoku::initializeSudokuGrid()

{

cout << "Write the definition." << endl;

}

void sudoku::initializeSudokuGrid(int g[][9])

{

cout << "Write the definition. " << endl;

}

void sudoku::printSudokuGrid()

{

cout << "Write the definition." << endl;

}

bool sudoku::solveSudoku()

{

int row, col;

if (findEmptyGridSlot(row, col))

{

for (int num = 1; num <= 9; num++)

{

if (canPlaceNum(row, col, num))

{

grid[row][col] = num;

if (solveSudoku()) //recursive call

return true;

grid[row][col] = 0; //backtrack

}

}

return false;

}

else

return true; //there are no empty slots

}

bool sudoku::findEmptyGridSlot(int &row, int &col)

{

cout << "Write the definition."<< endl;

}

bool sudoku::canPlaceNum(int row, int col, int num)

{

cout << "Write the definition."<< endl;

}

bool sudoku::numAlreadyInRow(int row, int num)

{

cout << "Write the definition." << endl;

}

bool sudoku::numAlreadyInCol(int col, int num)

{

cout << "Write the definition." << endl;

}

bool sudoku::numAlreadyInBox(int smallGridRow, int smallGridCol,

int num)

{

cout << "Write the definition." << endl;

}

Answer 1

CODE

import java.lang.*; 

public class Sudoku 
{ 
        int[] mat[]; 
        int N; // number of columns/rows. 
        int SRN; // square root of N 
        int K; // No. Of missing digits 

        // Constructor 
        Sudoku(int N, int K) 
        { 
                this.N = N; 
                this.K = K; 

                // Compute square root of N 
                Double SRNd = Math.sqrt(N); 
                SRN = SRNd.intValue(); 

                mat = new int[N][N]; 
        } 

        // Sudoku Generator 
        public void fillValues() 
        { 
                // Fill the diagonal of SRN x SRN matrices 
                fillDiagonal(); 

                // Fill remaining blocks 
                fillRemaining(0, SRN); 

                // Remove Randomly K digits to make game 
                removeKDigits(); 
        } 

        // Fill the diagonal SRN number of SRN x SRN matrices 
        void fillDiagonal() 
        { 

                for (int i = 0; i<N; i=i+SRN) 

                        // for diagonal box, start coordinates->i==j 
                        fillBox(i, i); 
        } 

        // Returns false if given 3 x 3 block contains num. 
        boolean unUsedInBox(int rowStart, int colStart, int num) 
        { 
                for (int i = 0; i<SRN; i++) 
                        for (int j = 0; j<SRN; j++) 
                                if (mat[rowStart+i][colStart+j]==num) 
                                        return false; 

                return true; 
        } 

        // Fill a 3 x 3 matrix. 
        void fillBox(int row,int col) 
        { 
                int num; 
                for (int i=0; i<SRN; i++) 
                { 
                        for (int j=0; j<SRN; j++) 
                        { 
                                do
                                { 
                                        num = randomGenerator(N); 
                                } 
                                while (!unUsedInBox(row, col, num)); 

                                mat[row+i][col+j] = num; 
                        } 
                } 
        } 

        // Random generator 
        int randomGenerator(int num) 
        { 
                return (int) Math.floor((Math.random()*num+1)); 
        } 

        // Check if safe to put in cell 
        boolean CheckIfSafe(int i,int j,int num) 
        { 
                return (unUsedInRow(i, num) && 
                                unUsedInCol(j, num) && 
                                unUsedInBox(i-i%SRN, j-j%SRN, num)); 
        } 

        // check in the row for existence 
        boolean unUsedInRow(int i,int num) 
        { 
                for (int j = 0; j<N; j++) 
                if (mat[i][j] == num) 
                                return false; 
                return true; 
        } 

        // check in the row for existence 
        boolean unUsedInCol(int j,int num) 
        { 
                for (int i = 0; i<N; i++) 
                        if (mat[i][j] == num) 
                                return false; 
                return true; 
        } 

        // A recursive function to fill remaining 
        // matrix 
        boolean fillRemaining(int i, int j) 
        { 
                // System.out.println(i+" "+j); 
                if (j>=N && i<N-1) 
                { 
                        i = i + 1; 
                        j = 0; 
                } 
                if (i>=N && j>=N) 
                        return true; 

                if (i < SRN) 
                { 
                        if (j < SRN) 
                                j = SRN; 
                } 
                else if (i < N-SRN) 
                { 
                        if (j==(int)(i/SRN)*SRN) 
                                j = j + SRN; 
                } 
                else
                { 
                        if (j == N-SRN) 
                        { 
                                i = i + 1; 
                                j = 0; 
                                if (i>=N) 
                                        return true; 
                        } 
                } 

                for (int num = 1; num<=N; num++) 
                { 
                        if (CheckIfSafe(i, j, num)) 
                        { 
                                mat[i][j] = num; 
                                if (fillRemaining(i, j+1)) 
                                        return true; 

                                mat[i][j] = 0; 
                        } 
                } 
                return false; 
        } 

        // Remove the K no. of digits to 
        // complete game 
        public void removeKDigits() 
        { 
                int count = K; 
                while (count != 0) 
                { 
                        int cellId = randomGenerator(N*N); 

                        // System.out.println(cellId); 
                        // extract coordinates i and j 
                        int i = (cellId/N); 
                        int j = cellId%9; 
                        if (j != 0) 
                                j = j - 1; 

                        // System.out.println(i+" "+j); 
                        if (mat[i][j] != 0) 
                        { 
                                count--; 
                                mat[i][j] = 0; 
                        } 
                } 
        } 

        // Print sudoku 
        public void printSudoku() 
        { 
                for (int i = 0; i<N; i++) 
                { 
                        for (int j = 0; j<N; j++) 
                                System.out.print(mat[i][j] + " "); 
                        System.out.println(); 
                } 
                System.out.println(); 
        } 

        // Driver code 
        public static void main(String[] args) 
        { 
                int N = 9, K = 20; 
                Sudoku sudoku = new Sudoku(N, K); 
                sudoku.fillValues(); 
                sudoku.printSudoku(); 
        } 
} 

OUTPUT

5 4 0 3 1 0 0 9 8 
0 0 0 5 2 0 1 0 6 
6 0 8 0 9 4 2 3 5 
1 2 5 0 8 7 3 6 9 
9 6 7 2 5 3 8 1 4 
0 8 4 0 6 9 5 7 2 
2 5 0 9 3 0 4 8 7 
8 0 0 6 4 2 9 0 3 
4 3 9 0 7 5 0 2 1