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