diff options
| -rw-r--r-- | test/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | test/Makefile | 9 | ||||
| -rw-r--r-- | test/sudoku.cxx | 230 | ||||
| -rw-r--r-- | test/sudoku_generator.cpp | 590 |
4 files changed, 739 insertions, 92 deletions
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index 6fb3b5105..730da2444 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -133,7 +133,7 @@ CREATE_EXAMPLE (resize-example5c "resize-example5c.cxx;resize-arrows.cxx" fltk) CREATE_EXAMPLE (rotated_text rotated_text.cxx fltk) CREATE_EXAMPLE (scroll scroll.cxx fltk) CREATE_EXAMPLE (subwindow subwindow.cxx fltk) -CREATE_EXAMPLE (sudoku "sudoku.cxx;sudoku.plist;sudoku.icns;sudoku.rc" "fltk_images;fltk;${AUDIOLIBS}") +CREATE_EXAMPLE (sudoku "sudoku.cxx;sudoku_generator.cxx;sudoku.plist;sudoku.icns;sudoku.rc" "fltk_images;fltk;${AUDIOLIBS}") CREATE_EXAMPLE (symbols symbols.cxx fltk) CREATE_EXAMPLE (tabs tabs.fl fltk) CREATE_EXAMPLE (table table.cxx fltk) diff --git a/test/Makefile b/test/Makefile index f1187caf5..51af5bbcb 100644 --- a/test/Makefile +++ b/test/Makefile @@ -131,6 +131,7 @@ CPPFILES =\ shape.cxx \ subwindow.cxx \ sudoku.cxx \ + sudoku_generator.cxx \ symbols.cxx \ table.cxx \ tabs.cxx \ @@ -596,19 +597,19 @@ scroll$(EXEEXT): scroll.o subwindow$(EXEEXT): subwindow.o -sudoku: sudoku.o +sudoku: sudoku.o sudoku_generator.o echo Linking $@... - $(CXX) $(ARCHFLAGS) $(CXXFLAGS) $(LDFLAGS) sudoku.o -o $@ $(AUDIOLIBS) $(LINKFLTKIMG) $(LDLIBS) + $(CXX) $(ARCHFLAGS) $(CXXFLAGS) $(LDFLAGS) sudoku.o sudoku_generator.o -o $@ $(AUDIOLIBS) $(LINKFLTKIMG) $(LDLIBS) $(OSX_ONLY) $(RM) -f -r sudoku.app $(OSX_ONLY) mkdir -p sudoku.app/Contents/MacOS sudoku.app/Contents/Resources $(OSX_ONLY) $(INSTALL_BIN) sudoku$(EXEEXT) sudoku.app/Contents/MacOS $(OSX_ONLY) $(INSTALL_BIN) mac-resources/sudoku.icns sudoku.app/Contents/Resources/ $(OSX_ONLY) $(INSTALL_BIN) mac-resources/sudoku.plist sudoku.app/Contents/Info.plist -sudoku.exe: sudoku.o sudoku.rc +sudoku.exe: sudoku.o sudoku_generator.o sudoku.rc echo Linking $@... $(RC) sudoku.rc sudokures.o - $(CXX) $(ARCHFLAGS) $(CXXFLAGS) $(LDFLAGS) sudoku.o sudokures.o -o $@ $(AUDIOLIBS) $(LINKFLTKIMG) $(LDLIBS) + $(CXX) $(ARCHFLAGS) $(CXXFLAGS) $(LDFLAGS) sudoku.o sudoku_generator.o sudokures.o -o $@ $(AUDIOLIBS) $(LINKFLTKIMG) $(LDLIBS) symbols$(EXEEXT): symbols.o diff --git a/test/sudoku.cxx b/test/sudoku.cxx index 97766ac2f..24529665c 100644 --- a/test/sudoku.cxx +++ b/test/sudoku.cxx @@ -135,7 +135,7 @@ class SudokuSound { class SudokuCell : public Fl_Widget { bool readonly_; int value_; - int test_value_[9]; + int marks_; public: @@ -144,13 +144,15 @@ class SudokuCell : public Fl_Widget { int handle(int event) FL_OVERRIDE; void readonly(bool r) { readonly_ = r; redraw(); } bool readonly() const { return readonly_; } - void test_value(int v, int n) { test_value_[n] = v; redraw(); } - int test_value(int n) const { return test_value_[n]; } - void value(int v) { - value_ = v; - for (int i = 0; i < 8; i ++) test_value_[i] = 0; - redraw(); - } + void mark(int n, bool set); + void toggle_mark(int n); + bool mark(int n); + void clear_marks(); + void value(int v) { + value_ = v; + clear_marks(); + redraw(); + } int value() const { return value_; } }; @@ -483,7 +485,9 @@ void SudokuSound::play(char note) { // Create a cell widget SudokuCell::SudokuCell(int X, int Y, int W, int H) - : Fl_Widget(X, Y, W, H, 0) { +: Fl_Widget(X, Y, W, H, 0), + marks_(0) +{ value(0); } @@ -491,15 +495,17 @@ SudokuCell::SudokuCell(int X, int Y, int W, int H) // Draw cell void SudokuCell::draw() { - static Fl_Align align[8] = { + static Fl_Align align[10] = { + 0, FL_ALIGN_TOP_LEFT, FL_ALIGN_TOP, FL_ALIGN_TOP_RIGHT, + FL_ALIGN_LEFT, + 0, FL_ALIGN_RIGHT, - FL_ALIGN_BOTTOM_RIGHT, - FL_ALIGN_BOTTOM, FL_ALIGN_BOTTOM_LEFT, - FL_ALIGN_LEFT + FL_ALIGN_BOTTOM, + FL_ALIGN_BOTTOM_RIGHT, }; @@ -527,11 +533,11 @@ SudokuCell::draw() { fl_draw(s, x(), y(), w(), h(), FL_ALIGN_CENTER); } - fl_font(FL_HELVETICA_BOLD, h() / 5); + fl_font(FL_HELVETICA_BOLD, h()*2/9); - for (int i = 0; i < 8; i ++) { - if (test_value_[i]) { - s[0] = test_value_[i] + '0'; + for (int i = 1; i <= 9; i ++) { + if (mark(i)) { + s[0] = i + '0'; fl_draw(s, x() + 5, y() + 5, w() - 10, h() - 10, align[i]); } } @@ -578,27 +584,8 @@ SudokuCell::handle(int event) { } if (Fl::event_state() & (FL_SHIFT | FL_CAPS_LOCK)) { - int i; - - for (i = 0; i < 8; i ++) - if (test_value_[i] == key) { - test_value_[i] = 0; - break; - } - - if (i >= 8) { - for (i = 0; i < 8; i ++) - if (!test_value_[i]) { - test_value_[i] = key; - break; - } - } - - if (i >= 8) { - for (i = 0; i < 7; i ++) test_value_[i] = test_value_[i + 1]; - test_value_[i] = key; - } - + toggle_mark(key); + value_ = 0; redraw(); } else { value(key); @@ -622,6 +609,29 @@ SudokuCell::handle(int event) { return Fl_Widget::handle(event); } +void SudokuCell::mark(int n, bool set) { + if (n<1 || n>9) return; + if (set) { + marks_ |= (1<<n); + } else { + marks_ &= ~(1<<n); + } +} + +void SudokuCell::toggle_mark(int n) { + if (n<1 || n>9) return; + marks_ ^= (1<<n); +} + +bool SudokuCell::mark(int n) { + if (n<1 || n>9) return 0; + return (marks_>>n) & 1; +} + +void SudokuCell::clear_marks() { + marks_ = 0; +} + // Sudoku class globals... Fl_Help_Dialog *Sudoku::help_dialog_ = (Fl_Help_Dialog *)0; @@ -641,7 +651,7 @@ Sudoku::Sudoku() { "&Check Game", FL_COMMAND | 'c', check_cb, 0, 0 }, { "&Restart Game", FL_COMMAND | 'r', restart_cb, 0, 0 }, { "&Solve Game", FL_COMMAND | 's', solve_cb, 0, FL_MENU_DIVIDER }, - { "&Update Helpers", 0, update_helpers_cb, 0, 0 }, + { "&Update Helpers", FL_COMMAND | 'u', update_helpers_cb, 0, 0 }, { "&Mute Sound", FL_COMMAND | 'm', mute_cb, 0, FL_MENU_TOGGLE | FL_MENU_DIVIDER }, { "&Quit", FL_COMMAND | 'q', close_cb, 0, 0 }, { 0 }, @@ -885,12 +895,12 @@ Sudoku::update_helpers() { int j, k, m; // First we delete any entries that the user may have made + // TODO: set all marks if none were set + // TODO: clear marks if value is used, don't set individual marks for (j = 0; j < 9; j ++) { for (k = 0; k < 9; k ++) { SudokuCell *cell = grid_cells_[j][k]; - for (m = 0; m < 8; m ++) { - cell->test_value(0, m); - } + cell->clear_marks(); } } @@ -925,10 +935,11 @@ Sudoku::update_helpers() { } } // transfer our findings to the markers - for (m = 1, k = 0; m <= 9; m ++) { + for (m = 1; m <= 9; m ++) { if (!taken[m]) - dst_cell->test_value(m, k ++); + dst_cell->mark(m, true); } + dst_cell->redraw(); } } @@ -994,47 +1005,63 @@ Sudoku::help_cb(Fl_Widget *, void *) { // Load the game from saved preferences... void Sudoku::load_game() { +#if 0 + for (int j = 0; j < 9; j ++) { + Fl_Preferences row(prefs_, Fl_Preferences::Name("Row%d", j)); + for (int k = 0; k < 9; k ++) { + Fl_Preferences p(row, Fl_Preferences::Name("Col%d", k)); + char name[255]; + SudokuCell *cell = grid_cells_[j][k]; + p.set("value", grid_values_[j][k]); + p.set("state", cell->value()); + p.set("readonly", cell->readonly()); + for (int m = 1; m <= 9; m ++) { + if (cell->mark(m)) + p.set(Fl_Preferences::Name("m%d", m), 1); + else + p.deleteEntry(Fl_Preferences::Name("m%d", m)); + } + } + } +#endif + // Load the current values and state of each grid... memset(grid_values_, 0, sizeof(grid_values_)); bool solved = true; + bool empty = false; - for (int j = 0; j < 9; j ++) + for (int j = 0; j < 9; j ++) { + Fl_Preferences row(prefs_, Fl_Preferences::Name("Row%d", j)); for (int k = 0; k < 9; k ++) { - char name[255]; - int val; + Fl_Preferences p(row, Fl_Preferences::Name("Col%d", k)); + int v; SudokuCell *cell = grid_cells_[j][k]; - snprintf(name, sizeof(name), "value%d.%d", j, k); - if (!prefs_.get(name, val, 0)) { - j = 9; - grid_values_[0][0] = 0; - break; - } - - grid_values_[j][k] = val; + p.get("value", v, 0); + grid_values_[j][k] = v; + if (v) empty = false; - snprintf(name, sizeof(name), "state%d.%d", j, k); - prefs_.get(name, val, 0); - cell->value(val); + p.get("state", v, 0); + cell->value(v); - snprintf(name, sizeof(name), "readonly%d.%d", j, k); - prefs_.get(name, val, 0); - cell->readonly(val != 0); - - if (val) cell->color(FL_GRAY); - else { + p.set("readonly", cell->readonly()); + cell->readonly(v != 0); + if (v) { + cell->color(FL_GRAY); + } else { cell->color(FL_LIGHT3); solved = false; } - for (int m = 0; m < 8; m ++) { - snprintf(name, sizeof(name), "test%d%d.%d", m, j, k); - prefs_.get(name, val, 0); - cell->test_value(val, m); + for (int m = 1; m <= 9; m ++) { + p.get(Fl_Preferences::Name("m%d", m), v, 0); + cell->mark(m, v); } + cell->redraw(); } + } // If we didn't load any values or the last game was solved, then // create a new game automatically... @@ -1064,19 +1091,50 @@ void Sudoku::new_cb(Fl_Widget *widget, void *) { Sudoku *s = (Sudoku *)(widget->window() ? widget->window() : widget); - if (s->grid_cells_[0][0]->color() != FL_GREEN) { - if (!fl_choice("Are you sure you want to change the difficulty level and " - "discard the current game?", "Keep Current Game", "Start New Game", - NULL)) return; - } +// if (s->grid_cells_[0][0]->color() != FL_GREEN) { +// if (!fl_choice("Are you sure you want to change the difficulty level and " +// "discard the current game?", "Keep Current Game", "Start New Game", +// NULL)) return; +// } s->new_game(time(NULL)); } +extern int generate_sudoku(int grid_data[81]); + // Create a new game... void Sudoku::new_game(time_t seed) { + + { + int grid_data[81]; + int *g = grid_data; + generate_sudoku(grid_data); + SudokuCell *cell; + for (int j = 0; j < 9; j ++) { + for (int k = 0; k < 9; k ++) { + int v = *g++; + int vv = v; if (vv<0) vv = -vv; + grid_values_[j][k] = vv; + cell = grid_cells_[j][k]; + if (v<0) { + cell->value(0); + cell->readonly(0); + cell->color(FL_LIGHT3); + } else { + cell->value(vv); + cell->readonly(1); + cell->color(FL_GRAY); + } + } + } + return; + } + + + + int j, k, m, n, t, count; @@ -1256,25 +1314,23 @@ Sudoku::restart_cb(Fl_Widget *widget, void *) { void Sudoku::save_game() { // Save the current values and state of each grid... - for (int j = 0; j < 9; j ++) + for (int j = 0; j < 9; j ++) { + Fl_Preferences row(prefs_, Fl_Preferences::Name("Row%d", j)); for (int k = 0; k < 9; k ++) { + Fl_Preferences p(row, Fl_Preferences::Name("Col%d", k)); char name[255]; SudokuCell *cell = grid_cells_[j][k]; - - snprintf(name, sizeof(name), "value%d.%d", j, k); - prefs_.set(name, grid_values_[j][k]); - - snprintf(name, sizeof(name), "state%d.%d", j, k); - prefs_.set(name, cell->value()); - - snprintf(name, sizeof(name), "readonly%d.%d", j, k); - prefs_.set(name, cell->readonly()); - - for (int m = 0; m < 8; m ++) { - snprintf(name, sizeof(name), "test%d%d.%d", m, j, k); - prefs_.set(name, cell->test_value(m)); + p.set("value", grid_values_[j][k]); + p.set("state", cell->value()); + p.set("readonly", cell->readonly()); + for (int m = 1; m <= 9; m ++) { + if (cell->mark(m)) + p.set(Fl_Preferences::Name("m%d", m), 1); + else + p.deleteEntry(Fl_Preferences::Name("m%d", m)); } } + } } diff --git a/test/sudoku_generator.cpp b/test/sudoku_generator.cpp new file mode 100644 index 000000000..8f6469e19 --- /dev/null +++ b/test/sudoku_generator.cpp @@ -0,0 +1,590 @@ +// +// 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 <stdio.h> +#include <stdlib.h> +#include <time.h> +#include <FL/Fl_Int_Vector.H> + +#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;i<check;i++) + { + if(empty[i].size() < empty[minIndex].size()) + minIndex = i; + } + + int branchFactor=empty[minIndex].size(); + int rowIndex = empty[minIndex][0]/9; + int colIndex = empty[minIndex][0]%9; + + tempGrid[rowIndex][colIndex] = this->solnGrid[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 |