From a1b55385e3c0d7d5c75178bc1307fba685b0f3d7 Mon Sep 17 00:00:00 2001 From: Matthias Melcher Date: Sun, 13 Aug 2023 18:20:43 +0200 Subject: Random testing and fixing. --- test/sudoku.cxx | 15 +- test/sudoku_generator.cpp | 590 ------------------------------------------- test/sudoku_generator.cxx | 630 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 643 insertions(+), 592 deletions(-) delete mode 100644 test/sudoku_generator.cpp create mode 100644 test/sudoku_generator.cxx diff --git a/test/sudoku.cxx b/test/sudoku.cxx index 9d2e52dcb..43fe37124 100644 --- a/test/sudoku.cxx +++ b/test/sudoku.cxx @@ -1082,7 +1082,7 @@ Sudoku::new_cb(Fl_Widget *widget, void *) { } -extern int generate_sudoku(int grid_data[81]); +extern int generate_sudoku(int grid_data[81], int minHints, int maxHints); // Create a new game... void @@ -1091,7 +1091,7 @@ Sudoku::new_game(time_t seed) { { int grid_data[81]; int *g = grid_data; - generate_sudoku(grid_data); + generate_sudoku(grid_data, 22, 31); SudokuCell *cell; for (int j = 0; j < 9; j ++) { for (int k = 0; k < 9; k ++) { @@ -1356,6 +1356,17 @@ Sudoku::solve_game() { // Main entry for game... +// Note 21-17 (proven minimum) clues can be set +// easy: 30-36 +// expert: 25-30 +// algo: 22 (rare) to 25 + +// extremely easy: 46+ +// easy: 36-46 +// medium: 32-35 +// difficult: 28-31 +// evil: 17-27 + int main(int argc, char *argv[]) { Sudoku s; diff --git a/test/sudoku_generator.cpp b/test/sudoku_generator.cpp deleted file mode 100644 index 8f6469e19..000000000 --- a/test/sudoku_generator.cpp +++ /dev/null @@ -1,590 +0,0 @@ -// -// Sudoku game generator using the Fast Light Tool Kit (FLTK). -// -// Copyright (c) 2018 Vaibhav Thakkar. -// Copyright 2023 by Vaibhav Thakkar and Matthias Melcher. -// -// This library is free software. Distribution and use rights are outlined in -// the file "COPYING" which should have been included with this file. If this -// file is missing or damaged, see the license at: -// -// https://www.fltk.org/COPYING.php -// -// Please see the following page on how to report bugs and issues: -// -// https://www.fltk.org/bugs.php -// - -// -// This solver is based on the work of Vaibhav Thakkar -// from https://github.com/vaithak/Sudoku-Generator -// vaithak/Sudoku-Generator is licensed under the MIT License -// Copyright (c) 2018 Vaibhav Thakkar -// -// The solver was modified to fit FLTKs requirements of using minimal C++ -// and adapted to the FLTK naming scheme. -// - -#include -#include -#include -#include - -#define UNASSIGNED 0 - -class Sudoku_Generator { -private: -public: - int grid[9][9]; - int solnGrid[9][9]; - int guessNum[9]; - int gridPos[81]; - int difficultyLevel; - bool grid_status; - -public: - Sudoku_Generator (); - Sudoku_Generator(int[81], bool row_major=true); - void fillEmptyDiagonalBox(int); - void createSeed(); - void printGrid(); - bool solveGrid(); - void countSoln(int &number); - void genPuzzle(); - bool gridStatus(); - void calculateDifficulty(); - int branchDifficultyScore(); -}; - -// Generate a random number between 0 and maxLimit-1 -int genRandNum(int maxLimit) -{ - return rand()%maxLimit; -} - - -// We take an integer array of the length n and swap the content around randomly. -// The function was part of the c++11 standard, but was removed in C++17 because -// it was regarded as flawed. -// This implementation is a minimal hack without care about random dstribution. -// For additional randomness, we do that three times. -void random_shuffle(int *data, int n, int (*r)(int)) -{ - for (int n = 3; n>0; --n) { - for (int i = n-1; i > 0; --i) { - int j = r(i+1); - int tmp = data[i]; - data[i] = data[j]; - data[j] = tmp; - } - } -} - -// Helper functions for solving grid -bool FindUnassignedLocation(int grid[9][9], int &row, int &col) -{ - for (row = 0; row < 9; row++) - { - for (col = 0; col < 9; col++) - { - if (grid[row][col] == UNASSIGNED) - return true; - } - } - return false; -} - -// Return true if num exists in row of grid. -bool UsedInRow(int grid[9][9], int row, int num) -{ - for (int col = 0; col < 9; col++) - { - if (grid[row][col] == num) - return true; - } - return false; -} - -// Return true if num exists in col of grid. -bool UsedInCol(int grid[9][9], int col, int num) -{ - for (int row = 0; row < 9; row++) - { - if (grid[row][col] == num) - return true; - } - return false; -} - -// Return true if num exists in box at row, col of grid. -bool UsedInBox(int grid[9][9], 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; -} - -// Return true if a number can be used at row, col and does not appear -// yet in the rom, column, or box -bool isSafe(int grid[9][9], int row, int col, int num) -{ - return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) && !UsedInBox(grid, row - row%3 , col - col%3, num); -} - -// Fill the box at idx*3, idx*3 with random values -void Sudoku_Generator::fillEmptyDiagonalBox(int idx) -{ - int start = idx*3; - random_shuffle(guessNum, 9, genRandNum); - for (int i = 0; i < 3; ++i) - { - for (int j = 0; j < 3; ++j) - { - this->grid[start+i][start+j] = guessNum[i*3+j]; - } - } -} - -// Create a soved Sudoku puzzle -void Sudoku_Generator::createSeed() -{ - /* Fill diagonal boxes to form: - x | . | . - . | x | . - . | . | x - */ - this->fillEmptyDiagonalBox(0); - this->fillEmptyDiagonalBox(1); - this->fillEmptyDiagonalBox(2); - - /* Fill the remaining blocks: - x | x | x - x | x | x - x | x | x - */ - this->solveGrid(); // Not truly random, but still good enough because we generate random diagonals. - - // Saving the solution grid - for(int i=0;i<9;i++) - { - for(int j=0;j<9;j++) - { - this->solnGrid[i][j] = this->grid[i][j]; - } - } -} - -// Initialize the egenrator -Sudoku_Generator::Sudoku_Generator() -{ - // initialize difficulty level - this->difficultyLevel = 0; - - // Randomly shuffling the array of removing grid positions - for(int i=0;i<81;i++) - { - this->gridPos[i] = i; - } - - random_shuffle(gridPos, 81, genRandNum); - - // Randomly shuffling the guessing number array - for(int i=0;i<9;i++) - { - this->guessNum[i]=i+1; - } - - random_shuffle(guessNum, 9, genRandNum); - - // Initialising the grid - for(int i=0;i<9;i++) - { - for(int j=0;j<9;j++) - { - this->grid[i][j]=0; - } - } - - grid_status = true; -} - -// Custom Initialising with grid passed as argument -Sudoku_Generator::Sudoku_Generator(int grid_data[81], bool row_major) -{ - // First pass: Check if all cells are valid - for(int i=0; i<81; ++i) - { - int curr_num = grid_data[i]; - if(!((curr_num == UNASSIGNED) || (curr_num > 0 && curr_num < 10))) - { - grid_status=false; - return; - } - - if(row_major) grid[i/9][i%9] = curr_num; - else grid[i%9][i/9] = curr_num; - } - - // Second pass: Check if all columns are valid - for (int col_num=0; col_num<9; ++col_num) - { - bool nums[10]={false}; - for (int row_num=0; row_num<9; ++row_num) - { - int curr_num = grid[row_num][col_num]; - if(curr_num!=UNASSIGNED && nums[curr_num]==true) - { - grid_status=false; - return; - } - nums[curr_num] = true; - } - } - - // Third pass: Check if all rows are valid - for (int row_num=0; row_num<9; ++row_num) - { - bool nums[10]={false}; - for (int col_num=0; col_num<9; ++col_num) - { - int curr_num = grid[row_num][col_num]; - if(curr_num!=UNASSIGNED && nums[curr_num]==true) - { - grid_status=false; - return; - } - nums[curr_num] = true; - } - } - - // Fourth pass: Check if all blocks are valid - for (int block_num=0; block_num<9; ++block_num) - { - bool nums[10]={false}; - for (int cell_num=0; cell_num<9; ++cell_num) - { - int curr_num = grid[((int)(block_num/3))*3 + (cell_num/3)][((int)(block_num%3))*3 + (cell_num%3)]; - if(curr_num!=UNASSIGNED && nums[curr_num]==true) - { - grid_status=false; - return; - } - nums[curr_num] = true; - } - } - - // Randomly shuffling the guessing number array - for(int i=0;i<9;i++) - { - this->guessNum[i]=i+1; - } - - random_shuffle(guessNum, 9, genRandNum); - - grid_status = true; -} - -// Return status of the custom grid passed. -bool Sudoku_Generator::gridStatus() -{ - return grid_status; -} - -// Printing the grid -void Sudoku_Generator::printGrid() -{ - for(int i=0;i<9;i++) - { - for(int j=0;j<9;j++) - { - if(grid[i][j] == 0) - printf(" ."); - else - printf(" %d", grid[i][j]); - if (((j%3) == 2) && (j < 8)) - printf(" |"); - } - printf("\n"); - if (((i%3) == 2) && (i < 8)) - printf("-------+-------+-------\n"); - } - printf("\nDifficulty of current sudoku(0 being easiest): %d\n", difficultyLevel); -} - -// Modified Sudoku solver -bool Sudoku_Generator::solveGrid() -{ - int row, col; - - // If there is no unassigned location, we are done - if (!FindUnassignedLocation(this->grid, row, col)) - return true; // success! - - // Consider digits 1 to 9 - for (int num = 0; num < 9; num++) - { - // if looks promising - if (isSafe(this->grid, row, col, this->guessNum[num])) - { - // make tentative assignment - this->grid[row][col] = this->guessNum[num]; - - // return, if success, yay! - if (solveGrid()) - return true; - - // failure, unmake & try again - this->grid[row][col] = UNASSIGNED; - } - } - - return false; // this triggers backtracking -} - -// Check if the grid is uniquely solvable -void Sudoku_Generator::countSoln(int &number) -{ - int row, col; - - if(!FindUnassignedLocation(this->grid, row, col)) - { - number++; - return ; - } - - - for(int i=0;i<9 && number<2;i++) - { - if( isSafe(this->grid, row, col, this->guessNum[i]) ) - { - this->grid[row][col] = this->guessNum[i]; - countSoln(number); - } - - this->grid[row][col] = UNASSIGNED; - } - -} -// END: Check if the grid is uniquely solvable - - -// START: Generate puzzle -void Sudoku_Generator::genPuzzle() -{ - for(int i=0;i<81;i++) - { - int x = (this->gridPos[i])/9; - int y = (this->gridPos[i])%9; - int temp = this->grid[x][y]; - this->grid[x][y] = UNASSIGNED; - - // If now more than 1 solution , replace the removed cell back. - int check=0; - countSoln(check); - if(check!=1) - { - this->grid[x][y] = temp; - } - } -} -// END: Generate puzzle - - -// START: Calculate branch difficulty score -int Sudoku_Generator::branchDifficultyScore() -{ - int emptyPositions = -1; - int tempGrid[9][9]; - int sum=0; - - for(int i=0;i<9;i++) - { - for(int j=0;j<9;j++) - { - tempGrid[i][j] = this->grid[i][j]; - } - } - - while(emptyPositions!=0) - { - Fl_Int_Vector empty[81]; - int empty_n = 0; - - for(int i=0;i<81;i++) - { - if(tempGrid[(int)(i/9)][(int)(i%9)] == 0) - { - // TODO: C++ - Fl_Int_Vector temp; - temp.push_back(i); - - for(int num=1;num<=9;num++) - { - if(isSafe(tempGrid,i/9,i%9,num)) - { - temp.push_back(num); - } - } - - empty[empty_n++] = temp; - } - - } - - if(empty_n == 0) - { - return sum; - } - - int minIndex = 0; - - int check = empty_n; - for(int i=0;isolnGrid[rowIndex][colIndex]; - sum = sum + ((branchFactor-2) * (branchFactor-2)) ; - - emptyPositions = empty_n - 1; - } - - return sum; - -} -// END: Finish branch difficulty score - - -// START: Calculate difficulty level of current grid -void Sudoku_Generator::calculateDifficulty() -{ - int B = branchDifficultyScore(); - int emptyCells = 0; - - for(int i=0;i<9;i++) - { - for(int j=0;j<9;j++) - { - if(this->grid[i][j] == 0) - emptyCells++; - } - } - - this->difficultyLevel = B*100 + emptyCells; -} -// END: calculating difficulty level - - -// START: The main function -int generate_sudoku(int grid_data[81]) -{ -#if 0 - int i, j; - FILE *f = fopen("/Users/matt/dev/su.cxx", "wb"); - fprintf(f, "// all horizontal chains\n"); - for (i=0; i<9; i++) { - fprintf(f, "{ "); - for (j=0; j<9; j++) { - fprintf(f, "%2d, ", i*9+j); - } - fprintf(f, "},\n"); - } - fprintf(f, "// all vertical chains\n"); - for (i=0; i<9; i++) { - fprintf(f, "{ "); - for (j=0; j<9; j++) { - fprintf(f, "%2d, ", j*9+i); - } - fprintf(f, "},\n"); - } - fprintf(f, "// all squares\n"); - for (i=0; i<9; i++) { - fprintf(f, "{ "); - for (j=0; j<9; j++) { - fprintf(f, "%2d, ", ((i%3)*3) + ((i/3)*3*9) + (j%3) + (j/3)*9); - } - fprintf(f, "},\n"); - } - fprintf(f, "// every field is part of 3 chains\n"); - for (i=0; i<81; i++) { - fprintf(f, "{ "); - int col = i % 9; - int row = i / 9; - fprintf(f, " %2d, %2d, %2d ", - i/9, i%9, (col/3) + (row/3)*3 - ); - fprintf(f, "},\n"); - } - fclose(f); -#endif - - - // Initialising seed for random number generation - srand((unsigned int)time(NULL)); - - // Creating an instance of Sudoku - Sudoku_Generator *puzzle = new Sudoku_Generator(); - - // Creating a seed for puzzle generation - puzzle->createSeed(); - - // Generating the puzzle - puzzle->genPuzzle(); - - // Calculating difficulty of puzzle - puzzle->calculateDifficulty(); - - // testing by printing the grid - puzzle->printGrid(); - -// // Printing the grid into SVG file -// string rem = "sudokuGen"; -// string path = argv[0]; -// path = path.substr(0,path.size() - rem.size()); -// puzzle->printSVG(path); -// cout<<"The above sudoku puzzle has been stored in puzzles.svg in current folder\n"; -// // freeing the memory - - puzzle->printGrid(); - printf("Difficulty: %d\n", puzzle->difficultyLevel); - for (int d = 0; d<9; d++) { - int x = 0, y = 0; - for (;;) { - x = genRandNum(9); - y = genRandNum(9); - if (puzzle->grid[x][y] == 0) break; - } - puzzle->grid[x][y] = puzzle->solnGrid[x][y]; - printf(" %d %d\n", x, y); - puzzle->calculateDifficulty(); - printf("Difficulty: %d\n", puzzle->difficultyLevel); - } - - int *g = grid_data; - for(int i=0;i<9;i++) { - for(int j=0;j<9;j++) { - if (puzzle->grid[i][j] == UNASSIGNED) { - *g++ = -puzzle->solnGrid[i][j]; - } else { - *g++ = puzzle->solnGrid[i][j]; - } - } - } - - delete puzzle; - - return 0; -} -// END: The main function diff --git a/test/sudoku_generator.cxx b/test/sudoku_generator.cxx new file mode 100644 index 000000000..58f8d6890 --- /dev/null +++ b/test/sudoku_generator.cxx @@ -0,0 +1,630 @@ +// +// Sudoku game generator using the Fast Light Tool Kit (FLTK). +// +// Copyright (c) 2018 Vaibhav Thakkar. +// Copyright 2023 by Vaibhav Thakkar and Matthias Melcher. +// +// This library is free software. Distribution and use rights are outlined in +// the file "COPYING" which should have been included with this file. If this +// file is missing or damaged, see the license at: +// +// https://www.fltk.org/COPYING.php +// +// Please see the following page on how to report bugs and issues: +// +// https://www.fltk.org/bugs.php +// + +// +// This solver is based on the work of Vaibhav Thakkar +// from https://github.com/vaithak/Sudoku-Generator +// vaithak/Sudoku-Generator is licensed under the MIT License +// Copyright (c) 2018 Vaibhav Thakkar +// +// The solver was modified to fit FLTKs requirements of using minimal C++ +// and adapted to the FLTK naming scheme. +// + +#include +#include +#include +#include + +#define UNASSIGNED 0 + +typedef int GridData[9][9]; + +class Sudoku_Generator { +private: +public: + GridData grid; + GridData solnGrid; + int guessNum[9]; + int gridPos[81]; + int difficultyLevel; + bool grid_status; + +public: + Sudoku_Generator (); + Sudoku_Generator(int[81], bool row_major=true); + void fillEmptyDiagonalBox(int); + void createSeed(); + void printGrid(); + bool solveGrid(); + void countSoln(int &number); + void genPuzzle(int minHints); + bool gridStatus(); + void calculateDifficulty(); + void restoreWorkGrid(); + int branchDifficultyScore(); +}; + +void Sudoku_Generator::restoreWorkGrid() +{ + for(int i=0;i<9;i++) + for(int j=0;j<9;j++) + this->grid[i][j] = this->solnGrid[i][j]; +} + +// Generate a random number between 0 and maxLimit-1 +int genRandNum(int maxLimit) +{ + return rand()%maxLimit; +} + + +// We take an integer array of the length n and swap the content around randomly. +// The function was part of the c++11 standard, but was removed in C++17 because +// it was regarded as flawed. +// This implementation is a minimal hack without care about random dstribution. +// For additional randomness, we do that three times. +void random_shuffle(int *data, int n) +{ + for (int z = 3; z>0; --z) { + for (int i = n-1; i > 0; --i) { + int j = rand() % (i+1); + int tmp = data[i]; + data[i] = data[j]; + data[j] = tmp; + } + } +// printf("Rand: "); +// for (int j=0; jgrid[start+i][start+j] = guessNum[i*3+j]; + } + } +} + +// Create a solved Sudoku puzzle +void Sudoku_Generator::createSeed() +{ + /* Fill diagonal boxes to form: + x | . | . + . | x | . + . | . | x + */ + this->fillEmptyDiagonalBox(0); + this->fillEmptyDiagonalBox(1); + this->fillEmptyDiagonalBox(2); + + /* Fill the remaining blocks: + x | x | x + x | x | x + x | x | x + */ + this->solveGrid(); // Not truly random, but still good enough because we generate random diagonals. + + // Saving the solution grid + for(int i=0;i<9;i++) + { + for(int j=0;j<9;j++) + { + this->solnGrid[i][j] = this->grid[i][j]; + } + } +} + +// Initialize the egenrator +Sudoku_Generator::Sudoku_Generator() +{ + // initialize difficulty level + this->difficultyLevel = 0; + + // Randomly shuffling the array of removing grid positions + for(int i=0;i<81;i++) + { + this->gridPos[i] = i; + } + + random_shuffle(gridPos, 81); + + // Randomly shuffling the guessing number array + for(int i=0;i<9;i++) + { + this->guessNum[i]=i+1; + } + + random_shuffle(guessNum, 9); + + // Initialising the grid + for(int i=0;i<9;i++) + { + for(int j=0;j<9;j++) + { + this->grid[i][j]=0; + } + } + + grid_status = true; +} + +// Custom Initialising with grid passed as argument +Sudoku_Generator::Sudoku_Generator(int grid_data[81], bool row_major) +{ + // First pass: Check if all cells are valid + for(int i=0; i<81; ++i) + { + int curr_num = grid_data[i]; + if(!((curr_num == UNASSIGNED) || (curr_num > 0 && curr_num < 10))) + { + grid_status=false; + return; + } + + if(row_major) grid[i/9][i%9] = curr_num; + else grid[i%9][i/9] = curr_num; + } + + // Second pass: Check if all columns are valid + for (int col_num=0; col_num<9; ++col_num) + { + bool nums[10]={false}; + for (int row_num=0; row_num<9; ++row_num) + { + int curr_num = grid[row_num][col_num]; + if(curr_num!=UNASSIGNED && nums[curr_num]==true) + { + grid_status=false; + return; + } + nums[curr_num] = true; + } + } + + // Third pass: Check if all rows are valid + for (int row_num=0; row_num<9; ++row_num) + { + bool nums[10]={false}; + for (int col_num=0; col_num<9; ++col_num) + { + int curr_num = grid[row_num][col_num]; + if(curr_num!=UNASSIGNED && nums[curr_num]==true) + { + grid_status=false; + return; + } + nums[curr_num] = true; + } + } + + // Fourth pass: Check if all blocks are valid + for (int block_num=0; block_num<9; ++block_num) + { + bool nums[10]={false}; + for (int cell_num=0; cell_num<9; ++cell_num) + { + int curr_num = grid[((int)(block_num/3))*3 + (cell_num/3)][((int)(block_num%3))*3 + (cell_num%3)]; + if(curr_num!=UNASSIGNED && nums[curr_num]==true) + { + grid_status=false; + return; + } + nums[curr_num] = true; + } + } + + // Randomly shuffling the guessing number array + for(int i=0;i<9;i++) + { + this->guessNum[i]=i+1; + } + + random_shuffle(guessNum, 9); + + grid_status = true; +} + +// Return status of the custom grid passed. +bool Sudoku_Generator::gridStatus() +{ + return grid_status; +} + +// Printing the grid +void Sudoku_Generator::printGrid() +{ + for(int i=0;i<9;i++) + { + for(int j=0;j<9;j++) + { + if(grid[i][j] == 0) + printf(" ."); + else + printf(" %d", grid[i][j]); + if (((j%3) == 2) && (j < 8)) + printf(" |"); + } + printf("\n"); + if (((i%3) == 2) && (i < 8)) + printf("-------+-------+-------\n"); + } + printf("\nDifficulty of current sudoku(0 being easiest): %d\n", difficultyLevel); +} + +// Modified Sudoku solver +bool Sudoku_Generator::solveGrid() +{ + int row, col; + + // If there is no unassigned location, we are done + if (!FindUnassignedLocation(this->grid, row, col)) + return true; // success! + + // Consider digits 1 to 9 + for (int num = 0; num < 9; num++) + { + // if looks promising + if (isSafe(this->grid, row, col, this->guessNum[num])) + { + // make tentative assignment + this->grid[row][col] = this->guessNum[num]; + + // return, if success, yay! + if (solveGrid()) + return true; + + // failure, unmake & try again + this->grid[row][col] = UNASSIGNED; + } + } + + return false; // this triggers backtracking +} + +// Check if the grid is uniquely solvable +void Sudoku_Generator::countSoln(int &number) +{ + int row, col; + + if(!FindUnassignedLocation(this->grid, row, col)) + { + number++; + return ; + } + + + for(int i=0;i<9 && number<2;i++) + { + if( isSafe(this->grid, row, col, this->guessNum[i]) ) + { + this->grid[row][col] = this->guessNum[i]; + countSoln(number); + } + + this->grid[row][col] = UNASSIGNED; + } + +} +// END: Check if the grid is uniquely solvable + + +// START: Generate puzzle +void Sudoku_Generator::genPuzzle(int minHints) +{ + int numHints = 81; + for(int i=0;i<81;i++) + { + int x = (this->gridPos[i])/9; + int y = (this->gridPos[i])%9; + int temp = this->grid[x][y]; + this->grid[x][y] = UNASSIGNED; + + // If now more than 1 solution , replace the removed cell back. + int check=0; + countSoln(check); + if(check!=1) + { + this->grid[x][y] = temp; +// printf("Can't remove cell %d\n", i); + } else { + numHints--; + if (numHints <= minHints) break; + } + } + printf("Found %d hints\n", numHints); +} +// END: Generate puzzle + + +// START: Calculate branch difficulty score +int Sudoku_Generator::branchDifficultyScore() +{ + int emptyPositions = -1; + GridData tempGrid; + int sum=0; + + for(int i=0;i<9;i++) + { + for(int j=0;j<9;j++) + { + tempGrid[i][j] = this->grid[i][j]; + } + } + + while(emptyPositions!=0) + { + Fl_Int_Vector empty[81]; + int empty_n = 0; + + for(int i=0;i<81;i++) + { + if(tempGrid[(int)(i/9)][(int)(i%9)] == 0) + { + Fl_Int_Vector temp; + temp.push_back(i); + + for(int num=1;num<=9;num++) + { + if(isSafe(tempGrid,i/9,i%9,num)) + { + temp.push_back(num); + } + } + + empty[empty_n++] = temp; + } + + } + + if(empty_n == 0) + { + return sum; + } + + int minIndex = 0; + + int check = empty_n; + for(int i=0;isolnGrid[rowIndex][colIndex]; + sum = sum + ((branchFactor-2) * (branchFactor-2)) ; + + emptyPositions = empty_n - 1; + } + + return sum; + +} +// END: Finish branch difficulty score + + +// START: Calculate difficulty level of current grid +void Sudoku_Generator::calculateDifficulty() +{ + int B = branchDifficultyScore(); + int emptyCells = 0; + + for(int i=0;i<9;i++) + { + for(int j=0;j<9;j++) + { + if(this->grid[i][j] == 0) + emptyCells++; + } + } + + this->difficultyLevel = B*100 + emptyCells; +} +// END: calculating difficulty level + + +// START: The main function +int generate_sudoku(int grid_data[81], int minHints, int maxHints) +{ +#if 0 + int i, j; + FILE *f = fopen("/Users/matt/dev/su.cxx", "wb"); + fprintf(f, "// all horizontal chains\n"); + for (i=0; i<9; i++) { + fprintf(f, "{ "); + for (j=0; j<9; j++) { + fprintf(f, "%2d, ", i*9+j); + } + fprintf(f, "},\n"); + } + fprintf(f, "// all vertical chains\n"); + for (i=0; i<9; i++) { + fprintf(f, "{ "); + for (j=0; j<9; j++) { + fprintf(f, "%2d, ", j*9+i); + } + fprintf(f, "},\n"); + } + fprintf(f, "// all squares\n"); + for (i=0; i<9; i++) { + fprintf(f, "{ "); + for (j=0; j<9; j++) { + fprintf(f, "%2d, ", ((i%3)*3) + ((i/3)*3*9) + (j%3) + (j/3)*9); + } + fprintf(f, "},\n"); + } + fprintf(f, "// every field is part of 3 chains\n"); + for (i=0; i<81; i++) { + fprintf(f, "{ "); + int col = i % 9; + int row = i / 9; + fprintf(f, " %2d, %2d, %2d ", + i/9, i%9, (col/3) + (row/3)*3 + ); + fprintf(f, "},\n"); + } + fclose(f); +#endif + + + // Initialising seed for random number generation + srand((unsigned int)time(NULL)); + + // Creating an instance of Sudoku + Sudoku_Generator *puzzle = new Sudoku_Generator(); + + // Creating a seed for puzzle generation + puzzle->createSeed(); + + // Generating the puzzle + puzzle->genPuzzle(minHints); + int minDiff = 100, maxDiff = 0; + for (int zz=0; zz<100; zz++) { + time_t start; time(&start); + random_shuffle(puzzle->gridPos, 81); + puzzle->restoreWorkGrid(); + puzzle->genPuzzle(minHints); + time_t end; time(&end); + puzzle->calculateDifficulty(); + printf("--- in %ld, difficulty is %d\n", end-start, puzzle->difficultyLevel); + if (puzzle->difficultyLevel < minDiff) minDiff = puzzle->difficultyLevel; + if (puzzle->difficultyLevel > maxDiff) maxDiff = puzzle->difficultyLevel; + } + printf("Difficulty range is %d to %d\n", minDiff, maxDiff); + // 22: 55 to 1658 + // 25: 56 to 1456 + // 28: 53 to 953, 53 to 1153, 53 to 1253 + // 31: 50 to 850, 50 to 950, 50 to 850 + // 40: 41 to 141 + // 45: 36 to 136 + + + // Calculating difficulty of puzzle + puzzle->calculateDifficulty(); + + // testing by printing the grid + puzzle->printGrid(); + +// // Printing the grid into SVG file +// string rem = "sudokuGen"; +// string path = argv[0]; +// path = path.substr(0,path.size() - rem.size()); +// puzzle->printSVG(path); +// cout<<"The above sudoku puzzle has been stored in puzzles.svg in current folder\n"; +// // freeing the memory + +// puzzle->printGrid(); + printf("Difficulty: %d\n", puzzle->difficultyLevel); +// for (int d = 0; d<9; d++) { +// int x = 0, y = 0; +// for (;;) { +// x = genRandNum(9); +// y = genRandNum(9); +// if (puzzle->grid[x][y] == 0) break; +// } +// puzzle->grid[x][y] = puzzle->solnGrid[x][y]; +// printf(" %d %d\n", x, y); +// puzzle->calculateDifficulty(); +// printf("Difficulty: %d\n", puzzle->difficultyLevel); +// } + + int *g = grid_data; + for(int i=0;i<9;i++) { + for(int j=0;j<9;j++) { + if (puzzle->grid[i][j] == UNASSIGNED) { + *g++ = -puzzle->solnGrid[i][j]; + } else { + *g++ = puzzle->solnGrid[i][j]; + } + } + } + + delete puzzle; + + return 0; +} +// END: The main function -- cgit v1.2.3