Codewars
https://www.codewars.com/kata/validate-sudoku-with-size-nxn/python
Given a Sudoku data structure with size NxN, N > 0 and √N == integer, write a method to validate if it has been filled out correctly.
The data structure is a multi-dimensional Array(in Rust: Vec<Vec<u32>>) , ie:
[
[7,8,4, 1,5,9, 3,2,6],
[5,3,9, 6,7,2, 8,4,1],
[6,1,2, 4,3,8, 7,5,9],
[9,2,8, 7,1,5, 4,6,3],
[3,5,7, 8,4,6, 1,9,2],
[4,6,1, 9,2,3, 5,8,7],
[8,7,6, 3,9,4, 2,1,5],
[2,4,3, 5,6,1, 9,7,8],
[1,9,5, 2,8,7, 6,3,4]
]
Rules for validation
- Data structure dimension:
NxNwhereN > 0and√N == integer - Rows may only contain integers:
1..N (N included) - Columns may only contain integers:
1..N (N included) - ‘Little squares’ (
3x3in example above) may also only contain integers:1..N (N included)
Martin’s comment
To be perfectly honest I have never played the sudoku. So firstly I had to learn a how to play it from Sudoku.com, and later solve the problem. My solution is definetely not the shortest nor ideal one but it works. I had saved a lot of work and issues using NumPy library in Python which I would like to learn more deeply.
Below is my solution.
Martin’s solution
import numpy, math
class Sudoku(object):
def __init__(self, m):
self.matrix = numpy.matrix(m)
def is_valid(self):
self.mysum = sum(x for x in range(1,len(self.matrix)+1))
self.mylen = int(math.sqrt(len(self.matrix)))
# iterate over submatrixes
for x in range(0,self.mylen):
for y in range(0, self.mylen):
submatrix = self.matrix[x*self.mylen:x*self.mylen+self.mylen,y*self.mylen:y*self.mylen+self.mylen]
for i in range(1,self.mylen):
if i not in submatrix.A1.tolist():
return False
if numpy.sum(submatrix) != self.mysum:
return False
results = self.numpy_lines(1) + self.numpy_lines(0) # rows + columns parsing
for result in results:
if not result:
return False
return True
def line_sudoku(self, line):
line = line.tolist()[0]
if sum(line) != self.mysum:
return False
for i in range(1, self.mylen):
if i not in line:
return False
return True
def numpy_lines(self,axis):
return numpy.apply_along_axis(self.line_sudoku, axis = axis, arr = self.matrix).tolist()
goodSudoku = Sudoku([
[1,4, 2,3],
[3,2, 4,1],
[4,1, 3,2],
[2,3, 1,4]
])
print(goodSudoku.is_valid())
Tests
# Valid Sudoku
goodSudoku1 = Sudoku([
[7,8,4, 1,5,9, 3,2,6],
[5,3,9, 6,7,2, 8,4,1],
[6,1,2, 4,3,8, 7,5,9],
[9,2,8, 7,1,5, 4,6,3],
[3,5,7, 8,4,6, 1,9,2],
[4,6,1, 9,2,3, 5,8,7],
[8,7,6, 3,9,4, 2,1,5],
[2,4,3, 5,6,1, 9,7,8],
[1,9,5, 2,8,7, 6,3,4]
])
goodSudoku2 = Sudoku([
[1,4, 2,3],
[3,2, 4,1],
[4,1, 3,2],
[2,3, 1,4]
])
# Invalid Sudoku
badSudoku1 = Sudoku([
[0,2,3, 4,5,6, 7,8,9],
[1,2,3, 4,5,6, 7,8,9],
[1,2,3, 4,5,6, 7,8,9],
[1,2,3, 4,5,6, 7,8,9],
[1,2,3, 4,5,6, 7,8,9],
[1,2,3, 4,5,6, 7,8,9],
[1,2,3, 4,5,6, 7,8,9],
[1,2,3, 4,5,6, 7,8,9],
[1,2,3, 4,5,6, 7,8,9]
])
badSudoku2 = Sudoku([
[1,2,3,4,5],
[1,2,3,4],
[1,2,3,4],
[1]
])
Test.it('should be valid')
Test.assert_equals(goodSudoku1.is_valid(), True, 'Testing valid 9x9')
Test.assert_equals(goodSudoku2.is_valid(), True, 'Testing valid 4x4')
Test.it ('should be invalid')
Test.assert_equals(badSudoku1.is_valid(), False, 'Values in wrong order')
Test.assert_equals(badSudoku2.is_valid(), False, '4x5 (invalid dimension)')
