დაადგინეთ, ვალიდურია თუ არა 9x9 ზომის სუდოკუს დაფა (მატრიცა).
მხოლოდ შევსებული უჯრების დადასტურებაა საჭირო შემდეგი წესების დაცვით:
- თითოეულ რიგში არ უნდა იყოს განმეორება.
- თითოეულ სვეტში არ უნდა იყოს განმეორება.
- თითოეულ 3x3 დაფაში არ უნდა იყოს განმეორება.
გაითვალისწინეთ, მაგალითში აღწერილი დაფა შეიძლება იყოს ვალიდური მაგრამ არა ამოხსნადი.
გადაცემული პარამეტრებიდან გამომდინარე ამოცანას აუცილებლად ექნება ერთი სწორი პასუხი.
პირველი მაგალითი
პარამეტრები:
`board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
- შედეგი:
true
- განმარტება: ვალიდურია, რადგან ყველა რიგი და ქვე-დაფა არ შეიცავს განმეორებად ციფრებს.
მეორე მაგალითი
პარამეტრები:
`board = [
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
- შედეგი:
false
- განმარტება: არ არის ვალიდური, რადგან პირველ სვეტში
8 განმეორდა.
შეზღუდევები
board.length == 9board[i].length == 9board[i][j] არის ციფრი '1'-დან '9'-მდე, ან '.'
ამოცანის ამოხსნა შესაძლებელია ბევრი გზით,
ცადეთ ისეთი ალგორითმის მოფიქრება, რომელიც O(1)-თან ახლოს არის.
