path: root/tools/sudoku_generator.cpp

/*
 * Sudoku: A plug-in for the Video Disk Recorder
 *
 * Copyright (C) 2005-2010, Thomas Günther <tom@toms-cafe.de>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#include "../puzzle.h"
#include "../solver.h"
#include "../generator.h"
#include <stdio.h>
#include <string.h>
#include <getopt.h>

using namespace Sudoku;


int print_version()
{
  printf("sudoku_generator %s\n"
         "Copyright (C) 2005-2010, Thomas Günther <tom@toms-cafe.de>\n"
         "This GPL program comes with ABSOLUTELY NO WARRANTY;\n"
         "this is free software, and you are welcome to redistribute it\n"
         "under certain conditions; see the source for details.\n", VERSION);
  return 0;
}

void print_description(unsigned int givens_count)
{
  printf("Sudoku with %d givens generated by sudoku_generator %s\n"
         "    This puzzle can be used without any limitations.\n"
         "\n", givens_count, VERSION);
}

int print_usage()
{
  printf("Usage: sudoku_generator [-n|--non-sym] [-d|--dump] [<givens_count>]\n"
         "         Generate a Sudoku puzzle.\n"
         "           givens_count   Number of givens (<= 81). Default is 36.\n"
         "                          Less than 26 givens takes very long.\n"
         "           -n, --non-sym  Generate a non-symmetric Sudoku puzzle.\n"
         "           -d, --dump     Dump the generated Sudoku (don't print).\n"
         "\n"
         "       sudoku_generator -s|--solve <sudoku_dump>\n"
         "         Solve a Sudoku puzzle.\n"
         "           sudoku_dump    String with 81 * 1-9 or _ (+ ignored).\n"
         "\n"
         "       sudoku_generator -p|--print <sudoku_dump>\n"
         "         Print a Sudoku puzzle.\n"
         "           sudoku_dump    String with 81 * 1-9 or _ (+ ignored).\n"
         "\n"
#ifdef WITH_TEST
         "       sudoku_generator -t|--test\n"
         "         Perform some test procedures.\n"
         "\n"
#endif
         "       sudoku_generator -v|--version\n"
         "         Print version information and exit.\n"
         "\n"
         "       sudoku_generator -h|--help\n"
         "         Print this help message and exit.\n"
         "\n");
  return 2;
}

void print_sudoku(const Numbers* sudoku_list[], unsigned int count,
                  unsigned int givens_count = 0)
{
  printf("\n");
  for (unsigned int row = 0; row <= DIM; ++row)
  {
    if (row % RDIM == 0)
    {
      for (unsigned int idx = 0; idx < count; ++idx)
      {
        printf("              ");
        for (unsigned int col = 0; col < DIM; ++col)
        {
          if (col % RDIM == 0)
            printf("  ");
          printf("- ");
        }
        printf("  ");
      }
      printf("\n");
    }
    if (row < DIM)
    {
      for (unsigned int idx = 0; idx < count; ++idx)
      {
        printf("              ");
        for (unsigned int col = 0; col < DIM; ++col)
        {
          if (col % RDIM == 0)
            printf("| ");
          unsigned int n = sudoku_list[idx]->get(Pos(col, row));
          if (n)
            printf("%d ", n);
          else
            printf("  ");
        }
        printf("| ");
      }
      printf("\n");
    }
  }
  printf("\n");
  if (givens_count != 0)
    print_description(givens_count);
}

void print_sudoku(const Numbers& sudoku, unsigned int givens_count = 0)
{
  const Numbers* sudoku_list[] = { &sudoku };
  print_sudoku(sudoku_list, 1, givens_count);
}

void print_sudoku(const Numbers& sudoku1, const Numbers& sudoku2,
                  unsigned int givens_count = 0)
{
  const Numbers* sudoku_list[] = { &sudoku1, &sudoku2 };
  print_sudoku(sudoku_list, 2, givens_count);
}

void dump_sudoku(const Numbers& sudoku)
{
  printf("%s\n", sudoku.get_dump());
}

int generate_puzzle(unsigned int givens_count, bool non_sym, bool dump)
{
  Puzzle puzzle;
  Generator generator(puzzle, givens_count, !non_sym);
  generator.find_next_solution();
  if (!generator.solution_is_valid())
    return 1;
  if (dump)
    dump_sudoku(puzzle);
  else
    print_sudoku(puzzle, givens_count);
  return 0;
}

int solve_puzzle(const char *dump)
{
  Numbers numbers(dump);
  bool given_marks[SDIM];
  for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
    given_marks[p] = numbers.get(p) != 0;
  Puzzle puzzle;
  puzzle.set_givens(numbers, given_marks);
  Solver solver(puzzle);
  solver.find_next_solution();
  if (!solver.solution_is_valid())
    return 1;
  print_sudoku(numbers, puzzle);
  solver.find_next_solution();
  if (!solver.solution_is_valid())
    return 0;
  printf("Error: Sudoku has more than one solution!\n");
  return 1;
}

int print_puzzle(const char *dump)
{
  Numbers numbers(dump);
  print_sudoku(numbers);
  return 0;
}

#ifdef WITH_TEST
bool test_search_first()
{
  bool correct = true;
  printf("Search the first Sudoku!\n");
  Puzzle puzzle;
  Solver solver(puzzle);
  solver.find_next_solution();
  if (solver.solution_is_valid())
    print_sudoku(puzzle);
  else
    correct = false, printf("Error: Sudoku is invalid!\n");
  printf("Search the second Sudoku!\n");
  solver.find_next_solution();
  if (solver.solution_is_valid())
    print_sudoku(puzzle);
  else
    correct = false, printf("Error: Sudoku is invalid!\n");
  return correct;
}

bool test_search_random()
{
  bool correct = true;
  printf("Search a random Sudoku!\n");
  Puzzle puzzle;
  Solver solver(puzzle, true);
  solver.find_next_solution();
  if (solver.solution_is_valid())
    print_sudoku(puzzle);
  else
    correct = false, printf("Error: Sudoku is invalid!\n");
  printf("Search another random Sudoku!\n");
  solver.reset();
  solver.find_next_solution();
  if (solver.solution_is_valid())
    print_sudoku(puzzle);
  else
    correct = false, printf("Error: Sudoku is invalid!\n");
  return correct;
}

bool test_generate_symmetric()
{
  bool correct = true;
  printf("Generate a random Sudoku with 36 symmetric givens!\n");
  Puzzle puzzle;
  Generator generator(puzzle, 36);
  generator.find_next_solution();
  if (generator.solution_is_valid())
    print_sudoku(puzzle);
  else
    correct = false, printf("Error: Sudoku is invalid!\n");
  printf("Solve the generated Sudoku!\n");
  Solver solver(puzzle);
  solver.find_next_solution();
  if (solver.solution_is_valid())
    print_sudoku(puzzle);
  else
    correct = false, printf("Error: Sudoku is invalid!\n");
  solver.find_next_solution();
  if (solver.solution_is_valid())
    correct = false, print_sudoku(puzzle),
      printf("Error: Sudoku has more than one solution!\n");
  else
    printf("Sudoku has only one solution!\n");
  printf("\n");
  return correct;
}

bool test_generate_non_symmetric()
{
  bool correct = true;
  printf("Generate a random Sudoku with 26 non-symmetric givens!\n");
  Puzzle puzzle;
  Generator generator(puzzle, 26, false);
  generator.find_next_solution();
  if (generator.solution_is_valid())
    print_sudoku(puzzle);
  else
    correct = false, printf("Error: Sudoku is invalid!\n");
  printf("Solve the generated Sudoku!\n");
  Solver solver(puzzle);
  solver.find_next_solution();
  if (solver.solution_is_valid())
    print_sudoku(puzzle);
  else
    correct = false, printf("Error: Sudoku is invalid!\n");
  solver.find_next_solution();
  if (solver.solution_is_valid())
    correct = false, print_sudoku(puzzle),
      printf("Error: Sudoku has more than one solution!\n");
  else
    printf("Sudoku has only one solution!\n");
  printf("\n");
  return correct;
}

int test_sudoku()
{
  unsigned int count = 0;
  unsigned int error = 0;
  ++count;
  if (!test_search_first())
    ++error;
  ++count;
  if (!test_search_random())
    ++error;
  ++count;
  if (!test_generate_symmetric())
    ++error;
  ++count;
  if (!test_generate_non_symmetric())
    ++error;
  if (error > 0)
    printf("%d errors in %d tests\n", error, count);
  else
    printf("All %d tests correct\n", count);
  if (error > 0)
    return 1;
  return 0;
}
#endif // WITH_TEST

int main(int argc, char* argv[])
{
  static const struct option long_options[] =
  {
    { "non-sym", no_argument, NULL, 'n' },
    { "dump",    no_argument, NULL, 'd' },
    { "solve",   no_argument, NULL, 's' },
    { "print",   no_argument, NULL, 'p' },
#ifdef WITH_TEST
    { "test",    no_argument, NULL, 't' },
#endif
    { "version", no_argument, NULL, 'v' },
    { "help",    no_argument, NULL, 'h' },
    { NULL }
  };
#ifdef WITH_TEST
  static const char* options = "ndsptvh";
#else
  static const char* options = "ndspvh";
#endif
  bool non_sym = false;
  bool dump    = false;
  bool solve   = false;
  bool print   = false;
  bool test    = false;
  bool version = false;
  bool help    = false;
  bool error   = false;
  int c;
  while ((c = getopt_long(argc, argv, options, long_options, NULL)) != -1)
  {
    switch (c)
    {
      case 'n': non_sym = true; break;
      case 'd': dump    = true; break;
      case 's': solve   = true; break;
      case 'p': print   = true; break;
#ifdef WITH_TEST
      case 't': test    = true; break;
#endif
      case 'v': version = true; break;
      case 'h': help    = true; break;
      default:  error   = true;
    }
  }
  int arg_count = argc - optind;

  bool generate = non_sym || dump ||
                  (arg_count == 0 && !test && !version && !help) ||
                  (arg_count == 1 && !solve && !print);
  unsigned int givens_count = 36;
  if (arg_count == 1 && generate &&
      sscanf(argv[optind], "%u", &givens_count) != 1)
    return print_usage();

  if ((generate ? 1 : 0) + (solve ? 1 : 0) + (print ? 1 : 0) + (test ? 1 : 0) +
      (version ? 1 : 0) + (help ? 1 : 0) > 1 || error)
    return print_usage();

  if (generate && 0 < givens_count && givens_count <= SDIM)
    return generate_puzzle(givens_count, non_sym, dump);

  if (solve && arg_count == 1 && strlen(argv[optind]) >= SDIM)
    return solve_puzzle(argv[optind]);

  if (print && arg_count == 1 && strlen(argv[optind]) >= SDIM)
    return print_puzzle(argv[optind]);

#ifdef WITH_TEST
  if (test)
    return test_sudoku();
#endif

  if (version)
    return print_version();

  return print_usage();
}