סודוקו

אז אתמול קרה לי אחד הדברים המעצבנים.
הייתי בראיון עבודה, והתבקשתי לכתוב פונקציה שבודקת תקינות של לוח סודוקו. זה נשמע כל כך פשוט בתיאוריה שאף פעם לא ניסיתי אפילו לכתוב את הפונקציה הזאת.

ואז קרה אחד הדברים הכי גרועים שיכולים לקרות בראיון – היה לי בריינפריז גמור.
כתבתי את הבדיקה של השורות והעמודות, ואז כשבאתי לכתוב את הבדיקה של הקוביות נתקעתי, לא היה לי מושג איך אני עושה את זה. היה לי ברור שצריך לעשות פה איזשהו משחק עם האינדקסים, אבל פשוט לא הצלחתי.

המשכתי להתברבר ולהתברבר ובסוף לא הצלחתי לסיים את התרגיל.
אז זה די מבאס, אבל מה שיותר גרוע הוא שחזרתי הביתה ועדיין לא ידעתי איך לענות על השאלה הזו, אז מן הסתם, ידעתי שאני צריכה לכתוב פוסט על זה.

אז המשימה היא זו – בהינתן לוח סודוקו מלא, צריך לבדוק האם הלוח תקין. כלומר, האם בכל שורה, עמודה וקוביה ישנם כל המספרים מ-1 עד 9, כשכל אחד חוזר פעם אחת בדיוק.

אז השאלה הזאת מחולקת לשלושה חלקים – 
צריך לבדוק שכל שורה בלוח היא תקינה, שכל עמודה בלוח היא תקינה וכל קוביה בלוח היא תקינה.
החלק של השורות והעמודות הוא ממש קל, ואפשר לבדוק את שניהם בלולאה אחת – 

def check_valid_vector(vector):
	for i in range(1,10):
		if vector.count(i) != 1:
			return False
	return True

def check_row_and_columns_are_valid(sudoku):
	for i in range(0,9):
		row = sudoku[i]
		if not check_valid_vector(row):
			return False
		column = [sudoku[j][i] for j in range(0,9)]
		if not check_valid_vector(column):
			return False
	return True

אבל אז מגיע החלק הקשה – איך אני משיגה את האינדקסים של קוביה בודדת כדי לבדוק אותה?
אני חושבת שמה שתקע אותי במקרה הזה היה התיאור של השאלה. אם השאלה הייתה על מטריצה כלשהי הייתי מתחילה מדוגמאות קטנות, מוצאת דרך להכליל אותן, ואז מגדילה. אבל בגלל שהשאלה הוצגה על לוח סודוקו זה חסם לי את כיוון המחשבה, וכל הזמן ניסיתי למצוא את הפתרון רק ללוח של תשע על תשע.

אז אני אנסה באמת להתחיל מדוגמא קטנה בתקווה שזה יעזור.
אני אסתכל על לוח של 4X4, אמלא אותו באינדקסים, ואראה אם אני מוצאת את התבנית של האינדקסים בכל קוביה – 

קול, אז בואו נראה מה קורה עם הקוביות כאן.
יש לי ארבע קוביות – 

a0 = 00,01,10,11 a1 = 02,03,12,13 a2 = 20,21,30,31 a3 = 22,23,32,33

אז קודם כל, אני יודעת שכל קוביה מתפרשת על שתי שורות ושתי עמודות, והשהדבר העיקרי שמפריד בין העמודות הוא האינדקס של הקוביה.
האינדקס של הקוביה יכול לתת לי מידע כלשהו על המקדמים של הטורים והעמודות.
יש שתי סוגים של מניפולציות שאני יכולה לחשוב עליהן לעשות לאינדקסים – 

מודולו = 

a0 → 0%2 = 0 a1 → 1%2 = 1 a2 → 2%2 = 0 a3 → 3%2 = 1

וחלוקה, שתיתן לי את התוצאות ההפוכות – 

a0 → 0/2 = 0 a1 → 1/2 = 0 a2 → 2/2 = 1 a3 → 3/2 = 1

עכשיו, אם אני אסתכל על האינדקסים של השורות והעמודות בכל קוביה, אני רואה שבכל קוביה יש שתי אינדקסים של שורות ושתי אינדקסים של עמודות, ואני מקבלת את כל הקומבינציות שלהן. כמו כן, תמיד יש הפרש של 1 בין עמודה לעמודה ושורה לשורה.
מממ… זה יכול אולי לצאת על ידי כפל? אני אנסה לפרמל משהו .

a0 = 00,01,10,11 a1 = 02,03,12,13 a2 = 20,21,30,31 a3 = 22,23,32,33

נגיד, בקוביה a0 אני רוצה לקבל את 0 פעמיים, פעם עם 0 ופעם עם 1, ואת 1 פעמיים, פעם עם 0 ופעם עם 1.
זה כבר לגמרי נשמע כמו לולאה בתוך לולאה – 

cube_a0 = [] for i in range(0,2): for j in range(0,2): cube_a0.append(i,j) i=0,j=0 cube_a0=[00] i=0,j=1 cube_a0=[00,01] i=1,j=0 cube_a0=[00,01,10] i=1,j=1 cube_a0=[00,01,10,11]

