1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
<<-DOC
Sudoku is a number-placement puzzle.
The objective is to fill a 9 × 9 grid with numbers in such a way that each column, each row,
and each of the nine 3 × 3 sub-grids that compose the grid all contain all of the numbers from 1 to 9 one time.
Implement an algorithm that will check whether the given grid of numbers represents a valid
Sudoku puzzle according to the layout rules described above.
Note that the puzzle represented by grid does not have to be solvable.
Example
For
grid = [['.', '.', '.', '1', '4', '.', '.', '2', '.'],
['.', '.', '6', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '1', '.', '.', '.', '.', '.', '.'],
['.', '6', '7', '.', '.', '.', '.', '.', '9'],
['.', '.', '.', '.', '.', '.', '8', '1', '.'],
['.', '3', '.', '.', '.', '.', '.', '.', '6'],
['.', '.', '.', '.', '.', '7', '.', '.', '.'],
['.', '.', '.', '5', '.', '.', '.', '7', '.']]
the output should be
sudoku2(grid) = true;
For
grid = [['.', '.', '.', '.', '2', '.', '.', '9', '.'],
['.', '.', '.', '.', '6', '.', '.', '.', '.'],
['7', '1', '.', '.', '7', '5', '.', '.', '.'],
['.', '7', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '8', '3', '.', '.', '.'],
['.', '.', '8', '.', '.', '7', '.', '6', '.'],
['.', '.', '.', '.', '.', '2', '.', '.', '.'],
['.', '1', '.', '2', '.', '.', '.', '.', '.'],
['.', '2', '.', '.', '3', '.', '.', '.', '.']]
the output should be
sudoku2(grid) = false.
The given grid is not correct because there are two 1s in the second column.
Each column, each row, and each 3 × 3 subgrid can only contain the numbers 1 through 9 one time.
Input/Output
[time limit] 4000ms (rb)
[input] array.array.char grid
A 9 × 9 array of characters, in which each character is either a digit from '1' to '9' or a period '.'.
[output] boolean
Return true if grid represents a valid Sudoku puzzle, otherwise return false.
THINK
If i grab each number in the matrix and store it's coordinate can I come up with a formula for
checking the appropriate indexes to see if there is a duplicate on the same row, column or 3x3 grid.
2 => [0, 4] => [[0, 3], [0, 5], [1, 3], [1, 4], [1, 5]]
9 => [0, 7]
6 => [1, 4] => [[0, 3], [0, 4], [0, 5], [1, 3], [1, 5], [2, 3], [2, 4], [2, 5]]
7 => [2, 0]
1 => [2, 1]
7 => [2, 4]
5 => [2, 5]
7 => [3, 1]
8 => [4, 4]
3 => [4, 5]
8 => [5, 2]
7 => [5, 4]
6 => [5, 7]
2 => [6, 5]
1 => [7, 1]
2 => [7, 3]
2 => [8, 1]
3 => [8, 4]
1 |2 | 4 |8
2^0|2^1|2^2|2^3|
DOC
describe "sudoku2" do
def duplicates?(items)
hash = {}
items.reject { |x| x == 0 || x == "." }.each do |item|
return true if hash[item]
hash[item] = true
end
false
end
def sudoku2(grid)
columns = 0.upto(8).map { |x| [x, []] }.to_h
# find duplicates in each row
0.upto(8) do |i|
row = grid[i].map(&:to_i)
return false if duplicates?(row.reject { |x| x == 0 })
row.each_with_index do |x, column|
columns[column].push(x.to_i) unless x == 0
end
end
# find duplicates in each column
columns.each do |key, column|
return false if duplicates?(column)
end
# find duplicates in each 3x3 grid
#PP.pp grid
row, column = 0, 0
until row > 8
section = grid[row][column...(column + 3)] +
grid[row + 1][column...(column + 3)] +
grid[row + 2][column...(column + 3)]
return false if duplicates?(section)
column += 3
if column > 8
column = 0
row += 3
end
end
true
end
def sudoku2(grid)
columns = Array.new(9) { Hash.new }
rows = Array.new(9) { Hash.new }
sub_grids = Array.new(9) { Hash.new }
9.times do |i|
9.times do |j|
value = grid[i][j].to_i
next if value.zero?
return false if rows[i].key?(value)
rows[i][value] = true
return false if columns[j].key?(value)
columns[j][value] = true
index = (i / 3) * 3 + (j / 3)
return false if sub_grids[index].key?(value)
sub_grids[index][value] = true
end
end
true
end
[
{ grid: [[".",".",".","1","4",".",".","2","."], [".",".","6",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".","1",".",".",".",".",".","."], [".","6","7",".",".",".",".",".","9"], [".",".",".",".",".",".","8","1","."], [".","3",".",".",".",".",".",".","6"], [".",".",".",".",".","7",".",".","."], [".",".",".","5",".",".",".","7","."]], expected: true },
{ grid: [[".",".",".",".","2",".",".","9","."], [".",".",".",".","6",".",".",".","."], ["7","1",".",".","7","5",".",".","."], [".","7",".",".",".",".",".",".","."], [".",".",".",".","8","3",".",".","."], [".",".","8",".",".","7",".","6","."], [".",".",".",".",".","2",".",".","."], [".","1",".","2",".",".",".",".","."], [".","2",".",".","3",".",".",".","."]], expected: false },
{ grid: [[".",".","4",".",".",".","6","3","."], [".",".",".",".",".",".",".",".","."], ["5",".",".",".",".",".",".","9","."], [".",".",".","5","6",".",".",".","."], ["4",".","3",".",".",".",".",".","1"], [".",".",".","7",".",".",".",".","."], [".",".",".","5",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."]], expected: false },
{ grid: [[".",".",".",".",".",".",".",".","2"], [".",".",".",".",".",".","6",".","."], [".",".","1","4",".",".","8",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".","3",".",".",".","."], ["5",".","8","6",".",".",".",".","."], [".","9",".",".",".",".","4",".","."], [".",".",".",".","5",".",".",".","."]], expected: true },
{ grid: [[".","9",".",".","4",".",".",".","."], ["1",".",".",".",".",".","6",".","."], [".",".","3",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".","7",".",".",".",".","."], ["3",".",".",".","5",".",".",".","."], [".",".","7",".",".","4",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".","7",".",".",".","."]], expected: true },
{ grid: [["7",".",".",".","4",".",".",".","."], [".",".",".","8","6","5",".",".","."], [".","1",".","2",".",".",".",".","."], [".",".",".",".",".","9",".",".","."], [".",".",".",".","5",".","5",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".","2",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."]], expected: false },
{ grid: [[".","4",".",".",".",".",".",".","."], [".",".","4",".",".",".",".",".","."], [".",".",".","1",".",".","7",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".","3",".",".",".","6","."], [".",".",".",".",".","6",".","9","."], [".",".",".",".","1",".",".",".","."], [".",".",".",".",".",".","2",".","."], [".",".",".","8",".",".",".",".","."]], expected: false },
{ grid: [[".",".","5",".",".",".",".",".","."], [".",".",".","8",".",".",".","3","."], [".","5",".",".","2",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","9"], [".",".",".",".",".",".","4",".","."], [".",".",".",".",".",".",".",".","7"], [".","1",".",".",".",".",".",".","."], ["2","4",".",".",".",".","9",".","."]], expected: false },
{ grid: [[".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".","9",".",".",".",".",".",".","1"], ["8",".",".",".",".",".",".",".","."], [".","9","9","3","5","7",".",".","."], [".",".",".",".",".",".",".","4","."], [".",".",".","8",".",".",".",".","."], [".","1",".",".",".",".","4",".","9"], [".",".",".","5",".","4",".",".","."]], expected: false },
{ grid: [[".",".",".","2",".",".","6",".","."], [".",".",".","1",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".","5",".","1",".",".","8"], [".","3",".",".",".",".",".",".","."], [".",".",".","9",".",".",".",".","3"], ["4",".",".",".",".",".",".",".","."], [".",".",".",".",".",".","3","8","."], [".",".",".",".",".",".",".",".","4"]], expected: true },
{ grid: [[".",".",".",".","8",".",".",".","."], [".",".",".",".",".",".","5",".","."], [".",".",".",".","4",".",".","2","."], [".",".",".","3",".","9",".",".","."], [".",".","1","8",".",".","9",".","."], [".",".",".",".",".","5","1",".","."], [".",".","3",".",".","8",".",".","."], [".","1","2",".","3",".",".",".","."], [".",".",".",".",".","7",".",".","1"]], expected: true },
{ grid: [[".",".",".",".",".",".","5",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], ["9","3",".",".","2",".","4",".","."], [".",".","7",".",".",".","3",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".","3","4",".",".",".","."], [".",".",".",".",".","3",".",".","."], [".",".",".",".",".","5","2",".","."]], expected: false },
{ grid: [[".",".",".",".","4",".","9",".","."], [".",".","2","1",".",".","3",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","3"], [".",".",".","2",".",".",".",".","."], [".",".",".",".",".","7",".",".","."], [".",".",".","6","1",".",".",".","."], [".",".","9",".",".",".",".",".","."], [".",".",".",".",".",".",".","9","."]], expected: true },
{ grid: [[".","8","7","6","5","4","3","2","1"], ["2",".",".",".",".",".",".",".","."], ["3",".",".",".",".",".",".",".","."], ["4",".",".",".",".",".",".",".","."], ["5",".",".",".",".",".",".",".","."], ["6",".",".",".",".",".",".",".","."], ["7",".",".",".",".",".",".",".","."], ["8",".",".",".",".",".",".",".","."], ["9",".",".",".",".",".",".",".","."]], expected: true },
{ grid: [[".",".",".",".",".",".",".",".","."], ["4",".",".",".",".",".",".",".","."], [".",".",".",".",".",".","6",".","."], [".",".",".","3","8",".",".",".","."], [".","5",".",".",".","6",".",".","1"], ["8",".",".",".",".",".",".","6","."], [".",".",".",".",".",".",".",".","."], [".",".","7",".","9",".",".",".","."], [".",".",".","6",".",".",".",".","."]], expected: true },
{ grid: [[".",".",".",".",".",".",".",".","1"], [".",".",".",".",".","6",".",".","."], ["4",".",".",".",".",".","3","8","."], ["7",".",".",".",".",".",".",".","."], [".",".",".",".","5","3",".",".","."], [".",".",".",".","6","8",".",".","."], ["3",".",".","9",".",".",".",".","."], [".",".",".",".",".","2","1","1","."], [".",".",".",".",".",".",".",".","."]], expected: false },
{ grid: [[".","8",".",".",".",".",".",".","."], [".",".",".",".","2",".",".",".","."], [".","6",".",".",".",".","1",".","4"], [".",".",".","9",".",".","7",".","."], [".",".",".",".",".",".",".","4","."], [".",".","1",".",".","8",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".","5",".","7","."], [".",".","3",".",".","5","6",".","."]], expected: false },
{ grid: [[".",".",".",".",".",".",".",".","."], [".",".","2",".",".",".",".",".","."], [".",".",".",".",".","2","7","1","."], [".",".",".",".",".",".",".",".","."], [".","2",".",".",".",".",".",".","."], [".","5",".",".",".",".",".",".","."], [".",".",".",".","9",".",".",".","8"], [".",".",".",".",".","1","6",".","."], [".",".",".",".","6",".",".",".","."]], expected: true },
{ grid: [[".",".",".","9",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".","3",".",".",".",".",".","1"], [".",".",".",".",".",".",".",".","."], ["1",".",".",".",".",".","3",".","."], [".",".",".",".","2",".","6",".","."], [".","9",".",".",".",".",".","7","."], [".",".",".",".",".",".",".",".","."], ["8",".",".","8",".",".",".",".","."]], expected: false },
{ grid: [[".",".",".",".",".",".","8","3","."], ["2",".",".",".",".",".",".",".","."], ["7",".",".",".",".","7",".","9","5"], [".",".",".","1",".",".",".",".","2"], [".","8",".","9",".",".",".",".","."], [".",".","5","1","9",".",".",".","."], ["5",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."]], expected: false },
].each do |x|
it do
expect(sudoku2(x[:grid])).to eql(x[:expected])
end
end
end
|
