Thursday, July 11, 2013

Sudoku Generator - A Bug Fixing Patch

The Full Story



The Problem

In the post "How to write a Sudoku Generator", the reader "vito kows" reported two issues.
  1. There is a bug in solutionCount().
  2. The generator takes too long for some seeds.
I am going to fix them below.


The Solution


1. Fix the bug in solutionCount()



Locate the original source code in solutionCount() :



Change it to:



Testing the Unique Solution Fix

Before proceeding to the next fix, you are suggested to compile and test it with :
javac *.java
java SudokuGenerator 28


2 Adding timeout in generate()


2.1 Locate source code in generate(int seed)

Change it to:


2.2 Locate source code in solveByRecursion()



Change it to



Final Testing

As a bonus for those who visited here, I am going to spend some CPU time to generate some puzzles with less than 30 open digits at the bottom of this post. And I will include the sample program that generates those puzzles.

Appendix - Puzzles with less than 30 open cells

String[] puzzles=new String[] {
"59......1..8..96.4.12.7.89.4.18..........6.17....2....8..24.....4....9...5.1.8...",
".2...7...5..2........68..3.7.5...6...4....5..69...3.8...1.6........7.842.3....176",
".621........75..4.5....6..274..6..3....5......5.....813.19...68.....34....561....",
"8...2...5.6.......9.73.1.4.6.5...9..7..9368...89.5....2.14...6....1....3....784..",
"....76...8.1....4...385............7...39.58.9...4.3.2...1.92..6...8..93.95...8..",
".....7..48.......31...46.8....19..........3.2.27...4.9..945...67..6.8....3...98.5",
"..3.87....1..4....8.7.....5.3..1.2..72...5.1.....6...467.....89.5.1......81..9.2.",
".2...98..7....1..6.68....1.....3...4..1........467..3......29..9168..32..839..4..",
".......93..971.8...6........3.124..6.7.59.48.942.......856.1............7.138....",
"7.......38...39......1.5.46...6.1..4.21...975.......6..82.9.6.....3.7.....3..81.9",
"......2.5.6..4.9..7.4.3......5..4...1..7...289......1..7......2.5.8.2.36....7....",
"..5....7...8.7....6..3.5..2..7.4..3638..5.1...9.1...2..4.761.....14...53.....3..7",
"..9..2.4...38....6.....3..23..65.7..9..4...63.2.3..1.5....8..7.69........7..1.4.8",
".5....23....4.......821.9........46.3........5..79...2..3....8..8.36..74.94..7..6",
"2....7.3.5..9.6.........8.11.64...873.58.........1.345..3....2.62.5.39.8.........",
"7...1.......586..164...3..5.3.7..1.44.8....2.....64.....7.3.9.85....1.6....29....",
".1...5......47.....6.3...8.......35..79.1.....2..58.6.6..7....48375....2.....6.3.",
"3.....4....8....63....27.185.67.2.89.2...3..1..3.6........3..5.7..9.1........692.",
"2...945.....2.......1..6....4.8.....1.2....73.6.1.2.89....1.3.47....3.5......97.6",
"7.326....8......695..19...3.3.....4...947...51.....6....8..13....5..2...3....729.",
"6.......5.9...6....47.536.2..43.2..71....78....61...2.2...4...1....39.8.5...2...3",
"..95...47.6..28.3...8.1....3.18.97....6...2....71...6...3.....8...6....58.53.....",
"2...3..966...948..4...15..2..6......9.5.....4....516...82...369....6..7.3..58....",
".3.4.......9..7..4.862.9....5..4..12...8...7...76...93.9....2.7.......6816.......",
"2...3..5.5..8.24........7.6.1..5.....6...3...3.2197...8.5...........1..493....2..",
".9...53...7..2.....4.38.5..3...41.6.....5.7.2..9.....84...9..71.8.1..64..6.8.....",
".....5.69..3..6.8.....78..23.....2...79......2.8.3....7.58.2.3.61.5...........19.",
"..93..7..85............63.221.6...5.7..8......4.....2.96.2.......75.8.4.5...6.93.",
".475....22..1.8.3....3..49.1.9.2.....2.4.........3..7.47....85.6..7.9.1....8.4..7",
"....24...4.3.5..7...2..3.........42...6.4..398..9........37961...916..45.7...5...",
".45....3..683.9......2.8..4.7..9......9..26......3..5..9....8.5.1.......3..415...",
"..8...92...6.32...5.....78...17..2...3....4...2...8..5....4..7175...1......27..69",
"..638....1.....3.98.71.....9..5......6.84.2.73.....6.545..1...66..4.3.....9.5..4.",
".8.35.9..7...81.....6....1....938.4...12....9.......3.4...932.7.9...2..16.....4.5",
".5......781.3.....2..7.415..8.2..4..4.....3.1..1.65..89..5..7.....63..8.......632",
"72..984...95...7......4..5.95..8...21......6.....7.3..3897..5......3.2.....8.1..9",
"...95.8.........4.341...7..19..7.2...2.5....3......4.5.5....124.74.9.3688..2.....",
};