x404.co.uk
http://www.x404.co.uk/forum/

Genius algorithm I created last night
http://www.x404.co.uk/forum/viewtopic.php?f=4&t=16372
Page 1 of 1

Author:  Fogmeister [ Tue May 01, 2012 7:55 am ]
Post subject:  Genius algorithm I created last night

I trying to come up with a way of parsing a string of any length to find a "sudoku definition" inside it.

A sudoku definition is a string of 81 numbers from 0 to 9 including ".". The zeroes and .s indicate blank squares.

What I really didn't want to do was start from each character and check the next 80 characters for an "incorrect" character. As this would mean parsing the entire string many times.

The solution I came up with was really quite good :D

In psuedo code...

Code:
while (i <= string.length - 81)
{
    get a substring from i of length 81.
   
    remove all sudoku characters from the substring.  (easy to do with a built in ObjC string function)
   
    if substring length = 0 then substring is a sudoku definition... return substring.
   
    if substring length > = then i += substring.length.
}


By doing it this way I could potentially be moving through the string 81 characters at a time. It only then starts to "slow down" when it begins to see a sudoku definition and will always find it :)

One thing I don't do is validate the grid but that is something maybe for the next version :)

I was really pleased with it though :D

Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/