Sudoku solving/generating

Since yesterday I have been working on the Sudoku solving and generating algorithms. Even though there is some progress and I extended my current solving algorithm, it is far from being perfect. I am afraid that I will not run away from making a mathematical description of a problem what does not encourage me to work… So what have I done and found out?

1. My solving algorithm includes two parts. Firstly it fills in all those numbers, where there are no other choices left (it is to be improved furthermore but it will be trivial). Second part is when the algorithm has to make a guess, go back to first part and then backtrack if a contradiction was found. Each guess was filled into a new copy of a current grid which was making the algorithm quite memory consuming. The new algorithm uses a stack to remember a history of actions and undoes its choices when backtracking what appeared to be much less efficient. The previous algorithm was solving an empty 16×16 Sudoku within few seconds, while a new one is unable to do it within few minutes. I think that the reason for this is that the history keeps track of every modification, including removals of suggestions.

2. I have extended the solving algorithm so it checks whether there exists such a zone (e.g. row or column) and such a number that the number cannot be put into any cell of this zone. The previous temporary solution was measuring the time of algorithm runtime to return the UNKNOWN status of a meaning “probably unsolvable but I am not efficient enough to find it”. It has be changed know and the algorithm returns either true if solvable or false if not solvable. I am going to add this new code into the previous algorithm – that seems to be the most efficient way.

3. After doing some research on the Sudoku solving/generating algorithms I have found out that it may be wiser to have a solved Sudoku and then remove the given amount of numbers from it. This approach apparently allows also to create a Sudoku with a unique solution – one of the most important parts my program is missing. I have found that there exists transformations that modify the grid and the grid still remains in a valid state. Those transformations are:

  • swapping two columns within the same block of columns (e.g. in Sudoku 9×9 we can swap 1st column with 2nd or 3rd, 4th column with 5th or 6th and 7th column with 8th or 9th).
  • swapping two rows within the same block
  • swapping two blocks of columns
  • swapping two blocks of rows
  • reflecting along diagonals
  • reflecting across the centre of the grid
  • rotations by n*90 degrees about the centre of the grid

And everything would be fine if not a one little detail I will describe on an example: Suppose that the three first cells in the first row contain numbers 1, 2 and 3. If we swap rows, blocks of rows or blocks of columns, nothing changes. If we swap columns, we change their order, but they are still next to each other. If we reflect or rotate, they will be rotated by 90 degrees but still will be in the same line (but now vertical nor horizontal). So if everywhere 1, 2 and 3 form a line within a zone, we will never get a Sudoku with e.g.:

12_                              1__                              _1_
_3_              or              _2_              or              _2_
___                              __3                              3__

4. I have spot that some Sudoku games generate grids that have a symmetry across the centre of the grid (i.e. not the values, but what cells are filled). I am still do not know how does it exactly work but I have also seen it while doing some research.

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

Posted on March 14, 2012, in My Projects and tagged . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: