Rene Kita's weblog

Blog[0] About[1] RSS[2] Links[3]

ksudbf - A Command Line Killer Sudoku Solver

2022-01-03

ksudbf[4] is a command-line solver for killer sudoku puzzles. In this blog posts I explain how to use it.

Let's take this puzzle[5]

An empty killer sudoku puzzle[6]

First of all we want the coordinates in our puzzle file to ease inputting the cell coordinates:

	$ sed -n '/shows all coordinates/,/^$/{/shows all coordinates/!p;}' \
	README > puzzle

ksudbf will ignore all lines starting with a | or a #. It will also ignore empty lines. Use this to make your editing easier.

Open the puzzle file in your editor, it should look like this:

	|----------+----------+----------|
	| 11 12 13 | 14 15 16 | 17 18 19 |
	| 21 22 23 | 24 25 26 | 27 28 29 |
	| 31 32 33 | 34 35 36 | 37 38 39 |
	|----------+----------+----------|
	| 41 42 43 | 44 45 46 | 47 48 49 |
	| 51 52 53 | 54 55 56 | 57 58 59 |
	| 61 62 63 | 64 65 66 | 67 68 69 |
	|----------+----------+----------|
	| 71 72 73 | 74 75 76 | 77 78 79 |
	| 81 82 83 | 84 85 86 | 87 88 89 |
	| 91 92 93 | 94 95 96 | 97 98 99 |
	|----------+----------+----------|

Start in the upper left corner, append the sum of the cage followed by all coordinates after the last line:

	3 11 12

The first number is the sum of the cage, all following numbers are coordinates.

Scan the first row for the next cage:

	3 11 12
	15 13 14 15
	22 16 25 26 35
	4 17 27
	16 18 28
	15 19 29 39 49

Continue scanning all rows, adding all cages not already added. You can find the complete input file for this puzzle here[7].

Do an error check without spoiling the solution: With ed or vi:

	w !ksudbf >/dev/null

or leave the editor and do:

	$ ksudbf puzzle >/dev/null

You might see three kind of errors:

1) _Invalid cell coordinate XY_

You mistyped a coordinate.

2) _Cell XY seen N times_

The cell with coordinate XY was seen N times instead of exactly once.

3) _Sum of all cages N, expected 405_

One or more cages have the wrong sum.

If you see an error, double check your input file and repeat the error check.

Now, either show the complete solution with ksudbf puzzle or open both the puzzle file and the solution with ksudhints:

	$ ksudhints -p puzzle -s <(ksudbf <puzzle)

You will be greeted with a summary how to use it:

	Commands:
	[r] XY	- Reveal cell XY (where XY is a valid coordinate).
	n [N]	- Show 1 or N next hints.
	p	- Print the board.
	s	- Show a table with all coordinates.
	e	- Open the board in $EDITOR (to add values to the partial solution).

	Press <Enter> without command to repeat the previous N commands.
	Press ^D to see the complete solution and exit.

Let's assume we already have a partial solution, press e to edit the current state. You'll see an empty grid in your editor:

	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .
	------+-------+------
	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .
	------+-------+------
	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .

Each dot represents a cell without value. Replace it with the value you got in your solution:

	. . . | . . . | . 9 8
	3 . . | . . . | . . .
	. . . | . . . | . . .
	------+-------+------
	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .
	------+-------+------
	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .

Save and quit. Press p to see your changes applied to the partial solution. ksudhints checks your input against the solution and will ignore wrong values.

To reveal a specific cell just enter the coordinate:

	34
	. . . | . . . | . 9 8
	3 . . | . . . | . . .
	. . . | 3 . . | . . .
	------+-------+------
	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .
	------+-------+------
	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .
	Cell 34: 3

Enter n to reveal the next value:

	n
	2 . . | . . . | . 9 8
	3 . . | . . . | . . .
	. . . | 3 . . | . . .
	------+-------+------
	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .
	------+-------+------
	. . . | . . . | . . .
	. . . | . . . | . . .
	. . . | . . . | . . .
	Cell 11: 2

ksudbf looks for the next cage with the smallest number of cells which is not fully filled and reveals the first unfilled cell.

Continue using n to show more. Use n 2 to show the next two values. Use e to add what you solved yourself.

If you have questions or general feedback send me an email[8] or join #rkta[9] on libera.org[10].

Last modified: 2023-09-07T05:31:20Z

E-mail: mail@rkta.de[11] IRC: #rkta[12] on Libera.Chat[13]

[6] An empty killer sudoku puzzle