Sudoku Crazy
If you don't know about "sudoku", you wont understand. Since April, it has become a popular puzzle in most newspapers. I'm not much good at crosswords, I try them, especially with Ep; not the cryptic, but the straightforward ones. I find it hard to remember words though I do think it's a good exercise.
These sudoku are more my level, much less sophisticated, they require only accuracy in applying simple logic.
Over the past 6 weeks, I've been writing a Java program to solve the puzzles. It's only been an exercise to learn to program in Java, but it did become something of an obsession. You might not find the following interesting and I wont mind if you skip it, but I need to describe the stages which I went through in my voyage of discovery.
The puzzle is a 9x9 matrix of cells, about 22 of which are occupied with single digits. The problem is to fill in the remaining cells with digits so that each of the 9 rows, columns and 3x3 boxes contain the digits 1 to 9.
I started by writing a routine that looked at each empty cell, cycling through the digits to find which would legally fit. For the odd cell which only had one digit possible, I'd fill it in. All subsequent efforts used this primary checking routine. Next there was the recursive routine which started at the top left, inserted the first digit which fitted and went on to the next, when it found that no digit fitted it would drop back and increment the previous cell. This "bulldozer" routine was hopelessly prodigal with the computer's memory, and there would be warnings it might crash. I did make it slightly more efficient by ordering the rows so the routine would start with the row with the fewest possible alternatives, but I wasn't satisfied. So I attempted to reproduce a logic I used when I did the puzzle myself. This I called "boblogic"; which is that, looking at a single row, column or box, I might find two cells where the same two possible numbers would fit. In this case, those two numbers could be excluded as possibilities for the remaining cells in the row, column or box. This I found to be a fiendishly difficult logic to program, especially for the boxes.
The next attempt, called "eplogic" looked at numbers first and cells second. It collects numbers which already exist in a row, column or box; then it finds the numbers needed. It cycles through these, looking at each of the empty cells; if it finds a number which can only fit in one of the empty cells, it is inserted. Again, I struggled to code this logic. I found each time I repeated the routine, it would find more numbers. Three repetitions is enough to complete a "medium" difficulty puzzle.
So it's done, Ep says I've obviously got withdrawal symptoms, and I think she's right, but I'm getting it out of my system by burdening the blog.
These sudoku are more my level, much less sophisticated, they require only accuracy in applying simple logic.
Over the past 6 weeks, I've been writing a Java program to solve the puzzles. It's only been an exercise to learn to program in Java, but it did become something of an obsession. You might not find the following interesting and I wont mind if you skip it, but I need to describe the stages which I went through in my voyage of discovery.
The puzzle is a 9x9 matrix of cells, about 22 of which are occupied with single digits. The problem is to fill in the remaining cells with digits so that each of the 9 rows, columns and 3x3 boxes contain the digits 1 to 9.
I started by writing a routine that looked at each empty cell, cycling through the digits to find which would legally fit. For the odd cell which only had one digit possible, I'd fill it in. All subsequent efforts used this primary checking routine. Next there was the recursive routine which started at the top left, inserted the first digit which fitted and went on to the next, when it found that no digit fitted it would drop back and increment the previous cell. This "bulldozer" routine was hopelessly prodigal with the computer's memory, and there would be warnings it might crash. I did make it slightly more efficient by ordering the rows so the routine would start with the row with the fewest possible alternatives, but I wasn't satisfied. So I attempted to reproduce a logic I used when I did the puzzle myself. This I called "boblogic"; which is that, looking at a single row, column or box, I might find two cells where the same two possible numbers would fit. In this case, those two numbers could be excluded as possibilities for the remaining cells in the row, column or box. This I found to be a fiendishly difficult logic to program, especially for the boxes.
The next attempt, called "eplogic" looked at numbers first and cells second. It collects numbers which already exist in a row, column or box; then it finds the numbers needed. It cycles through these, looking at each of the empty cells; if it finds a number which can only fit in one of the empty cells, it is inserted. Again, I struggled to code this logic. I found each time I repeated the routine, it would find more numbers. Three repetitions is enough to complete a "medium" difficulty puzzle.
So it's done, Ep says I've obviously got withdrawal symptoms, and I think she's right, but I'm getting it out of my system by burdening the blog.
posted by us at 7:48 PM
<< Home