Determining valid values for a given cell

A valid value for a given sudoku cell is values that are absent in the row, column and the block where the cell belongs. Any values that exist in those 3 regions are forbidden values. To illustrate the 3 regions, please refer to the picture below for cell (1, 1).

• Forbidden values row is highlighted with green
• Forbidden values column is highlighted with yellow
• Forbidden values for the block is highlighted with red

sudoku forbidden value regions

Looking at the picture above, for cell (1, 1) the forbidden values are 1, 3, 4. 5. 7, 9; thus the allowable values for cell (1, 1) are 2, 6 and 8. To get the allowable values in SQL, we’ll need to get all legal values and remove forbidden values. We can use LEFT JOIN to achieve it.

SELECT nums.* FROM
	nums
	LEFT JOIN (
		SELECT * FROM sudoku WHERE x_col = 1 OR y_col = 1
		UNION
		SELECT * FROM sudoku WHERE x_col BETWEEN 1 AND 3
			AND y_col BETWEEN 1 AND 3
	) AS forbidden_values ON forbidden_values.val = nums.num
WHERE
	forbidden_values.val IS NULL

Making the SQL generic

The SQL above works for cell (1, 1). To make it generic for all x and y values, we need to find out some kind of relationship between x and y and the row, column and block. Here’s all the possible values for any given x and y values.

Looking at the table above, we can see that the forbidden row and column regions are simply the same value as the x or y for the cell. The block region is rather tricky, I think. Here’s the summary:

1. For x or y values 1, 2 and 3, the block’s x or y coordinate is 1
2. For x or y values 4, 5 and 6, the block’s x or y coordinate is 4
3. For x or y values 7, 8 and 9, the block’s x or y coordinate is 7

To map values 1, 2 and 3 to 1, one way to do it is to subtract 1 from the values then integer divide the result then add 1 to it. Thus, we have:

1. (1 – 1) / 3 = 0; 0 + 1 = 1
2. (2 – 1) / 3 = 0; 0 + 1 = 1
3. (3 – 1) / 3 = 0; 0 + 1 = 1

To make the values work for 4, 5, 6 we can add 3 to the result. For 7, 8, 9, we add 6. In other words,

1. For 4, 5, 6, we add 1 * 3 to the result.
2. For 6, 7, 8, we add 2 * 3 to the result.
3. We can even extend this for 1, 2, 3, we add 0 * 3 to the result.

Now that we know to get block x values, getting the block y values should be pretty easy; it is x values + 2. In the formula above, to get y, we can add 3 instead of 1. Well, now that we have a consistent way in getting the result, let’s modify the formula above to a generic form:

For x : ( 3 * ((x – 1) / 3)) + 1
For y : ( 3 * ((x – 1) / 3)) + 3

Final SQL statement for getting legal values

Now that we know how to make it generic, let’s plug it in for the SQL statement we have in the beginning of this page. Assume x and y on the SQL below is a variable.

SELECT nums.* FROM
	nums
	LEFT JOIN (
		SELECT * FROM sudoku WHERE x_col = 1 OR y_col = 1
		UNION
		SELECT * FROM sudoku WHERE x_col BETWEEN (3 * FLOOR((x  - 1)/ 3)) + 1 AND (3 * FLOOR((x  - 1)/ 3)) + 3
			AND y_col BETWEEN (3 * FLOOR((y  - 1)/ 3)) + 1 AND (3 * FLOOR((y  - 1)/ 3)) + 3
	) AS forbidden_values ON forbidden_values.val = nums.num
WHERE
	forbidden_values.val IS NULL

Now that we know how to get legal values for the cell, let’s turn to the next page for algorithm for solving sudoku.