| 1 | #* Copyright (C) 2008 Christian Guine | ||
| 2 | # * This program is free software; you can redistribute it and/or modify it | ||
| 3 | # * under the terms of the GNU General Public License as published by the Free | ||
| 4 | # * Software Fondation; either version 2 of the License, or (at your option) | ||
| 5 | # * any later version. | ||
| 6 | # * This program is distributed in the hope that it will be useful, but WITHOUT | ||
| 7 | # * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | ||
| 8 | # * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for | ||
| 9 | # * more details. | ||
| 10 | # * You should have received a copy of the GNU General Public License along with | ||
| 11 | # * this program; if not, write to the Free Software Foundation, Inc., 59 | ||
| 12 | # * Temple Place - Suite 330, Boston, MA 02111-1307, USA. | ||
| 13 | # */ | ||
| 14 | # newgrille.pm design of a new grid | ||
| 15 | # voir lorsqu on a trouve une case blanche si on se repositionne tout de suite | ||
| 16 | sub newgrille { | ||
| 17 | use Games::Sudoku::sudokuprincipal; | ||
| 18 | use Games::Sudoku::affichgrille; | ||
| 19 | use Games::Sudoku::conf; | ||
| 20 | conf(); | ||
| 21 | if ($wcanvas == 1) { # delete Label of beginning | ||
| 22 | $canvas -> destroy; | ||
| 23 | $framed -> destroy; | ||
| 24 | $wcanvas = 0; | ||
| 25 | $frame1 = $main->Frame; | ||
| 26 | $frame1->pack; | ||
| 27 | } | ||
| 28 | $trait = "N"; | ||
| 29 | $oldwcpt = 0; | ||
| 30 | $fin = 0; | ||
| 31 | $force = 0; | ||
| 32 | BOUCLE:while ($fin == 0 and $force == 0) { # loop as much as a solution was not found | ||
| 33 | # where all is found | ||
| 34 | print "debut boucle\n"; | ||
| 35 | init_tableau(); # initialization table | ||
| 36 | $fin = 0; | ||
| 37 | $cpt = 0; | ||
| 38 | $wcpt2 = 0; | ||
| 39 | $toploop = 0; | ||
| 40 | $cptpris = 0; | ||
| 41 | $cptblanc = 0; | ||
| 42 | $cptlibre = 0; | ||
| 43 | $nbreposit = 0; | ||
| 44 | $cptcaseblanche = 0; | ||
| 45 | $restauresolution = 0; | ||
| 46 | $wsi = 0; | ||
| 47 | $wsj = 0; | ||
| 48 | $wsk = 0; | ||
| 49 | $wwsi = 0; | ||
| 50 | $wwsj = 0; | ||
| 51 | $wwsk = 0; | ||
| 52 | $wtoploop = 0; | ||
| 53 | $ic = 0; | ||
| 54 | $jc = 0; | ||
| 55 | $kc = 0; | ||
| 56 | $aic = 0; # init index for "affect" | ||
| 57 | $ajc = 0; | ||
| 58 | $akc = -1; | ||
| 59 | $affect = 0; | ||
| 60 | if ($nbcase == 16) { | ||
| 61 | $cptloop = 10000; | ||
| 62 | } else { | ||
| 63 | $cptloop = 500; | ||
| 64 | } | ||
| 65 | LOOP:while (($fin == 0) and ($cpt < $cptloop) | ||
| 66 | and ($toploop < 150)) { #loop for filling the grid | ||
| 67 | #$topcase = 5; # debug | ||
| 68 | #cherche_case_blanche1(); | ||
| 69 | $cpt++; | ||
| 70 | $wcpt2++; | ||
| 71 | $topreplace = 0; | ||
| 72 | if ($wcpt2 > 2000) { | ||
| 73 | comptageOK(); | ||
| 74 | if (($nbcase != 6 and $nbcase != 8 and $nbcase != 9 and $nbcase != 4) # pour debug à enlever | ||
| 75 | and $toploop > 1) { # pour debug à enlever | ||
| 76 | $force = 1; # pour debug à enlever | ||
| 77 | last; # pour debug à enlever | ||
| 78 | } # pour debug à enlever | ||
| 79 | print ("Reprise comptage\n"); | ||
| 80 | $wcpt2 = 0; | ||
| 81 | } | ||
| 82 | #$topcase = 7; # debug | ||
| 83 | #cherche_case_blanche1(); | ||
| 84 | # random search of a number | ||
| 85 | if ($wtoploop == 1) { | ||
| 86 | if ($wsi == $wwsi and $wsj == $wwsj and $wsk == $wwsk) { # we verifie | ||
| 87 | #that all possibilities | ||
| 88 | # are explored | ||
| 89 | print ("Tout est pris arret\n"); | ||
| 90 | $fin = 0; | ||
| 91 | $force = 1; # change force = 0 for no stopping | ||
| 92 | last; | ||
| 93 | } | ||
| 94 | $wwsi = $wsi; | ||
| 95 | $wwsj = $wsj; | ||
| 96 | $wwsk = $wsk; | ||
| 97 | $i = $wsi; | ||
| 98 | $j = $wsj; | ||
| 99 | $k = $wsk; | ||
| 100 | $wtoploop = 0; | ||
| 101 | $topreplace = 1; | ||
| 102 | $nbreposit++; | ||
| 103 | print "ligne= " . ($i + 1) . " colonne= " . ($j + 1) . " valeur= " | ||
| 104 | . ($k + 1) . " cpt= " . $cpt . " toploop= " . $toploop . " cptlibre= " | ||
| 105 | . $cptlibre . "\n"; | ||
| 106 | } else { | ||
| 107 | if ($cpt < 300) { | ||
| 108 | #print("rand"); | ||
| 109 | $i = int(rand($nbcase)); | ||
| 110 | $j = int(rand($nbcase)); | ||
| 111 | $k = int(rand($nbcase)); | ||
| 112 | } else { | ||
| 113 | print "affect1"; | ||
| 114 | affect(); | ||
| 115 | if ($cpt > 800) { | ||
| 116 | print ("arret cpt > 800\n"); | ||
| 117 | $restauresolution = 1; # restaure solution | ||
| 118 | $force = 1; | ||
| 119 | } | ||
| 120 | } | ||
| 121 | } | ||
| 122 | #print "ligne= " . ($i + 1) . " colonne= " . ($j + 1) . " valeur= " . ($k + 1) | ||
| 123 | # . " cpt= " . $cpt . "\n"; | ||
| 124 | $caseblanche = 0; | ||
| 125 | #$topcase = 9; # debug | ||
| 126 | #cherche_case_blanche1(); | ||
| 127 | if ($precarre[$i][$j][$k] ne "P") { | ||
| 128 | $cpt--; | ||
| 129 | $wcpt2--; | ||
| 130 | if ($topreplace == 1) { | ||
| 131 | print ("deja pris"); | ||
| 132 | } | ||
| 133 | print "KO$i$j$k"; | ||
| 134 | $cptpris++; | ||
| 135 | #$topcase = 8; # debug | ||
| 136 | #cherche_case_blanche1(); | ||
| 137 | next LOOP; | ||
| 138 | } | ||
| 139 | print "OK$i$j$k"; | ||
| 140 | #$topcase = 10; # debug | ||
| 141 | #cherche_case_blanche1(); | ||
| 142 | $#wprecarre = -1; | ||
| 143 | # save before checking correct choice | ||
| 144 | for (my $wi = 0; $wi < $nbcase; $wi++) { | ||
| 145 | for (my $wj = 0; $wj < $nbcase; $wj++) { | ||
| 146 | for (my $wk = 0; $wk < $nbcase; $wk++) { | ||
| 147 | $wprecarre[$wi][$wj][$wk] = $precarre[$wi][$wj][$wk]; | ||
| 148 | } | ||
| 149 | #cherche_case_blanche1(); # debug | ||
| 150 | } | ||
| 151 | } | ||
| 152 | #$topcase = 1; # debug | ||
| 153 | #cherche_case_blanche1(); # debug | ||
| 154 | # we cancel the other possibility on line column and area | ||
| 155 | $precarre[$i][$j][$k] = "S"; | ||
| 156 | $trait = "N"; | ||
| 157 | $ligne = $i; | ||
| 158 | $colonne = $j; | ||
| 159 | $valeur = $k; | ||
| 160 | $entree = "S"; | ||
| 161 | $endroit = ""; | ||
| 162 | $topcase = 11; | ||
| 163 | modif_tableau(); | ||
| 164 | $topcase = 30; | ||
| 165 | # it is checked that there is no completely cancelled square | ||
| 166 | cherche_case_blanche1(); | ||
| 167 | $final = 0; | ||
| 168 | solution(); # we are checking that all is found | ||
| 169 | $caseblanche = 0; | ||
| 170 | cherche_case_blanche1(); | ||
| 171 | verifnbcase(); | ||
| 172 | exportation(); | ||
| 173 | $topcase = 4; #debug | ||
| 174 | cherche_case_blanche1(); | ||
| 175 | } | ||
| 176 | # it is checked that all is filled | ||
| 177 | #$fin = 1; # we stop more we go on | ||
| 178 | $fin = 1; # put in zero not to stop any more | ||
| 179 | $cpt1 = 0; | ||
| 180 | for (my $wi = 0; $wi < $nbcase; $wi++) { | ||
| 181 | for (my $wj = 0; $wj < $nbcase; $wj++) { | ||
| 182 | $trouve = 0; | ||
| 183 | for (my $wk = 0; $wk < $nbcase; $wk++) { | ||
| 184 | if ($precarre[$wi][$wj][$wk] ne " " | ||
| 185 | and $precarre[$wi][$wj][$wk] ne "P") { | ||
| 186 | $trouve = 1; | ||
| 187 | if ($precarre[$wi][$wj][$wk] eq "S") { | ||
| 188 | $cpt1++; | ||
| 189 | } | ||
| 190 | } | ||
| 191 | } | ||
| 192 | if ($trouve == 0) { | ||
| 193 | $fin = 0; # we start again | ||
| 194 | } | ||
| 195 | } | ||
| 196 | } | ||
| 197 | $topcase = 11; # debug | ||
| 198 | cherche_case_blanche1(); | ||
| 199 | print "fin cpt1= " . $cpt1 . " fin= " . $fin . " toploop= " . $toploop . "\n"; | ||
| 200 | } | ||
| 201 | #$traitexport = "S"; | ||
| 202 | #exportation(); # save the solution | ||
| 203 | # Preparation grid for posting | ||
| 204 | for (my $wi = 0; $wi < $nbcase; $wi++) { | ||
| 205 | for (my $wj = 0; $wj < $nbcase; $wj++) { | ||
| 206 | $trouve = 0; | ||
| 207 | # Is it a seizure in the square? | ||
| 208 | for (my $wk1 = 0; $wk1 < $nbcase; $wk1++) { | ||
| 209 | if ($precarre[$wi][$wj][$wk1] eq "S") { | ||
| 210 | $trouve = 1; | ||
| 211 | last; | ||
| 212 | } | ||
| 213 | } | ||
| 214 | for (my $wk = 0; $wk < $nbcase; $wk++) { | ||
| 215 | if ($precarre[$wi][$wj][$wk] ne "S") { | ||
| 216 | if ($trouve == 0) { # if we find a seizure | ||
| 217 | $precarre[$wi][$wj][$wk] = "P"; | ||
| 218 | } else { | ||
| 219 | $precarre[$wi][$wj][$wk] = " "; | ||
| 220 | } | ||
| 221 | } | ||
| 222 | } | ||
| 223 | } | ||
| 224 | } | ||
| 225 | #$topcase = 6; # debug | ||
| 226 | #cherche_case_blanche1(); | ||
| 227 | # Elimination of impossible combinations | ||
| 228 | for (my $wi = 0; $wi < $nbcase; $wi++) { | ||
| 229 | for (my $wj = 0; $wj < $nbcase; $wj++) { | ||
| 230 | $trouve = 0; | ||
| 231 | for (my $wk = 0; $wk < $nbcase; $wk++) { | ||
| 232 | if ($precarre[$wi][$wj][$wk] eq "S") { | ||
| 233 | $entree = "S"; | ||
| 234 | $ligne = $wi; | ||
| 235 | $colonne = $wj; | ||
| 236 | $valeur = $wk; | ||
| 237 | $endroit = ""; | ||
| 238 | $topcase = 12; | ||
| 239 | modif_tableau($entree); | ||
| 240 | } | ||
| 241 | } | ||
| 242 | } | ||
| 243 | } | ||
| 244 | restaure_solution(); | ||
| 245 | $fin = 0; | ||
| 246 | $traitexport = " "; | ||
| 247 | exportation(); | ||
| 248 | $traitexport = "S"; | ||
| 249 | exportation(); # save the solution | ||
| 250 | retour_arriere(); # abolition no one or two seizures according to difficulty | ||
| 251 | $traitexport = " "; | ||
| 252 | exportation(); | ||
| 253 | affichage_grille('V'); | ||
| 254 | $timedebut = time; | ||
| 255 | fin_saisie(); | ||
| 256 | if ($nbcase == 16 and $affect == 0) { # sauvegarde solutions | ||
| 257 | if ($system eq "linux") { | ||
| 258 | #my $t = time; | ||
| 259 | my @tab = ("cp", "sudoku16.txt", "sudoku16$t.txt"); # sauvegarde | ||
| 260 | system @tab; | ||
| 261 | @tab = ("cp", "sudokus16.txt", "sudokus16$t.txt"); | ||
| 262 | system @tab; | ||
| 263 | } | ||
| 264 | } | ||
| 265 | if (defined($fabrication) and $fabrication == 1) { # sauvegarde solutions | ||
| 266 | newgrille(); | ||
| 267 | } | ||
| 268 | } | ||
| 269 | 1; | ||
| 270 | |||
| 271 | sub comptageOK { | ||
| 272 | $wcpt3 = 0; | ||
| 273 | my $n1cpt = 0; | ||
| 274 | $cptlibre = 0; | ||
| 275 | $wcptstock = 0; | ||
| 276 | for (my $wi = 0; $wi < $nbcase; $wi++) { | ||
| 277 | for (my $wj = 0; $wj < $nbcase; $wj++) { | ||
| 278 | for (my $wk = 0; $wk < $nbcase; $wk++) { | ||
| 279 | if ($precarre[$wi][$wj][$wk] eq "S" or $precarre[$wi][$wj][$wk] eq "C") | ||
| 280 | { | ||
| 281 | $wcpt3++; | ||
| 282 | } elsif ($precarre[$wi][$wj][$wk] eq "P") { | ||
| 283 | if (($wsi < $wi or | ||
| 284 | ($wsi == $wi and $wsj < $wj) or | ||
| 285 | ($wsi == $wi and $wsj == $wj and $wsk < $wk)) | ||
| 286 | and $wcptstock == 0) { | ||
| 287 | $n1cpt++; | ||
| 288 | if ($n1cpt >= $nbreposit) { # having so already | ||
| 289 | #re-positioned them ask | ||
| 290 | #for following free position | ||
| 291 | $wsi = $wi; | ||
| 292 | $wsj = $wj; | ||
| 293 | $wsk = $wk; | ||
| 294 | $wcptstock = 1; | ||
| 295 | #print ("stock1 wi= " . $wi . " wj= " . $wj . | ||
| 296 | # " wk= " . $wk . "\n"); | ||
| 297 | } | ||
| 298 | } | ||
| 299 | $cptlibre++; | ||
| 300 | } | ||
| 301 | } | ||
| 302 | } | ||
| 303 | } | ||
| 304 | #print "comptage" . $wcpt3 . " fin= " . $fin . " cpt= " . $cpt . " cptloop= " . $cptloop . | ||
| 305 | # " toploop= " . $toploop . " cptpris= " . $cptpris . " cptblanc= " . $cptblanc . "\n"; | ||
| 306 | $wtoploop = 0; | ||
| 307 | if ($wcpt3 == $oldwcpt) { | ||
| 308 | $toploop++; # we stop the loop if the number of thrue squares is not greater | ||
| 309 | $wtoploop = 1; | ||
| 310 | } | ||
| 311 | $cptpris = 0; | ||
| 312 | $cptblanc = 0; | ||
| 313 | $oldwcpt = $wcpt3; | ||
| 314 | } | ||
| 315 | |||
| 316 | sub affect { # allocation square free since the beginning | ||
| 317 | for ($aic = $aic; $aic < $nbcase; $aic ++) { | ||
| 318 | for ($ajc = $ajc; $ajc < $nbcase; $ajc++) { | ||
| 319 | for ($akc = $akc + 1; $akc < $nbcase; $akc++) { | ||
| 320 | if ($precarre[$aic][$ajc][$akc] eq "P") { | ||
| 321 | $i = $aic; | ||
| 322 | $j = $ajc; | ||
| 323 | $k = $akc; | ||
| 324 | print ("affect " . $aic . "," . $ajc . "," . $akc . "\n"); | ||
| 325 | last; | ||
| 326 | } | ||
| 327 | } | ||
| 328 | if ($precarre[$aic][$ajc][$akc] eq "P") { | ||
| 329 | last; | ||
| 330 | } else { | ||
| 331 | $akc = -1; | ||
| 332 | } | ||
| 333 | } | ||
| 334 | if ($precarre[$aic][$ajc][$akc] eq "P") { | ||
| 335 | last; | ||
| 336 | } else { | ||
| 337 | $ajc = 0; | ||
| 338 | } | ||
| 339 | } | ||
| 340 | print("affect i= " . $i . " j = " . $j . " k = " . $k . " nbcases " . $nbcase . "\n"); | ||
| 341 | if ($aic == ($nbcase)) { | ||
| 342 | print("tout a ete examine \n"); | ||
| 343 | $fin = 1; | ||
| 344 | $affect = 1; # supprimer si pas de recherche solution | ||
| 345 | } | ||
| 346 | } | ||
| 347 | |||
| 348 | sub cherche_case_blanche1 { | ||
| 349 | $caseblanche = 0; | ||
| 350 | cherche_case_blanche(); | ||
| 351 | if ($caseblanche == 1) { | ||
| 352 | print ("Restauration2 topcase = $topcase\n"); | ||
| 353 | $#precarre = -1; | ||
| 354 | for ($wi = 0; $wi < $nbcase; $wi++) { | ||
| 355 | for ($wj = 0; $wj < $nbcase; $wj++) { | ||
| 356 | for ($wk = 0; $wk < $nbcase; $wk++) { | ||
| 357 | $precarre[$wi][$wj][$wk] = | ||
| 358 | $wprecarre[$wi][$wj][$wk]; | ||
| 359 | } | ||
| 360 | } | ||
| 361 | } | ||
| 362 | } | ||
| 363 | } | ||
| 364 | |||
| 365 | sub verifnbcase { | ||
| 366 | # Check that in an area the number of squares determined | ||
| 367 | # + the possible number of squares is equal to nbcase | ||
| 368 | # otherwise restoration | ||
| 369 | #print ("verifnbcase\n"); | ||
| 370 | $wimin = 0; | ||
| 371 | $wjmin = 0; | ||
| 372 | $restaur = 0; | ||
| 373 | if ($nbcase == 9) { | ||
| 374 | $plusi = 3; | ||
| 375 | $plusj = 3; | ||
| 376 | } elsif ($nbcase == 4) { | ||
| 377 | $plusi = 2; | ||
| 378 | $plusj = 2; | ||
| 379 | } elsif ($nbcase == 6) { | ||
| 380 | $plusi = 2; | ||
| 381 | $plusj = 3; | ||
| 382 | } elsif ($nbcase == 8) { | ||
| 383 | $plusi = 2; | ||
| 384 | $plusj = 4; | ||
| 385 | } elsif ($nbcase == 10) { | ||
| 386 | $plusi = 2; | ||
| 387 | $plusj = 5; | ||
| 388 | } elsif ($nbcase == 12) { | ||
| 389 | $plusi = 3; | ||
| 390 | $plusj = 4; | ||
| 391 | } else { | ||
| 392 | $plusi = 4; | ||
| 393 | $plusj = 4; | ||
| 394 | } | ||
| 395 | for ($ligne = 0; $ligne < $nbcase; $ligne = $ligne + $plusi) { | ||
| 396 | for ($colonne = 0; $colonne < $nbcase; $colonne = $colonne + $plusj) { | ||
| 397 | ($wimin, $wimax, $wjmin, $wjmax) = calminmax($nbcase, $ligne, $colonne); | ||
| 398 | # counting numbers possible squares in an area | ||
| 399 | $wcpt1 = 0; | ||
| 400 | $#area = -1; | ||
| 401 | if ($nbcase == 4) { | ||
| 402 | @area = (0,0,0,0); | ||
| 403 | } elsif ($nbcase == 6) { | ||
| 404 | @area = (0,0,0,0,0,0); | ||
| 405 | } elsif ($nbcase == 8) { | ||
| 406 | @area = (0,0,0,0,0,0,0,0); | ||
| 407 | } elsif ($nbcase == 9) { | ||
| 408 | @area = (0,0,0,0,0,0,0,0,0); | ||
| 409 | } elsif ($nbcase == 10) { | ||
| 410 | @area = (0,0,0,0,0,0,0,0,0,0); | ||
| 411 | } elsif ($nbcase == 12) { | ||
| 412 | @area = (0,0,0,0,0,0,0,0,0,0,0,0); | ||
| 413 | } else { | ||
| 414 | @area = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0); | ||
| 415 | } | ||
| 416 | for ($wim = $wimin; $wim < $wimax; $wim++) { | ||
| 417 | for ($wjm = $wjmin; $wjm < $wjmax; $wjm++) { | ||
| 418 | for ($wkm = 0; $wkm < $nbcase; $wkm++) { | ||
| 419 | if ($precarre[$wim][$wjm][$wkm] ne " ") { | ||
| 420 | $area[$wkm] = 1; | ||
| 421 | } | ||
| 422 | } | ||
| 423 | } | ||
| 424 | } | ||
| 425 | for ($iarea = 0; $iarea < $nbcase; $iarea++) { | ||
| 426 | $wcpt1 = $wcpt1 + $area[$iarea]; | ||
| 427 | } | ||
| 428 | if ($wcpt1 != $nbcase) { #impossible solution we backup | ||
| 429 | print ("\nverifnbcase $wimin $wjmin $wcpt1 restaure\n"); | ||
| 430 | $#precarre = -1; | ||
| 431 | for ($wim = 0; $wim < $nbcase; $wim++) { | ||
| 432 | for ($wjm = 0; $wjm < $nbcase; $wjm++) { | ||
| 433 | for ($wkm = 0; $wkm < $nbcase; $wkm++) { | ||
| 434 | $precarre[$wim][$wjm][$wkm] = | ||
| 435 | $wprecarre[$wim][$wjm][$wkm]; | ||
| 436 | } | ||
| 437 | } | ||
| 438 | } | ||
| 439 | } | ||
| 440 | } | ||
| 441 | } | ||
| 442 | } | ||
| 443 | |||
| 444 | sub restaure_solution { | ||
| 445 | use Games::Sudoku::conf; | ||
| 446 | use Games::Sudoku::sudokuprincipal; | ||
| 447 | conf(); | ||
| 448 | # we choose a solution | ||
| 449 | if ($restauresolution == 1 and $nbcase == 16) { | ||
| 450 | my $i = int(rand($nbsolution)); | ||
| 451 | importation("","sav$i"); | ||
| 452 | print ("restaure_solution sav$i\n"); | ||
| 453 | } | ||
| 454 | } |