זה היה קל, אבל איך אני מתקדמת מפה לשאר הקוביות?
בקוביה a1 אני רוצה לקבל את 0 פעמיים, פעם עם 2 ופעם עם 3, ואת 1 פעמיים, פעם עם 1 ופעם עם 3.

אני יודעת! אני אוסיף את המודולו של הקוביה כפול 2!
מממ… מסובך. את 0 ו-1 כבר ראיתי שאני יכולה לקבל בלולא פשוטה, אבל איך אני מקבלת פעם 2 ופעם 3?

cube_a1 = [] for i in range(0,2): for j in range(0,2): row = i column = 2*(1%2) + j cube_a0.append(row,column) i=0,j=0 cube_a1=[02] i=0,j=1 cube_a1=[00,03] i=1,j=0 cube_a1=[00,01,12] i=1,j=1 cube_a1=[00,01,12,13]

אוקי, התקדמות מצוינת. מה לגבי הקוביה הבאה?
ב-a2 אני רוצה לקבל פעמיים 2 ופעמיים 3, פעם עם 0 ופעם עם 1.
אז אני כבר יודעת איך לייצר 2 ו-3 ו-0 ו-1, אבל איך אני מקבלת אותם בסדר ההפוך הפעם? משתמשת בחלוקה של האינדקס של הקוביה כמקדם לשורה – 

cube_a2 = [] for i in range(0,2): for j in range(0,2): row = 2*(2/2) + i column = 2*(2%2) + j cube_a0.append(row,column) i=0,j=0 cube_a2=[20] i=0,j=1 cube_a2=[20,21] i=1,j=0 cube_a2=[20,21,30] i=1,j=1 cube_a2=[20,21,30,31]

עכשיו רק נשאר לוודא שהאלגוריתם שלי פועל גם על הקוביה האחרונה – 

cube_a3 = [] for i in range(0,2): for j in range(0,2): row = 2*(3/2) + i column = 2*(3%2) + j cube_a0.append(row,column) i=0,j=0 cube_a2=[22] i=0,j=1 cube_a2=[22,23] i=1,j=0 cube_a2=[22,23,32] i=1,j=1 cube_a2=[22,23,32,33]

קיבלתי תוצאה נכונה!
עכשיו כל מה שאני צריכה הוא להכליל את האלגוריתם!
אני אתחיל עם ההכללה לגודל הנוכחי שלי – 4X4 – 

for cube_index in range(0,4):
	cube = []
for i in range(0,2):
	for j in range(0,2):
		row = 2*(cube_index/2) + i
		column = 2*(cube_index%2) + j
		cube.append(row,column)

עכשיו אני רוצה להכליל למטריצה גדולה יותר (נגיד, סודוקו).

בסודוקו יש לי 9 קוביות, בכל קוביה יש לי 3 שורות ו-3 עמודות. כל המקומות בהם השתמשתי בקבוע 2 היו בעצם ריצות על שורות או עמודות, או מיקום הקוביה ביחד לשורה/עמודה. ולכן כולם יתחלפו כאן בשלוש – או, בהכללה גדולה יותר, בשורש של גודל הסודוקו.

cube_size = sqrt(board_size)
for cube_index in range (0,board_size):
	cube = []
	for i in range(0,cube_size):
		for j in range(0,cube_size):
			row = cube_size*(cube_index/cube_size) + i
			column = cube_size*(cube_index%cube_size) + j
		cube.append(row,column)

אני אעשה בדיקה חלקית מאוד של קוביה בלוח סודוקו

board_size = 9 cube_size = 3 cube_index = 1 cube = [] i=0 j=0 row = 0 column = 3 cube = [03] i=0 j=1 row = 0 column = 4 cube = [03,04] i=0 j=2 row = 0 column = 5 cube = [03,04,05] i=1 j=0 row = 1 column = 3 cube = [03,04,05,13] …

כמובן שעכשיו, כשאני מסתכלת על האלגוריתם הסופי שלי זה נראה מאוד הגיוני – כל פעם לוקחים מקדם שורה ומקדם עמודה שמתארים את השורות והעמודות של הקוביות (ולא שלא התאים הפנימיים) – והמודולו והחלוקה רק משמשים בשביל לחשב אותם.

למען האמת הייתי יכולה לעשות פתרון מאוד פשוט שהיה מביא אותי לאותה התוצאה – 

cube_size = sqrt(board_size)
for cube_row in range(0,cube_size):
	for cube_column in range(0,cube_size):
	cube = []
	for i in range(0,cube_size):
		for j in range(0,cube_size):
			row = cube_row*cube_size + i
			column = cube_column*cube_size + j
		cube.append(row,column)

אבל כמובן ש-hindsight is 20/20. 

אפשר להגיד שהפתרון הזה שרץ על השורות והעמודות של הקוביות הוא סוג של הפתרון הנאיבי ואני פספסתי אותו כי ניסיתי להתחכם יותר מדי. אני אנסה להבא לעלות על דברים כאלה יותר מהר. העיקר שניצחתי את הסודוקו ארור! הגיע הזמן לקודד את זה!

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/sudoku_checker.py