Sudoku in Java (HARD/ADVANCED)

Given a partially filled 9 x 9 sudoku board, you need to output a solution to it.

Input

The first line contains N which is the number of Sudoku puzzles. N Sudoku puzzles follow. Each one contains 9 lines with each line containing 9 space separated integers. A 0 indicates an unfilled square, and an integer between 1 and 9 denotes a filled square with that value.

Output

Output to STDOUT the completely filled Sudoku board for each Sudoku. If there are multiple solutions, you can output any one.

Scoring

If your code output does not represent a valid filled Sudoku board, or if it is inconsistent with the given input, your solution will get a "Wrong Answer" judgement.

Otherwise, your score is the ratio (4000 - characters in the source code)/40. Any source code which solves all the testcases and has greater than 2000 characters will get a nominal score of 0.1. Your goal is to reach as close to 100 as possible.

Your code will be tested on multiple testcases. Each testcase will have N sudokus and your code should obey all the limits present in the environment to clear the testcase.

Your code will be judged as a wrong answer even if it fails any one of the testcase. Each sudoku is a different variant and a code that's optimal for one configuration needn't be for another.

Test Case Generation

You are guaranteed that there is at least one solution satisfying the input. All inputs are randomly generated, by filling in up to 25 random squares. If the grid generated isn't solvable, it is discarded and the procedure is repeated.

Sample Input

2
0 0 0 0 0 0 0 0 0
0 0 8 0 0 0 0 4 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 8 0 0 0 0 4 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0

Sample Output

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

Task

Complete the function sudoku_solve that takes a 2-D array of sudoku grid as input.

#include<iostream>

#include<vector>

using namespace std;

#define UNASSIGNED 0

#define N 9

bool FindUnassignedLocation(int grid[N][N], int &row, int &col);

// Checks whether it will be legal to assign num to the given row,col

bool isSafe(int grid[N][N], int row, int col, int num);

/* Takes a partially filled-in grid and attempts to assign values to

  all unassigned locations in such a way to meet the requirements

  for Sudoku solution (non-duplication across rows, columns, and boxes) */

bool SolveSudoku(int grid[N][N])

{

    int row, col;

    // If there is no unassigned location, we are done

    if (!FindUnassignedLocation(grid, row, col))

       return true; // success!

    // consider digits 1 to 9

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

    {

        // if looks promising

        if (isSafe(grid, row, col, num))

        {

            // make tentative assignment

            grid[row][col] = num;

            // return, if success, yay!

            if (SolveSudoku(grid))

                return true;

            // failure, unmake & try again

            grid[row][col] = UNASSIGNED;

        }

    }

    return false; // this triggers backtracking

}

/* Searches the grid to find an entry that is still unassigned. If

   found, the reference parameters row, col will be set the location

   that is unassigned, and true is returned. If no unassigned entries

   remain, false is returned. */

bool FindUnassignedLocation(int grid[N][N], int &row, int &col)

{

    for (row = 0; row < N; row++)

        for (col = 0; col < N; col++)

            if (grid[row][col] == UNASSIGNED)

                return true;

    return false;

}

/* Returns a boolean which indicates whether any assigned entry

   in the specified row matches the given number. */

bool UsedInRow(int grid[N][N], int row, int num)

{

    for (int col = 0; col < N; col++)

        if (grid[row][col] == num)

            return true;

    return false;

}

/* Returns a boolean which indicates whether any assigned entry

   in the specified column matches the given number. */

bool UsedInCol(int grid[N][N], int col, int num)

{

    for (int row = 0; row < N; row++)

        if (grid[row][col] == num)

            return true;

    return false;

}

/* Returns a boolean which indicates whether any assigned entry

   within the specified 3x3 box matches the given number. */

bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)

{

    for (int row = 0; row < 3; row++)

        for (int col = 0; col < 3; col++)

            if (grid[row+boxStartRow][col+boxStartCol] == num)

                return true;

    return false;

}

/* Returns a boolean which indicates whether it will be legal to assign

   num to the given row,col location. */

bool isSafe(int grid[N][N], int row, int col, int num)

{

    /* Check if 'num' is not already placed in current row,

       current column and current 3x3 box */

    return !UsedInRow(grid, row, num) &&

           !UsedInCol(grid, col, num) &&

           !UsedInBox(grid, row - row%3 , col - col%3, num);

}

/* A utility function to print grid  */

void printGrid(int grid[N][N])

{

    for (int row = 0; row < N; row++)

    {

       for (int col = 0; col < N; col++)

             printf("%2d", grid[row][col]);

        printf("\n");

    }

}int main(void) {

    int n, board[9][9];

    cin >> n;

    for(int i=0;i<n;i++) {

        for(int j=0;j<9;j++) {

            for(int k=0;k<9;k++) {

                board[j][k] = 0;

                cin >> board[j][k];

            }

        }

        if (SolveSudoku(board) == true)

          printGrid(board);

    else

         printf("No solution exists");

    

    }

    return 0;

}