Recursive Sudoku solver

I got back to coding after a long absence cause mainly by the final exams. My first project was to implement a recursive Sudoku solver.

I had previously written an iterative Sudoku solver that makes use of the same techniques that people do by ruling out what numbers can fit in a cell untill there is only one possible number that can fir. However, this method fails on harder puzzles where a guess has to be made in order to solve the puzzle.

Brute force algorithms enter here. The Sudoku puzzle lends itself well to the classic recursive brute force algorithm,

The step by step algorithm:

  1. If puzzle is solved
    1. End
  2. If puzzle is not valid
    1. End
  3. Find first empty cell : cell that contains 0
  4. While the cell value is less than 10 and while the puzzle is unsolved
    1. Increment cell by 1
    2. Solve
  5. If the cell value is greater than 9
    1. Reset the cell value to 0 : This means that a previous guess was invalid so this ends and the previous cell value is incremented

Project Euler – Problem 6

Problem 6 is by far one of the easiest problems yet.

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Again, there are at – least two possible methods. One is our dear friend, Mr. Brute Force 🙂 The other is more mathematical.

Brute force description

There’s not much to be said about this one. Create loops to add the sum of numbers from 1 to 100, and another loop to add the squares of numbers from 1 to 100. Square the sum you get in the first loop, and then find it’s difference. It’s simple.

Mathematical Approach

To understand the mathematical approach, you must have knowledge of the two formulas given below:

It’s all high school maths. They are easy to prove as well, especially the first one.
Writing out functions for the above should not be a difficult task, whatever language you choose.

In my version, I’ve written them as Macros (using the # pre processor directive)

Comparison

For a single iteration, both methods take less than 0.001 s or 1 ms which means they can’t be measured. Over 1,000,000 iterations, the brute force method takes 0.723 s while the other approach still clocks in at a nifty 0.001 s.

Solution in C++

Project Euler – Problem 4

The problem description, from the Project Euler website:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 ×99.

Find the largest palindrome made from the product of two 3-digit numbers.

Again, a little brute force never hurt anybody 😛

General Algorithm

Before you begin, you must identify how exactly your going to check if a number is a palindrome. The question defines a palindrome for you: A palindromic number reads the same both ways. IMO, the easiest way to check if a number is a palindrome is to reverse it and see if it is equal to it’s original value. Given below is a general reverse algorithm.

  1. Initialize reversed number to zero.
  2. While the number to be reversed (n), is not zero:
    1. Get the last digit by n % 10.
    2. Make it a subsequent digit of the reversed number by doing the following:
      1. Reversed number  *= 10.
      2. Reversed Number += last digit.
    3. Remove the last digit (n /= 10).
  3. At the end of the loop, you will have the reversed number.

I guess the iteration for checking the product of every 3 digit number needs no explanation.

Solution in C++

Note: If you’re having trouble with _int64 on your compiler, replace it with long long int