OCuk Weekly Programming Challenge #1: Sudoku Solver [12 - 19 March 2014]

[Number_25]

In this weeks challenge you will be required to design and implement a Sudoku Solver application. Sudoku is a logic-based numerical placement game which originates from France.

To correctly answer a Sudoku puzzle you are required to fill empty cells in a 9x9 grid in accordance to the following rules...

• A number can only feature once in each row.
• A number can only feature once in each column.
• A number can only feature once in each region. (3x3 block)

On successful completion of this challenge, you are required to produce an application that can successfully solve even the hardest Sudoku puzzle.

What your application must load...

The application should be able to load in a simple plain text file. My advice to you would to think of a suitable way of storing the data into memory.

  1     8 
5       2
   3 6   
  4 8 3  
 7  5  1 
  2 1 6  
   2 7   
8       5
 3     4

You can download this file here.

What your application should output...

The application should either print out onto the screen or in a filethe solved puzzle.Use whatever languages you want, the more obscure the better.

This is just for fun, no awards (yet)

On successful completion, please put your finished code in both spoiler and code tags!

Good luck!

 

[john_s]

Cracking idea!

 

[xbenjiiman]

Not the prettiest thing, but hey.

Spoiler

solver.js

var SudokuSolver = function(board) {
    this.sudokuBoard = board;
    this.solved = [
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        []
    ];
}

SudokuSolver.prototype.parse = function() {
    var result = [];
    var fill = this.sudokuBoard.replace(/ /g, '0');
    var rows = fill.split(/\n/g);
    for (var i in rows) {
        result[i] = rows[i].split('');
    }
    this.sudokuBoard = result;
    return this;
}

SudokuSolver.prototype.solve = function() {
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            this.solved[i][j] = (this.sudokuBoard[i][j] > 0) ? 2 : 0;
        }
    }
    this.solveNumber(0, 0);
    return this;
}

SudokuSolver.prototype.display = function() {
    var result = '';
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            if (j % 9 === 0) {
                result += "\n";
            }
            result += this.sudokuBoard[i][j] + " ";
        }
    }
    return result;
}

