R Programming

Sudoku

Helper functions

M_ind converts between single matrix index and x,y indices

# convert single index v_i to i,j 
M_ind <- function(v_i) {
  i = 9 # dim of sudoku
  i_m = ifelse(v_i%%i,v_i%%i,i)
  return(c(i_m,ceiling(v_i/i)))
}

Getting the 3x3 “boxes” of the sudoku:

# create boxes
boxes <- matrix(
  sapply(list(1:3,4:6,7:9),rep,3,each=3),
  9,byrow = TRUE
)

Logic

Checking if the number at x,y is unique in its row, column and box.

is_valid <- function(X,Y,board,boxes) {
  box   <- boxes[X,Y] 
  if (any(duplicated(board[X,],incomparables = 0))) {
    return(FALSE)
  } else if (any(duplicated(board[,Y],incomparables = 0))) {
    return(FALSE)
  } else if (any(duplicated(board[boxes==box],incomparables = 0))){
    return(FALSE)
  } else {
    return(TRUE)
  } 
}

Now the depth first search algorithm.

solve_sudoku <- function(sudoku) {
  empty = which(sudoku == 0) # obtain empty pos
  S = length(empty) + 1      # steps
  N = 1                      # Step
  while (N < S) {
    i = M_ind(empty[N])      # row; col index of empty pos
    while (TRUE) {
    sudoku[empty[N]] = sudoku[empty[N]] + 1
    check = is_valid(X=i[1],Y=i[2],board=sudoku,boxes = boxes) 
    if(sudoku[empty[N]] > 9){
        sudoku[empty[N]] = 0 # reset
        N = N - 1            # go back
        break
      }
    if(check) {
        N = N + 1           # proceed
        break
      }
    }
  }
  return(sudoku)
}

Testing

Lets test the implementation on three example sudoku with increasing difficulty

6	5	2				9
				6				8
	9		2				7
2		9	3		1
1		7		5		3		4
			4		9	8		2
	6				7		2
3				9
		4				6	5	9

		1			5	8
2	8				3		7
			4	2
	1
				5			4
8	3		9			5
9	5		3			4
					7			6
		2

		5	3
8							2
	7			1		5
4					5	3
	1			7				6
		3	2				8
	6		5					9
		4					3
					9	7

The left one is rather easy, the middle one medium and the right one is made by the Finnish Mathematician Inkala and is very hard to solve.

Lets run it:

6	5	2	7	3	8	9	4	1
4	7	1	9	6	5	2	3	8
8	9	3	2	1	4	5	7	6
2	4	9	3	8	1	7	6	5
1	8	7	6	5	2	3	9	4
5	3	6	4	7	9	8	1	2
9	6	8	5	4	7	1	2	3
3	2	5	1	9	6	4	8	7
7	1	4	8	2	3	6	5	9

4	9	1	7	6	5	8	3	2
2	8	5	1	9	3	6	7	4
3	7	6	4	2	8	1	9	5
5	1	7	6	3	4	2	8	9
6	2	9	8	5	1	7	4	3
8	3	4	9	7	2	5	6	1
9	5	8	3	1	6	4	2	7
1	4	3	2	8	7	9	5	6
7	6	2	5	4	9	3	1	8

1	4	5	3	2	7	6	9	8
8	3	9	6	5	4	1	2	7
6	7	2	9	1	8	5	4	3
4	9	6	1	8	5	3	7	2
2	1	8	4	7	3	9	5	6
7	5	3	2	9	6	4	8	1
3	6	7	5	4	2	8	1	9
9	8	4	7	6	1	2	3	5
5	2	1	8	3	9	7	6	4

we get the solution to all three lvls of sudoku!

How long did this approach take to come up with the solutions?

microbenchmark::microbenchmark(
  solve_sudoku(easy),
  solve_sudoku(medium),
  solve_sudoku(Inkala),
  times = 1
)

Unit: milliseconds
                 expr        min         lq       mean     median         uq        max neval
   solve_sudoku(easy)   42.17106   42.17106   42.17106   42.17106   42.17106   42.17106     1
 solve_sudoku(medium)  154.17445  154.17445  154.17445  154.17445  154.17445  154.17445     1
 solve_sudoku(Inkala) 2733.38598 2733.38598 2733.38598 2733.38598 2733.38598 2733.38598     1

Thats it!