Sudoku¶
Note
This is a harder problem. Some basic details may be left out of the language-specific notes as a result to make room for the code itself and finer or newer necessary details.
Sudoku is a Japanese number game that can be found in newspapers and publications internationally. The game features a nine-by-nine grid with some numbers filled in to begin. The goal of the game is to complete the grid such that every row and every column contain the numbers one through nine exclusively, and every adjacent three-by-three grid also contains all numbers one through nine. Here is an example:
The initial puzzle is on the left and the solved puzzle is on the right.
The goal of our program, of course, is to solve any solvable sudoku puzzle. This type of problem is sometimes called a constraint problem or a cover problem in mathematics. There are many solutions to this problem, but we will be focusing on the solution commonly known as “backtracking”. The general idea is to find an empty square, place a valid digit, and continue that until there is a square with no valid digits. In that case, go back and change digits until there is a valid digit for that square. Repeat this until all squares in the grid contain valid digits, and the puzzle is solved. So, to reiterate, we are trying something repeatedly that changes based off of whether future actions are successful. This would look like a recursive function that returns true or false:
Find the next position in our 2D array which is not filled in (has zero as a value, in our case)
Iterate through numbers one through nine checking if they are present in that same row, column, or 3x3 square
In the case that there is a valid number, place it there and repeat (call this same function recursively to fill in another square, waiting for a true / false value from this future call to determine whether to try more numbers)
In the case that there isn’t a valid number, return false and continue with the previous step in the previous call
Have a condition at the beginning of this function that returns true if there are no empty squares
This process would look something like this:
This is a hard recursive problem, so it’s encouraged to read the above summary carefully as well as the code. After you think you understand the concept, try finding where each step is occuring in the code.
Also, I believe this is the first use of a “multidimensional” array on this site. Just think of it as an array of arrays. In fact, typically you can replace part of its statements so that it looks like a normal array with usual commands. E.g. Instead of array[x][y], think of array[x] as arrayRow, then arrayRow[y]. Review the Preferred Arrays page for these.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool sudokuSolve(vector<vector<int>> &board){
bool solved = true;
int row = 0;
int column = 0;
for(int i = 0; i < board.size(); i++){
if(!solved)
break;
for(int j = 0; j < board[0].size(); j++){
if (board[i][j] == 0){
solved = false;
row = i;
column = j;
break;
}
}
}
if(solved)
return true;
for(int i = 1; i < 10; i++){
if(find(board[row].begin(), board[row].end(), i) == board[row].end()) {
for(int j = 0; j < board.size(); j++){
if (board[j][column] == i)
goto numberFound;
}
int block_row = (row / 3) * 3;
int block_column = (column / 3) * 3;
for(int j = 0; j < 3; j++){
for(int k = 0; k < 3; k++){
if (board[block_row + j][block_column + k] == i)
goto numberFound;
}
}
board[row][column] = i;
if (sudokuSolve(board))
return true;
board[row][column] = 0;
}
numberFound: ;
}
return false;
}
void printBoard(vector<vector<int>> &board){
for(int row = 0; row < board.size(); row++){
for(int column = 0; column < board[0].size(); column++){
cout << board[row][column] << " ";
if ((column + 1) % 3 == 0)
cout << " ";
}
cout << endl;
if ((row + 1) % 3 == 0)
cout << endl;
}
}
int main() {
vector<vector<int>> board = { {7, 0, 0, 0, 0, 9, 0, 0, 3}, // c++ 11
{0, 9, 0, 1, 0, 0, 8, 0, 0},
{0, 1, 0, 0, 0, 7, 0, 0, 0},
{0, 3, 0, 4, 0, 0, 0, 8, 0},
{6, 0, 0, 0, 8, 0, 0, 0, 1},
{0, 7, 0, 0, 0, 2, 0, 3, 0},
{0, 0, 0, 5, 0, 0, 0, 1, 0},
{0, 0, 4, 0, 0, 3, 0, 9, 0},
{5, 0, 0, 7, 0, 0, 0, 0, 2} };
printBoard(board);
if(sudokuSolve(board))
cout << "Board solved" << endl;
else
cout << "Impossible board" << endl;
printBoard(board);
}
using System.Collections.Generic;
class Program {
static bool sudokuSolve(List<List<int>> board){
bool solved = true;
int row = 0;
int column = 0;
for(int i = 0; i < board.Count; i++){
if(!solved)
break;
for(int j = 0; j < board[0].Count; j++){
if (board[i][j] == 0){
solved = false;
row = i;
column = j;
break;
}
}
}
if(solved)
return true;
for(int i = 1; i < 10; i++){
if(!board[row].Contains(i)){
for(int j = 0; j < board.Count; j++){
if (board[j][column] == i)
goto numberFound;
}
int block_row = (row / 3) * 3;
int block_column = (column / 3) * 3;
for(int j = 0; j < 3; j++){
for(int k = 0; k < 3; k++){
if (board[block_row + j][block_column + k] == i)
goto numberFound;
}
}
board[row][column] = i;
if (sudokuSolve(board))
return true;
board[row][column] = 0;
}
numberFound: ;
}
return false;
}
static void printBoard(List<List<int>> board){
for(int row = 0; row < board.Count; row++){
for(int column = 0; column < board[0].Count; column++){
System.Console.Write("{0} ", board[row][column]);
if ((column + 1) % 3 == 0)
System.Console.Write(" ");
}
System.Console.WriteLine(" ");
if ((row + 1) % 3 == 0)
System.Console.WriteLine(" ");
}
}
static void Main(string[] args)
{
List<List<int>> board = new List<List<int>>
{ new List<int> {7, 0, 0, 0, 0, 9, 0, 0, 3},
new List<int> {0, 9, 0, 1, 0, 0, 8, 0, 0},
new List<int> {0, 1, 0, 0, 0, 7, 0, 0, 0},
new List<int> {0, 3, 0, 4, 0, 0, 0, 8, 0},
new List<int> {6, 0, 0, 0, 8, 0, 0, 0, 1},
new List<int> {0, 7, 0, 0, 0, 2, 0, 3, 0},
new List<int> {0, 0, 0, 5, 0, 0, 0, 1, 0},
new List<int> {0, 0, 4, 0, 0, 3, 0, 9, 0},
new List<int> {5, 0, 0, 7, 0, 0, 0, 0, 2} };
printBoard(board);
if(sudokuSolve(board))
System.Console.WriteLine("Board solved");
else
System.Console.WriteLine("Impossible board");
printBoard(board);
}
}
import java.util.*;
public class sudokuBacktrack {
public static boolean sudokuSolve(List<List<Integer>> board){
boolean solved = true;
int row = 0;
int column = 0;
for(int i = 0; i < board.size(); i++){
if(!solved)
break;
for(int j = 0; j < board.get(0).size(); j++){
if (board.get(i).get(j) == 0){
solved = false;
row = i;
column = j;
break;
}
}
}
if(solved)
return true;
numberFound:
for(int i = 1; i < 10; i++){
if(!board.get(row).contains(i)){
for(int j = 0; j < board.size(); j++){
if (board.get(j).get(column) == i)
continue numberFound;
}
int block_row = (row / 3) * 3;
int block_column = (column / 3) * 3;
for(int j = 0; j < 3; j++){
for(int k = 0; k < 3; k++){
if (board.get(block_row + j).get(block_column + k) == i)
continue numberFound;
}
}
board.get(row).set(column, i);
if (sudokuSolve(board))
return true;
board.get(row).set(column, 0);
}
}
return false;
}
static void printBoard(List<List<Integer>> board){
for(int row = 0; row < board.size(); row++){
for(int column = 0; column < board.get(0).size(); column++){
System.out.print(board.get(row).get(column) + " ");
if ((column + 1) % 3 == 0)
System.out.print(" ");
}
System.out.println(" ");
if ((row + 1) % 3 == 0)
System.out.println(" ");
}
}
public static void main(String[] args) {
List<List<Integer>> board = new ArrayList<List<Integer>> ();
board.add(Arrays.asList(7, 0, 0, 0, 0, 9, 0, 0, 3));
board.add(Arrays.asList(0, 9, 0, 1, 0, 0, 8, 0, 0));
board.add(Arrays.asList(0, 1, 0, 0, 0, 7, 0, 0, 0));
board.add(Arrays.asList(0, 3, 0, 4, 0, 0, 0, 8, 0));
board.add(Arrays.asList(6, 0, 0, 0, 8, 0, 0, 0, 1));
board.add(Arrays.asList(0, 7, 0, 0, 0, 2, 0, 3, 0));
board.add(Arrays.asList(0, 0, 0, 5, 0, 0, 0, 1, 0));
board.add(Arrays.asList(0, 0, 4, 0, 0, 3, 0, 9, 0));
board.add(Arrays.asList(5, 0, 0, 7, 0, 0, 0, 0, 2));
printBoard(board);
if(sudokuSolve(board))
System.out.println("Board solved");
else
System.out.println("Impossible board");
printBoard(board);
}
}
function sudokuSolve(board){
var solved = true;
var row = 0;
var column = 0;
for(var rw = 0; rw < board.length; rw++){
if(!solved)
break;
for(var clmn = 0; clmn < board[0].length; clmn++){
if (board[rw][clmn] === 0){
solved = false;
row = rw;
column = clmn;
break;
}
}
}
if (solved)
return true;
numberFound:
for(var num = 1; num < 10; num++){
if(board[row].indexOf(num) <= -1){
for(var i = 0; i < board.length; i++){
if(board[i][column] === num)
continue numberFound;
}
var block_row = Math.floor(row / 3) * 3;
var block_column = Math.floor(column / 3) * 3;
for(var i = 0; i < 3; i++){
for(var j = 0; j < 3; j++){
if (board[block_row + i][block_column + j] === num)
continue numberFound;
}
}
board[row][column] = num;
if (sudokuSolve(board))
return true;
board[row][column] = 0;
}
}
return false;
}
function printBoard(board){
var boardStr = "";
for(var row = 0; row < board.length; row++){
for (var column = 0; column < board[0].length; column++){
boardStr += board[row][column] + " ";
if ((column + 1) % 3 === 0)
boardStr += " ";
}
boardStr += "\n";
if ((row + 1) % 3 === 0)
boardStr += "\n";
}
console.log(boardStr);
}
var board = [ [7, 0, 0, 0, 0, 9, 0, 0, 3],
[0, 9, 0, 1, 0, 0, 8, 0, 0],
[0, 1, 0, 0, 0, 7, 0, 0, 0],
[0, 3, 0, 4, 0, 0, 0, 8, 0],
[6, 0, 0, 0, 8, 0, 0, 0, 1],
[0, 7, 0, 0, 0, 2, 0, 3, 0],
[0, 0, 0, 5, 0, 0, 0, 1, 0],
[0, 0, 4, 0, 0, 3, 0, 9, 0],
[5, 0, 0, 7, 0, 0, 0, 0, 2] ];
printBoard(board);
if (sudokuSolve(board))
console.log("Board solved");
else
console.log("Impossible board");
printBoard(board);
def sudokuSolve(board):
solved = True
row = 0
column = 0
for rw in range(len(board)):
if not solved:
break
for clmn in range(len(board[0])):
if board[rw][clmn] == 0:
solved = False
row = rw
column = clmn
break
if solved:
return True
for num in range(1, 10):
if num not in board[row] and num not in [row[column] for row in board]:
block_row = (row // 3) * 3
block_column = (column // 3) * 3
if all( board[block_row + i][block_column + j] != num
for i in range(3) for j in range(3) ):
board[row][column] = num
if sudokuSolve(board):
return True
board[row][column] = 0
return False
def printBoard(board):
for row in range(len(board)):
for column in range(len(board[0])):
print(board[row][column], end=" ")
if ((column + 1) % 3) == 0:
print(" ", end="")
print(" ")
if ((row + 1) % 3) == 0:
print(" ")
board = [ [7, 0, 0, 0, 0, 9, 0, 0, 3],
[0, 9, 0, 1, 0, 0, 8, 0, 0],
[0, 1, 0, 0, 0, 7, 0, 0, 0],
[0, 3, 0, 4, 0, 0, 0, 8, 0],
[6, 0, 0, 0, 8, 0, 0, 0, 1],
[0, 7, 0, 0, 0, 2, 0, 3, 0],
[0, 0, 0, 5, 0, 0, 0, 1, 0],
[0, 0, 4, 0, 0, 3, 0, 9, 0],
[5, 0, 0, 7, 0, 0, 0, 0, 2] ]
printBoard(board)
if sudokuSolve(board):
print("Board solved")
else:
print("Impossible board")
printBoard(board)
func sudokuSolve(_ board: inout [[Int]]) -> Bool {
var solved = true
var row = 0
var column = 0
for rw in 0..<board.count{
if !solved{
break
}
for clmn in 0..<board[0].count{
if board[rw][clmn] == 0{
solved = false
row = rw
column = clmn
break
}
}
}
if solved{
return true
}
numberFound:
for num in 0...9{
if !board[row].contains(num){
for i in 0..<board.count{
if board[i][column] == num{
continue numberFound
}
}
let block_row = (row / 3) * 3
let block_column = (column / 3) * 3
for i in 0..<3{
for j in 0..<3{
if board[block_row + i][block_column + j] == num{
continue numberFound
}
}
}
board[row][column] = num
if sudokuSolve(&board){
return true
}
board[row][column] = 0
}
}
return false
}
func printBoard(_ board: [[Int]]) {
for row in 0..<board.count{
for column in 0..<board[0].count{
print(board[row][column], terminator:" ")
if (column + 1) % 3 == 0{
print(" ", terminator:"")
}
}
print(" ")
if (row + 1) % 3 == 0{
print(" ")
}
}
}
var board = [ [7, 0, 0, 0, 0, 9, 0, 0, 3],
[0, 9, 0, 1, 0, 0, 8, 0, 0],
[0, 1, 0, 0, 0, 7, 0, 0, 0],
[0, 3, 0, 4, 0, 0, 0, 8, 0],
[6, 0, 0, 0, 8, 0, 0, 0, 1],
[0, 7, 0, 0, 0, 2, 0, 3, 0],
[0, 0, 0, 5, 0, 0, 0, 1, 0],
[0, 0, 4, 0, 0, 3, 0, 9, 0],
[5, 0, 0, 7, 0, 0, 0, 0, 2] ]
printBoard(board)
if sudokuSolve(&board){
print("Board solved")
}else{
print("Impossible board")
}
printBoard(board)
Notes¶
The line #include <vector> is needed to use vectors.
The line #include <algorithm> is needed to use the find function.
goto is a keyword in c++ usually frowned upon, however this is a valid use, namely
breaking out of a nested loop (loop within a loop). The syntax is there is a “label” somewhere with the
syntax labelName:, and calling goto labelName; directs the compiler to skip to that line,
ignoring the usual order of execution.
Note
There is one line marked as C++ 11 here, so add “-std=c++11” after “g++” when compiling if it doesn’t work.
The line using System.Collections.Generic; is needed to use Lists.
goto is a keyword in c++ usually frowned upon, however this is a valid use, namely
breaking out of a nested loop (loop within a loop). The syntax is there is a “label” somewhere with the
syntax labelName:, and calling goto labelName; directs the compiler to skip to that line,
ignoring the usual order of execution.
The line import java.util.*; is needed to use Lists.
The continue keyword can be used to continue an outer loop from inside a nested loop (loop inside
a loop). To do this, the outer loop is given a “label” with the syntax labelName: right before the
loop statement. Then, when calling continue from the nested loop, the syntax continue labelName;
is used.
The continue keyword can be used to continue an outer loop from inside a nested loop (loop inside
a loop). To do this, the outer loop is given a “label” with the syntax labelName: right before the
loop statement. Then, when calling continue from the nested loop, the syntax continue labelName;
is used.
The line with [row[column] for row in board] uses what is known in Python as “list comprehension”.
The idea is to make a list (array) with a loop in a compact way, as opposed to declaring a list and then
defining a loop to add the list’s contents. The syntax is [operationOnValue for Value in List],
which gives the list containing every operationOnValue. This saves a few lines.
The line all( board[block_row + i][block_column + j] != num for i in range(3) for j in range(3) )
has a similar syntax to the list comprehension previously. Firstly, the all function in python
returns true if all elements in a list are true, and false otherwise. This leaves the list comprehension
on the inside - it has the same syntax as before, however list comprehension allows nested for loops (in the
same line!). This means that on top of whatever loop statement “x” there was previously, you can add an
x for ... in ... on top of it. Normally this makes the most sense with seperate variables, such as
“i” and “j” here. This line is specifically checking whether a number is present in a specific 3x3 grid.
The inout modifier is used on a function parameter to make it call by reference. An ampersand
(&) is then needed in the function call(s) to use the memory address of the variable.
The continue keyword can be used to continue an outer loop from inside a nested loop (loop inside
a loop). To do this, the outer loop is given a “label” with the syntax labelName: right before the
loop statement. Then, when calling continue from the nested loop, the syntax continue labelName
is used.
There are only “range-based for loops” in swift. To use it like a normal for loop, give it a range with the syntax
0..<number in place of the array, where 0 is the starting index and number is the index it
stops short of. ..< means it stops short of the number and ... means it stops at the number.
When printing to the console with print, the terminator parameter can be changed to replace the
default newline (\n).
There’s also a convoluted four-line version. And a faster version.