Changes

16x16 Puzzle // A Backtracking program in C++ to solve Sudoku problem #include <stdio.h> // UNASSIGNED is used for empty cells in sudoku grid #define UNASSIGNED 0 // N is used for the size of Sudoku grid. Size will be NxN #define N 16 // This function finds an entry in grid that is still unassigned 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 16 for (int num = 1; num <= 16; 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 an 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 an 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 an assigned entry within the specified 4x4 box matches the given number. */ bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num) { for (int row = 0; row < 4; row++) for (int col = 0; col < 4; 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 4x4 box */ return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) && !UsedInBox(grid, row - row%4 , col - col%4, num)&& grid[row][col]==UNASSIGNED; } /* 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"); } } /* Driver Program to test above functions */ int main() { //https://puzzlemadness.co.uk/16by16giantsudoku/ // 0 means unassigned cells

{0, 0, 11, 9, 0, 7, 0, 0, 0, 0, 0, 12, 0, 8, 16, 5}, {0, 0, 10, 0, 11, 13, 0, 0, 0, 0, 0, 3, 12, 0, 6, 0}, {0, 5, 0, 0, 10, 15, 0, 1, 7, 2, 0, 0, 14, 11, 0, 0}, {0, 0, 5, 0, 0, 12, 14, 0, 0, 10, 0, 0, 15, 0, 0, 4}, {9, 0, 14, 6, 0, 0, 1, 0, 16, 0, 2, 0, 3, 0, 13, 0}, {8, 13, 0, 4, 0, 0, 0, 0, 12, 7, 3, 0, 0, 6, 0, 0}, {0, 16, 12, 0, 0, 5, 0, 9, 0, 13, 14, 4, 1, 0, 0, 0}}; if (SolveSudoku(grid) == true) printGrid(grid); else printf("No solution exists"); return 0; }

{13, 0, 0, 5, 0, 2, 23, 14, 4, 18, 22, 0, 17, 0, 0, 20, 0, 1, 9, 21, 12, 0, 0, 8, 11}, {14, 23, 0, 24, 0, 0, 0, 0, 0, 0, 0, 0, 20, 25, 0, 3, 4, 13, 0, 11, 21, 9, 5, 18, 22}, {7, 0, 0, 11, 17, 20, 24, 0, 0, 0, 3, 4, 1, 12, 0, 0, 6, 14, 0, 5, 25, 13, 0, 0, 0}, {0, 0, 16, 9, 0, 17, 11, 7, 10, 25, 0, 0, 0, 13, 6, 0, 0, 18, 0, 0, 19, 4, 0, 0, 20}, {6, 15, 0, 19, 4, 13, 0, 0, 5, 0, 18, 11, 0, 0, 9, 8, 22, 16, 25, 10, 7, 0, 0, 0, 0}, {0, 0, 0, 2, 0, 0, 10, 19, 3, 0, 1, 0, 22, 9, 4, 11, 15, 0, 20, 0, 0, 8, 23, 0, 25}, {0, 24, 8, 13, 1, 0, 0, 4, 20, 0, 17, 14, 0, 0, 18, 0, 16, 22, 5, 0, 11, 0, 10, 0, 0}, {23, 10, 0, 0, 0, 0, 0, 0, 18, 0, 6, 0, 16, 0, 0, 17, 1, 0, 13, 0, 0, 3, 19, 12, 0}, {25, 5, 0, 14, 11, 0, 17, 0, 8, 24, 13, 0, 19, 23, 15, 9, 0, 0, 12, 0, 20, 0, 22, 0, 7}, {0, 0, 17, 4, 0, 22, 15, 0, 23, 11, 12, 25, 0, 0, 0, 0, 18, 8, 0, 7, 0, 0, 14, 0, 13}, {19, 6, 23, 22, 8, 0, 0, 1, 25, 4, 14, 2, 0, 3, 7, 13, 10, 11, 16, 0, 0, 0, 0, 0, 0}, {0, 4, 0, 17, 0, 3, 0, 24, 0, 8, 20, 23, 11, 10, 25, 22, 0, 0, 0, 12, 13, 2, 18, 6, 0}, {0, 0, 7, 16, 0, 0, 6, 17, 2, 21, 0, 18, 0, 0, 0, 19, 0, 0, 8, 0, 0, 0, 0, 4, 0}, {18, 9, 25, 1, 2, 11, 0, 0, 13, 22, 4, 0, 21, 0, 5, 0, 23, 7, 0, 0, 15, 0, 3, 0, 8}, {0, 21, 10, 0, 0, 12, 0, 20, 16, 0, 19, 0, 0, 0, 0, 15, 14, 4, 2, 18, 23, 25, 11, 7, 0}};