SudokuSolver.prototype.solveNumber = function(x, y) {
    if (x === 9) {
        var count = 0;
        for (var i = 0; i < 9; i++) {
            for (var j = 0; j < 9; j++) {
                count += (this.solved[i][j] > 0) ? 1 : 0;
            }
        }
        return (count === 81) ? true : false;
    }

    if (this.solved[x][y] >= 1) {
        var nX = x;
        var nY = y + 1;
        if (nY === 9) {
            nX = x + 1;
            nY = 0;
        }
        return this.solveNumber(nX, nY);
    } else {
        var used = [0, 0, 0, 0, 0, 0, 0, 0, 0];
        for (var i = 0; i < 9; i++) {
            if (this.solved[x][i] >= 1) {
                used[this.sudokuBoard[x][i] - 1] = true;
            }
            if (this.solved[i][y] >= 1) {
                used[this.sudokuBoard[i][y] - 1] = true;
            }
        }

        for (var i = x - (x % 3); i < x - (x % 3) + 3; i++) {
            for (var j = y - (y % 3); j < y - (y % 3) + 3; j++) {
                if (this.solved[i][j] >= 1) {
                    used[this.sudokuBoard[i][j] - 1] = true;
                }
            }
        }

        for (var i = 0; i < used.length; i++) {
            if (!used[i]) {
                this.solved[x][y] = 1;
                this.sudokuBoard[x][y] = i + 1;

                var nX = x;
                var nY = y + 1;
                if (nY === 9) {
                    nX = x + 1;
                    nY = 0;
                }

                if (this.solveNumber(nX, nY)) {
                    return true;
                }

                for (var k = 0; k < 9; k++) {
                    for (var l = 0; l < 9; l++) {
                        if (k > x || (k === x && l >= y)) {
                            if (this.solved[k][l] === 1) {
                                this.solved[k][l] = 0;
                                this.sudokuBoard[k][l] = 0;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
}

module.exports = SudokuSolver;

app.js

var Sudoku = require('./solver.js'),
    fs = require('fs');

var puzzle = fs.readFileSync('sudokusolver.dat', 'utf8');

var sudoku = new Sudoku(puzzle).parse().solve();
console.log(sudoku.display());

Returns

C:\\njs\\sudoku>node app.js

6 1 7 9 2 5 4 8 3
5 4 3 8 7 1 9 6 2
2 9 8 3 4 6 5 7 1
1 5 4 6 8 9 3 2 7
3 7 6 4 5 2 8 1 9
9 8 2 7 1 3 6 5 4
4 6 5 2 3 7 1 9 8
8 2 9 1 6 4 7 3 5
7 3 1 5 9 8 2 4 6

Git Repo: http://git.xbenjii.co.uk/xbenjii/sudoku-solver

 

[Dj_Jestar]

I've attempted this before in a purely object manner, as an exercise to instill the "tell, don't ask" principle (e.g. tell a cell to be a value etc, so no matrix of values allowed). Good lord it was hard work

 

[xbenjiiman]

I've attempted this before in a purely object manner, as an exercise to instill the "tell, don't ask" principle (e.g. tell a cell to be a value etc, so no matrix of values allowed). Good lord it was hard work

Yep, it was an absolute brain**** trying to get my head around the backtracking algorithm.

 

[Spike560]

I am currently trying to learn C++ and have just started out. So this was a tough ask!

Method is that of brute force.

The two areas I struggled with were firstly, how to track back in the grid once a dead end was reached.

Secondly, how to read a text file into the array I needed to test!

Anyway, my solution:

Spoiler

Main.cpp

#include <iostream>
#include <algorithm>
#include <fstream>
#include "functions.h"

using std::cout;
using std::endl;

bool inRow(int (&arr)[9][9], int var, int row);
bool inCol(int (&arr)[9][9], int var, int col);
bool inBox(int (&arr)[9][9], int var, int row, int col);
bool gridValid(int (&arr)[9][9]);

int main()
{
    std::ifstream myFile("sudokusolver.dat");

    int myArray[9][9] = {0};

    for (int i = 0 ; i < 9 ; ++i){
        for (int j = 0 ; j < 9 ; ++j){

            int a = myFile.get();
            if (a == '\n'){
                if (j == 0){
                    --i;
                    j = 7;
                }
                else{
                    j -= 2;
                }
                break;
            }

            if (isdigit(a)){
                int val = a - '0';
                myArray[i][j] = val;
            }
        }
    }

    int safeArray[9][9];

    std::copy(std::begin(myArray), std::end(myArray), std::begin(safeArray));

    int cnt = 1;
    bool success = false;
    bool failure = false;

    for (int i = 0 ; i < 9 ; ++i){
        for (int j = 0; j < 9 ; ++j){

            if ((myArray[i][j] != 0) && (myArray[i][j] == safeArray[i][j])) {
                if (failure){
                    if (j == 0){
                        --i;
                        j = 7;
                    }
                    else{
                       j -= 2;
                    }
                }
                continue;
            }

            if((failure) && (myArray[i][j] == 9)){
                myArray[i][j] = 0;
                if (j == 0){
                    --i;
                    j = 7;
                }
                else{
                    j -= 2;
                }
                continue;
            }

            if (failure){
            cnt = 1 + myArray[i][j];
            }
            else {
            cnt = myArray[i][j];
            }

            if (cnt == 0){
                ++cnt;
            }

            failure = false;
            success = false;

            while (cnt < 10){
                myArray[i][j] = cnt;
                if ( (inRow(myArray,cnt,i)) || (inCol(myArray,cnt,j)) || (inBox(myArray,cnt,i,j)) ){
                    ++cnt;
                    continue;
                }
                success = true;
                break;
            }

            if (success){
                continue;
            }

            failure = true;

            myArray[i][j] = 0;
            if (j == 0){
                --i;
                j = 7;
            }
            else{
                j -= 2;
            }
        }
    }

    if(gridValid(myArray)){

        cout << "Grid is solved! Final grid is:" << endl << endl;
        for (int i = 0 ; i < 9 ; ++i){
            for (int j = 0 ; j < 9 ; ++j){

                cout << myArray[i][j] << " ";
            }
            cout << endl;
        }
    }
    else{

        cout << "Algorithm failed to solve grid" << endl;
    }

    return 0;
}

functions.h

bool inRow(int (&arr)[9][9], int var, int row){

    int cnt = 0;
    for (int i=0 ; i<9 ; ++i){
        if ((arr[row][i]) == var){
            ++cnt;
            if (cnt > 1)
                return 1;
        }
    }
    return 0;
}

bool inCol(int (&arr)[9][9], int var, int col){

    int cnt = 0;
    for (int i=0 ; i<9 ; ++i){
        if ((arr[i][col]) == var){
            ++cnt;
            if (cnt > 1)
                return 1;
        }
    }
    return 0;
}

bool inBox(int (&arr)[9][9], int var, int row, int col){

    int startRow = (row < 3) ? 0 : (row < 6) ? 3 : 6;
    int startCol = (col < 3) ? 0 : (col < 6) ? 3 : 6;
    int cnt = 0;
    for (int i = startRow; i < (startRow + 3); ++i){
        for (int j = startCol; j < (startCol + 3); ++j){
            if ((arr[i][j]) == var){
                ++cnt;
                if (cnt > 1)
                    return 1;
            }
        }
    }
    return 0;
}


bool gridValid(int (&arr)[9][9]){

    for (int i = 0 ; i < 9 ; ++i ){
        for (int j = 0 ; j < 9 ; ++j){
            if (inRow(arr,arr[i][j],i) || inCol(arr,arr[i][j],j) || inBox(arr,arr[i][j],i,j) )
                return 0;
        }
    }
    return 1;
}

Returns

Grid is solved! Final grid is:

6 1 7 9 2 5 4 8 3
5 4 3 8 7 1 9 6 2
2 9 8 3 4 6 5 7 1
1 5 4 6 8 9 3 2 7
3 7 6 4 5 2 8 1 9
9 8 2 7 1 3 6 5 4
4 6 5 2 3 7 1 9 8
8 2 9 1 6 4 7 3 5
7 3 1 5 9 8 2 4 6

Process returned 0 (0x0)   execution time : 0.047 s
Press any key to continue.

I have not tested it with any other input file/grid so who knows whether it is foolproof.

Improvements to the code are more than welcome.

Reading input from a file was also new to me, and so validation around that area would be a obvious improvement.

 

[xbenjiiman]

I am currently trying to learn C++ and have just started out. So this was a tough ask!

Method is that of brute force.

The two areas I struggled with were firstly, how to track back in the grid once a dead end was reached.

Secondly, how to read a text file into the array I needed to test!

Anyway, my solution:

Spoiler

Main.cpp

#include <iostream>
#include <algorithm>
#include <fstream>
#include "functions.h"

using std::cout;
using std::endl;

bool inRow(int (&arr)[9][9], int var, int row);
bool inCol(int (&arr)[9][9], int var, int col);
bool inBox(int (&arr)[9][9], int var, int row, int col);
bool gridValid(int (&arr)[9][9]);

int main()
{
    std::ifstream myFile("sudokusolver.dat");

    int myArray[9][9] = {0};

    for (int i = 0 ; i < 9 ; ++i){
        for (int j = 0 ; j < 9 ; ++j){

            int a = myFile.get();
            if (a == '\n'){
                if (j == 0){
                    --i;
                    j = 7;
                }
                else{
                    j -= 2;
                }
                break;
            }

            if (isdigit(a)){
                int val = a - '0';
                myArray[i][j] = val;
            }
        }
    }

    int safeArray[9][9];

    std::copy(std::begin(myArray), std::end(myArray), std::begin(safeArray));

    int cnt = 1;
    bool success = false;
    bool failure = false;

    for (int i = 0 ; i < 9 ; ++i){
        for (int j = 0; j < 9 ; ++j){

            if ((myArray[i][j] != 0) && (myArray[i][j] == safeArray[i][j])) {
                if (failure){
                    if (j == 0){
                        --i;
                        j = 7;
                    }
                    else{
                       j -= 2;
                    }
                }
                continue;
            }

            if((failure) && (myArray[i][j] == 9)){
                myArray[i][j] = 0;
                if (j == 0){
                    --i;
                    j = 7;
                }
                else{
                    j -= 2;
                }
                continue;
            }

            if (failure){
            cnt = 1 + myArray[i][j];
            }
            else {
            cnt = myArray[i][j];
            }

            if (cnt == 0){
                ++cnt;
            }

            failure = false;
            success = false;

            while (cnt < 10){
                myArray[i][j] = cnt;
                if ( (inRow(myArray,cnt,i)) || (inCol(myArray,cnt,j)) || (inBox(myArray,cnt,i,j)) ){
                    ++cnt;
                    continue;
                }
                success = true;
                break;
            }

            if (success){
                continue;
            }

            failure = true;

            myArray[i][j] = 0;
            if (j == 0){
                --i;
                j = 7;
            }
            else{
                j -= 2;
            }
        }
    }

    if(gridValid(myArray)){

        cout << "Grid is solved! Final grid is:" << endl << endl;
        for (int i = 0 ; i < 9 ; ++i){
            for (int j = 0 ; j < 9 ; ++j){

                cout << myArray[i][j] << " ";
            }
            cout << endl;
        }
    }
    else{

        cout << "Algorithm failed to solve grid" << endl;
    }

    return 0;
}

functions.h

bool inRow(int (&arr)[9][9], int var, int row){

    int cnt = 0;
    for (int i=0 ; i<9 ; ++i){
        if ((arr[row][i]) == var){
            ++cnt;
            if (cnt > 1)
                return 1;
        }
    }
    return 0;
}

bool inCol(int (&arr)[9][9], int var, int col){

    int cnt = 0;
    for (int i=0 ; i<9 ; ++i){
        if ((arr[i][col]) == var){
            ++cnt;
            if (cnt > 1)
                return 1;
        }
    }
    return 0;
}

bool inBox(int (&arr)[9][9], int var, int row, int col){

    int startRow = (row < 3) ? 0 : (row < 6) ? 3 : 6;
    int startCol = (col < 3) ? 0 : (col < 6) ? 3 : 6;
    int cnt = 0;
    for (int i = startRow; i < (startRow + 3); ++i){
        for (int j = startCol; j < (startCol + 3); ++j){
            if ((arr[i][j]) == var){
                ++cnt;
                if (cnt > 1)
                    return 1;
            }
        }
    }
    return 0;
}


bool gridValid(int (&arr)[9][9]){

    for (int i = 0 ; i < 9 ; ++i ){
        for (int j = 0 ; j < 9 ; ++j){
            if (inRow(arr,arr[i][j],i) || inCol(arr,arr[i][j],j) || inBox(arr,arr[i][j],i,j) )
                return 0;
        }
    }
    return 1;
}

Returns

Grid is solved! Final grid is:

6 1 7 9 2 5 4 8 3
5 4 3 8 7 1 9 6 2
2 9 8 3 4 6 5 7 1
1 5 4 6 8 9 3 2 7
3 7 6 4 5 2 8 1 9
9 8 2 7 1 3 6 5 4
4 6 5 2 3 7 1 9 8
8 2 9 1 6 4 7 3 5
7 3 1 5 9 8 2 4 6

Process returned 0 (0x0)   execution time : 0.047 s
Press any key to continue.

I have not tested it with any other input file/grid so who knows whether it is foolproof.

Improvements to the code are more than welcome.

Reading input from a file was also new to me, and so validation around that area would be a obvious improvement.

You're 18 minutes late.

 

[Spike560]

Ha ha! While that might be the case, the inaugural OCUK Weekly Programming Challenge could surely only be complete with at least two entries....

 

[Nimble]

My solution in Racket (a dialect of Lisp).

Spoiler

#lang racket

(define (sudoku-read puzzle-str)
  (if (> (string-length puzzle-str) 0)
      (let ([c (string-ref puzzle-str 0)])
        (cond [(equal? c #\space) (cons 0 (sudoku-read (substring puzzle-str 1)))]
              [(equal? c #\newline) (sudoku-read (substring puzzle-str 1))]
              [else (cons (string->number (string c)) (sudoku-read (substring puzzle-str 1)))]
              ))
      null
      )
  )

(define (sudoku-output puzzle [n 0])
  (if (= (remainder n 10) 0)
      (string-append "\n" (sudoku-output puzzle (add1 n)))
      (if (> (length puzzle) 0)
          (if (= (car puzzle) 0)
              (string-append " " (sudoku-output (cdr puzzle) (add1 n)))
              (string-append (number->string (car puzzle)) (sudoku-output (cdr puzzle) (add1 n)))
              )
          ""
          )
      )
  )


(define (sudoku-check-conflict puzzle n num [n2 0])
  (if (= n2 81)
      #f
      (if (and
           (= (list-ref puzzle n2) num)
           (or (= (remainder n 9) (remainder n2 9))
               (= (quotient n 9) (quotient n2 9))
               (let ([sqr-offset (- n2
                                (+ (* (quotient n 27) 27)
                                   (* (quotient (remainder n 9) 3) 3)))])
                 (and (>= sqr-offset 0) (< sqr-offset 21) (< (remainder sqr-offset 9) 3)))))
          #t
          (sudoku-check-conflict puzzle n num (add1 n2))
          )
      )
  )

(define (sudoku-set puzzle n num)
  (append (take puzzle n) (list num) (drop puzzle (add1 n))) 
  )

(define (sudoku-solve puzzle [n 0] [num 1])
  (if (= n 81)
      puzzle
      (if (= (list-ref puzzle n) 0)
          (if (= num 10)
              #f
              (if (sudoku-check-conflict puzzle n num)
                  (sudoku-solve puzzle n (add1 num))
                  (let ([solution (sudoku-solve (sudoku-set puzzle n num) (add1 n))])
                    (if solution
                        solution
                        (sudoku-solve puzzle n (add1 num))
                        ))
                  )
              )
          (sudoku-solve puzzle (add1 n))
          )
      )
  )


(display
 (sudoku-output
  (sudoku-solve
   (sudoku-read (file->string "sudoku-puzzle")))))

Result:

> ./sudoku-solve

321945768
569871432
748326591
154689327
673452819
982713654
415267983
896134275
237598146

If you use recursion then backtracking is effortless (though the performance may not be great).

I am currently trying to learn C++ and have just started out. So this was a tough ask!

Method is that of brute force.

The two areas I struggled with were firstly, how to track back in the grid once a dead end was reached.

Secondly, how to read a text file into the array I needed to test!

Anyway, my solution:

Spoiler

Main.cpp

#include <iostream>
#include <algorithm>
#include <fstream>
#include "functions.h"

using std::cout;
using std::endl;

bool inRow(int (&arr)[9][9], int var, int row);
bool inCol(int (&arr)[9][9], int var, int col);
bool inBox(int (&arr)[9][9], int var, int row, int col);
bool gridValid(int (&arr)[9][9]);

int main()
{
    std::ifstream myFile("sudokusolver.dat");

    int myArray[9][9] = {0};

    for (int i = 0 ; i < 9 ; ++i){
        for (int j = 0 ; j < 9 ; ++j){

            int a = myFile.get();
            if (a == '\n'){
                if (j == 0){
                    --i;
                    j = 7;
                }
                else{
                    j -= 2;
                }
                break;
            }

            if (isdigit(a)){
                int val = a - '0';
                myArray[i][j] = val;
            }
        }
    }

    int safeArray[9][9];

    std::copy(std::begin(myArray), std::end(myArray), std::begin(safeArray));

    int cnt = 1;
    bool success = false;
    bool failure = false;

    for (int i = 0 ; i < 9 ; ++i){
        for (int j = 0; j < 9 ; ++j){

            if ((myArray[i][j] != 0) && (myArray[i][j] == safeArray[i][j])) {
                if (failure){
                    if (j == 0){
                        --i;
                        j = 7;
                    }
                    else{
                       j -= 2;
                    }
                }
                continue;
            }

            if((failure) && (myArray[i][j] == 9)){
                myArray[i][j] = 0;
                if (j == 0){
                    --i;
                    j = 7;
                }
                else{
                    j -= 2;
                }
                continue;
            }

            if (failure){
            cnt = 1 + myArray[i][j];
            }
            else {
            cnt = myArray[i][j];
            }

            if (cnt == 0){
                ++cnt;
            }

            failure = false;
            success = false;

            while (cnt < 10){
                myArray[i][j] = cnt;
                if ( (inRow(myArray,cnt,i)) || (inCol(myArray,cnt,j)) || (inBox(myArray,cnt,i,j)) ){
                    ++cnt;
                    continue;
                }
                success = true;
                break;
            }

            if (success){
                continue;
            }

            failure = true;

            myArray[i][j] = 0;
            if (j == 0){
                --i;
                j = 7;
            }
            else{
                j -= 2;
            }
        }
    }

    if(gridValid(myArray)){

        cout << "Grid is solved! Final grid is:" << endl << endl;
        for (int i = 0 ; i < 9 ; ++i){
            for (int j = 0 ; j < 9 ; ++j){

                cout << myArray[i][j] << " ";
            }
            cout << endl;
        }
    }
    else{

        cout << "Algorithm failed to solve grid" << endl;
    }

    return 0;
}

functions.h

bool inRow(int (&arr)[9][9], int var, int row){

    int cnt = 0;
    for (int i=0 ; i<9 ; ++i){
        if ((arr[row][i]) == var){
            ++cnt;
            if (cnt > 1)
                return 1;
        }
    }
    return 0;
}

bool inCol(int (&arr)[9][9], int var, int col){

    int cnt = 0;
    for (int i=0 ; i<9 ; ++i){
        if ((arr[i][col]) == var){
            ++cnt;
            if (cnt > 1)
                return 1;
        }
    }
    return 0;
}

bool inBox(int (&arr)[9][9], int var, int row, int col){

    int startRow = (row < 3) ? 0 : (row < 6) ? 3 : 6;
    int startCol = (col < 3) ? 0 : (col < 6) ? 3 : 6;
    int cnt = 0;
    for (int i = startRow; i < (startRow + 3); ++i){
        for (int j = startCol; j < (startCol + 3); ++j){
            if ((arr[i][j]) == var){
                ++cnt;
                if (cnt > 1)
                    return 1;
            }
        }
    }
    return 0;
}


bool gridValid(int (&arr)[9][9]){

    for (int i = 0 ; i < 9 ; ++i ){
        for (int j = 0 ; j < 9 ; ++j){
            if (inRow(arr,arr[i][j],i) || inCol(arr,arr[i][j],j) || inBox(arr,arr[i][j],i,j) )
                return 0;
        }
    }
    return 1;
}

Returns

Grid is solved! Final grid is:

6 1 7 9 2 5 4 8 3
5 4 3 8 7 1 9 6 2
2 9 8 3 4 6 5 7 1
1 5 4 6 8 9 3 2 7
3 7 6 4 5 2 8 1 9
9 8 2 7 1 3 6 5 4
4 6 5 2 3 7 1 9 8
8 2 9 1 6 4 7 3 5
7 3 1 5 9 8 2 4 6

Process returned 0 (0x0)   execution time : 0.047 s
Press any key to continue.

I have not tested it with any other input file/grid so who knows whether it is foolproof.

Improvements to the code are more than welcome.

Reading input from a file was also new to me, and so validation around that area would be a obvious improvement.

These lines

bool inRow(int (&arr)[9][9], int var, int row);
bool inCol(int (&arr)[9][9], int var, int col);
bool inBox(int (&arr)[9][9], int var, int row, int col);
bool gridValid(int (&arr)[9][9]);

serve no purpose. If you want to separate declarations and definitions, then those lines (the declarations) should be in functions.h and the current contents of functions.h should be in functions.cpp. You're also missing a header guard (http://en.wikipedia.org/wiki/Include_guard) in functions.h.

 

[Spike560]

Thanks for the pointers Nimble - will take that on board for future projects.

Our grid solutions are different by the way, does this mean there are multiple solutions or were we solving different grids?

 

[Nimble]

Ah, we're actually solving different grids; the supplied puzzle has 10 characters in the first line, I deleted the last space, while you deleted the first space.