Haui's bytes

news, diary, journal, whatever

Sudoku

Solving sudoku puzzles usually requires nothing more than a pen and some time. Solving 50 sudoku puzzles, however, requires a huge amount of time. 50 sudoku puzzles...? Yep, to get the solution for Problem 96 on ProjectEuler, 50 sudokus need to be solved first. I’ve solved my first 49 problems on ProjectEuler a few years ago and recently rediscovered the website. So I started with the sudoku problem and got the solution quite fast by using a simple brute force algorithm. I’m not going to post the solution for the problem, but just the C++ code for my sudoku solver. After compiling the program with g++ -std=c++11 -O6 -o sudokusolver sudokusolver.cpp, sudokus given in an input file are solved with a simple recursion based algorithm. An example is given below:

Trying to solve:
---------
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
---------
    |
    V
---------
483921657
967345821
251876493
548132976
729564138
136798245
372689514
814253769
695417382
---------

The sudokus in the input file must consist of 9 consecutive lines containing the initial values inside the sudoku. Blank fields are represented by zero. Multiple sudokus have to be separated by at least one dash in a single line.