diff options
Diffstat (limited to 'apps/plugins/puzzles/src/latin.c')
-rw-r--r-- | apps/plugins/puzzles/src/latin.c | 164 |
1 files changed, 30 insertions, 134 deletions
diff --git a/apps/plugins/puzzles/src/latin.c b/apps/plugins/puzzles/src/latin.c index 39930166e7..a2d5713b30 100644 --- a/apps/plugins/puzzles/src/latin.c +++ b/apps/plugins/puzzles/src/latin.c | |||
@@ -563,7 +563,7 @@ void latin_solver_free_scratch(struct latin_solver_scratch *scratch) | |||
563 | sfree(scratch); | 563 | sfree(scratch); |
564 | } | 564 | } |
565 | 565 | ||
566 | void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o) | 566 | bool latin_solver_alloc(struct latin_solver *solver, digit *grid, int o) |
567 | { | 567 | { |
568 | int x, y; | 568 | int x, y; |
569 | 569 | ||
@@ -577,14 +577,23 @@ void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o) | |||
577 | memset(solver->row, 0, o*o); | 577 | memset(solver->row, 0, o*o); |
578 | memset(solver->col, 0, o*o); | 578 | memset(solver->col, 0, o*o); |
579 | 579 | ||
580 | for (x = 0; x < o; x++) | ||
581 | for (y = 0; y < o; y++) | ||
582 | if (grid[y*o+x]) | ||
583 | latin_solver_place(solver, x, y, grid[y*o+x]); | ||
584 | |||
585 | #ifdef STANDALONE_SOLVER | 580 | #ifdef STANDALONE_SOLVER |
586 | solver->names = NULL; | 581 | solver->names = NULL; |
587 | #endif | 582 | #endif |
583 | |||
584 | for (x = 0; x < o; x++) { | ||
585 | for (y = 0; y < o; y++) { | ||
586 | int n = grid[y*o+x]; | ||
587 | if (n) { | ||
588 | if (cube(x, y, n)) | ||
589 | latin_solver_place(solver, x, y, n); | ||
590 | else | ||
591 | return false; /* puzzle is already inconsistent */ | ||
592 | } | ||
593 | } | ||
594 | } | ||
595 | |||
596 | return true; | ||
588 | } | 597 | } |
589 | 598 | ||
590 | void latin_solver_free(struct latin_solver *solver) | 599 | void latin_solver_free(struct latin_solver *solver) |
@@ -810,15 +819,17 @@ static int latin_solver_recurse | |||
810 | } else { | 819 | } else { |
811 | newctx = ctx; | 820 | newctx = ctx; |
812 | } | 821 | } |
813 | latin_solver_alloc(&subsolver, outgrid, o); | ||
814 | #ifdef STANDALONE_SOLVER | 822 | #ifdef STANDALONE_SOLVER |
815 | subsolver.names = solver->names; | 823 | subsolver.names = solver->names; |
816 | #endif | 824 | #endif |
817 | ret = latin_solver_top(&subsolver, diff_recursive, | 825 | if (latin_solver_alloc(&subsolver, outgrid, o)) |
818 | diff_simple, diff_set_0, diff_set_1, | 826 | ret = latin_solver_top(&subsolver, diff_recursive, |
819 | diff_forcing, diff_recursive, | 827 | diff_simple, diff_set_0, diff_set_1, |
820 | usersolvers, valid, newctx, | 828 | diff_forcing, diff_recursive, |
821 | ctxnew, ctxfree); | 829 | usersolvers, valid, newctx, |
830 | ctxnew, ctxfree); | ||
831 | else | ||
832 | ret = diff_impossible; | ||
822 | latin_solver_free(&subsolver); | 833 | latin_solver_free(&subsolver); |
823 | if (ctxnew) | 834 | if (ctxnew) |
824 | ctxfree(newctx); | 835 | ctxfree(newctx); |
@@ -1059,11 +1070,13 @@ int latin_solver(digit *grid, int o, int maxdiff, | |||
1059 | struct latin_solver solver; | 1070 | struct latin_solver solver; |
1060 | int diff; | 1071 | int diff; |
1061 | 1072 | ||
1062 | latin_solver_alloc(&solver, grid, o); | 1073 | if (latin_solver_alloc(&solver, grid, o)) |
1063 | diff = latin_solver_main(&solver, maxdiff, | 1074 | diff = latin_solver_main(&solver, maxdiff, |
1064 | diff_simple, diff_set_0, diff_set_1, | 1075 | diff_simple, diff_set_0, diff_set_1, |
1065 | diff_forcing, diff_recursive, | 1076 | diff_forcing, diff_recursive, |
1066 | usersolvers, valid, ctx, ctxnew, ctxfree); | 1077 | usersolvers, valid, ctx, ctxnew, ctxfree); |
1078 | else | ||
1079 | diff = diff_impossible; | ||
1067 | latin_solver_free(&solver); | 1080 | latin_solver_free(&solver); |
1068 | return diff; | 1081 | return diff; |
1069 | } | 1082 | } |
@@ -1298,121 +1311,4 @@ bool latin_check(digit *sq, int order) | |||
1298 | return ret; | 1311 | return ret; |
1299 | } | 1312 | } |
1300 | 1313 | ||
1301 | |||
1302 | /* -------------------------------------------------------- | ||
1303 | * Testing (and printing). | ||
1304 | */ | ||
1305 | |||
1306 | #ifdef STANDALONE_LATIN_TEST | ||
1307 | |||
1308 | #include <stdio.h> | ||
1309 | #include <time.h> | ||
1310 | |||
1311 | const char *quis; | ||
1312 | |||
1313 | static void latin_print(digit *sq, int order) | ||
1314 | { | ||
1315 | int x, y; | ||
1316 | |||
1317 | for (y = 0; y < order; y++) { | ||
1318 | for (x = 0; x < order; x++) { | ||
1319 | printf("%2u ", ELT(sq, x, y)); | ||
1320 | } | ||
1321 | printf("\n"); | ||
1322 | } | ||
1323 | printf("\n"); | ||
1324 | } | ||
1325 | |||
1326 | static void gen(int order, random_state *rs, int debug) | ||
1327 | { | ||
1328 | digit *sq; | ||
1329 | |||
1330 | solver_show_working = debug; | ||
1331 | |||
1332 | sq = latin_generate(order, rs); | ||
1333 | latin_print(sq, order); | ||
1334 | if (latin_check(sq, order)) { | ||
1335 | fprintf(stderr, "Square is not a latin square!"); | ||
1336 | exit(1); | ||
1337 | } | ||
1338 | |||
1339 | sfree(sq); | ||
1340 | } | ||
1341 | |||
1342 | void test_soak(int order, random_state *rs) | ||
1343 | { | ||
1344 | digit *sq; | ||
1345 | int n = 0; | ||
1346 | time_t tt_start, tt_now, tt_last; | ||
1347 | |||
1348 | solver_show_working = 0; | ||
1349 | tt_now = tt_start = time(NULL); | ||
1350 | |||
1351 | while(1) { | ||
1352 | sq = latin_generate(order, rs); | ||
1353 | sfree(sq); | ||
1354 | n++; | ||
1355 | |||
1356 | tt_last = time(NULL); | ||
1357 | if (tt_last > tt_now) { | ||
1358 | tt_now = tt_last; | ||
1359 | printf("%d total, %3.1f/s\n", n, | ||
1360 | (double)n / (double)(tt_now - tt_start)); | ||
1361 | } | ||
1362 | } | ||
1363 | } | ||
1364 | |||
1365 | void usage_exit(const char *msg) | ||
1366 | { | ||
1367 | if (msg) | ||
1368 | fprintf(stderr, "%s: %s\n", quis, msg); | ||
1369 | fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis); | ||
1370 | exit(1); | ||
1371 | } | ||
1372 | |||
1373 | int main(int argc, char *argv[]) | ||
1374 | { | ||
1375 | int i, soak = 0; | ||
1376 | random_state *rs; | ||
1377 | time_t seed = time(NULL); | ||
1378 | |||
1379 | quis = argv[0]; | ||
1380 | while (--argc > 0) { | ||
1381 | const char *p = *++argv; | ||
1382 | if (!strcmp(p, "--soak")) | ||
1383 | soak = 1; | ||
1384 | else if (!strcmp(p, "--seed")) { | ||
1385 | if (argc == 0) | ||
1386 | usage_exit("--seed needs an argument"); | ||
1387 | seed = (time_t)atoi(*++argv); | ||
1388 | argc--; | ||
1389 | } else if (*p == '-') | ||
1390 | usage_exit("unrecognised option"); | ||
1391 | else | ||
1392 | break; /* finished options */ | ||
1393 | } | ||
1394 | |||
1395 | rs = random_new((void*)&seed, sizeof(time_t)); | ||
1396 | |||
1397 | if (soak == 1) { | ||
1398 | if (argc != 1) usage_exit("only one argument for --soak"); | ||
1399 | test_soak(atoi(*argv), rs); | ||
1400 | } else { | ||
1401 | if (argc > 0) { | ||
1402 | for (i = 0; i < argc; i++) { | ||
1403 | gen(atoi(*argv++), rs, 1); | ||
1404 | } | ||
1405 | } else { | ||
1406 | while (1) { | ||
1407 | i = random_upto(rs, 20) + 1; | ||
1408 | gen(i, rs, 0); | ||
1409 | } | ||
1410 | } | ||
1411 | } | ||
1412 | random_free(rs); | ||
1413 | return 0; | ||
1414 | } | ||
1415 | |||
1416 | #endif | ||
1417 | |||
1418 | /* vim: set shiftwidth=4 tabstop=8: */ | 1314 | /* vim: set shiftwidth=4 tabstop=8: */ |