פיתוח פותר סודוקו אוטומטי ב Elixir - חלק 2
משחקי לוח ובפרט משחקים כמו סודוקו הם הזדמנות מצוינת ללמוד על רקורסיות ומבני נתונים, ושפה כמו אליקסיר הופכת את העבודה הזאת להרבה יותר נעימה. אנחנו ממשיכים עם החלק השני של המדריך בו נלמד על שיטת החשיבה הפונקציונאלית ועל רקורסיות ב Elixir.
1. מה עושים היום
בחלק הקודם כתבנו קוד אליקסיר שקורא תיאור של לוח סודוקו ובונה ממנו מפה איתה אנחנו יכולים לעבוד כדי לפתור את הלוח. היום נראה איך להשתמש במבנה הנתונים שיצרנו כדי לזהות את כל המהלכים הבאים "הבטוחים" בלוח.
2. מהו מהלך בטוח
בכל לוח סודוקו יש משבצות שכבר מלאות - או שקיבלנו אותן ככה מהלוח או שזה משבצות שכבר ניחשנו את הערך שצריך להיות בהן. משבצות אלה יוצרות אילוצים על המשבצות הריקות:
בכל שורה כל סיפרה יכולה להופיע רק פעם אחת - ולכן עבור משבצת נתונה, אם יש סיפרה מסוימת איתה באותה השורה הסיפרה הזאת בטוח לא תופיע באותה המשבצת.
בכל עמודה כל סיפרה יכולה להופיע רק פעם אחת - ולכן כשיש לנו סיפרה במשבצת אחרת באותה עמודה בטוח הסיפרה הזאת לא תופיע אצלנו.
בכל "קופסא" כל סיפרה יכולה להופיע רק פעם אחת.
לפעמים יש כבר כל כך הרבה ערכים ידועים במשבצות שסביבך שאפשר לדעת בוודאות מה הערך שצריך להיות במשבצת מסוימת. למשל בלוח הזה:
8 . . . . 5 3 7 2
. . . . 8 6 . 9 .
. 3 . 2 . . 8 . .
5 6 . . . 4 1 3 9
. . . . 6 . . . .
3 4 7 9 . . . 6 5
. . 1 . . 7 . 2 .
. 2 . 6 5 . . . .
5 7 9 8 . . . . 4
נתבונן במשבצת הימנית ביותר בשורה השניה: אי אפשר לרשום בה 2, 4, 5 ו-9 כי כולם נמצאים איתה באותו טור. אי אפשר לרשום בה את 6 או 8 כי שניהם נמצאים כבר איתה באותה שורה, ואי אפשר לרשום בה 3 ו-7 כי שניהם כבר מופיעים איתה באותה עמודה. לכן בוודאות במשבצת הזאת צריך לרשום 1.
בחלק של היום נרצה לבנות מנגנון שישחק בשבילנו באופן אוטומטי את כל המהלכים הבטוחים. זה עדיין לא יפתור את הלוח אבל זה בהחלט יקרב אותנו במיוחד בלוחות שנחשבים "קלים".
3. תיקון הקוד מהחלק הקודם כך שיהיה קל לזהות מהלכים בטוחים
בשביל לזהות את כל המהלכים הבטוחים נרצה במהלך התוכנית שלנו לרוץ בלולאה על כל המשבצות במשחק ולשאול לגבי כל משבצת האם יש מהלך בטוח שאפשר לשחק בה. בחלק הקודם יצרנו את הלוח עם הקוד הבא:
def build_from_data(input_file_data) do
input_file_data
|> String.split("\n")
|> Enum.map(&String.trim/1)
|> Enum.map(&String.split/1)
|> Enum.filter(fn x -> !Enum.empty?(x) end)
|> Enum.flat_map(fn x -> x end)
|> Enum.with_index
|> Enum.filter(fn { val, _index } -> val != "." end)
|> Enum.map(fn { val, index } -> {
{ div(index, 9), rem(index, 9) },
MapSet.new([String.to_integer(val)])
}
end)
|> Map.new
end
הלוח שנוצר הורכב ממפה בה כל מפתח הוא אינדקס וכל ערך הוא קבוצת כל האפשרויות שאפשר לרשום בערך זה. משבצות ריקות לא נכנסו לחישוב שלנו בגלל השורה:
|> Enum.filter(fn { val, _index } -> val != "." end)
הבחירה להשאיר את המשבצות הריקות בחוץ היא טובה כי היא תאפשר לנו בהמשך להשתמש בקוד דומה כדי לקרוא לוחות שמיוצגים אחרת (למשל לוח שמגיע בתור JSON Object בו רשומים רק הערכים), אבל היא מסבכת אותנו כשנרצה לסרוק בלולאה את כל המשבצות בלוח.
פונקציית העזר הראשונה שארצה לכתוב היא פונקציה שתפקידה למלא את הלוח, כלומר להוסיף גם את המידע על האינדקסים שלא הופיעו בקלט. הפונקציה Sudoku.get שכתבנו אתמול ממילא יודעת להחזיר את קבוצת כל הספרות אם מבקשים ממנה אינדקס שהיא לא מכירה ולכן נוכל להשתמש בה:
def fill_blanks(game) do
for i <- 0..8 do
for j <- 0..8 do
{ { i, j }, Sudoku.get(game, { i, j }) }
end
end
|> Enum.flat_map(fn x -> x end)
|> Map.new
end
הפקודה for באליקסיר היא דרך מתוחכמת לייצר רשימה. היא נראית כמו לולאת for במובן זה שאנחנו רושמים פקודות בבלוק שאחריה, אבל לפקודה for יש ערך החזר והוא רשימת כל התוצאות של הפקודות הפנימיות. לכן הלולאה המקוננת שלנו מחזירה רשימה של רשימות. הפונקציה flat_map מיישרת את המבנה והפונקציה Map.new הופכת אותו חזרה למפה.
הפונקציה fill_blanks לכן מקבלת מפה ומייצרת ממנה מפה חדשה. במפה החדשה יהיו תמיד 81 שורות ובכל שורה המפתח יהיה האינדקס (שורה, עמודה) והערך יהיה התוצאה של Sudoku.get על האינדקס.
קוד הבניה המתוקן יראה כך:
def build_from_data(input_file_data) do
input_file_data
|> String.split("\n")
|> Enum.map(&String.trim/1)
|> Enum.map(&String.split/1)
|> Enum.filter(fn x -> !Enum.empty?(x) end)
|> Enum.flat_map(fn x -> x end)
|> Enum.with_index
|> Enum.filter(fn { val, _index } -> val != "." end)
|> Enum.map(fn { val, index } -> {
{ div(index, 9), rem(index, 9) },
MapSet.new([String.to_integer(val)])
}
end)
|> Map.new
|> fill_blanks
end
4. כתיבת פונקציות עזר
בכתיבת תוכנית בגישה הפונקציונאלית אנחנו לא מתעסקים בבניית מודל של העולם ואיפיון הממשק של כל מחלקה. במקום זה אנחנו מתמקדים במידע ובשינויים שהוא עובר. גם הכתיב עצמו הוא בדרך כלל מלמטה למעלה, כלומר מתחילים מבניית פונקציות קטנות שיעזרו לנו לתאר שינויים מורכבים במידע, ואז מחברים אותן כדי לתאר את אותם שינויים.
מה שמעניין אותנו היום הוא למצוא מהלכים בטוחים ובשביל זה נצטרך להיות מסוגלים להסתכל על כל הערכים שיש בשורה, בעמודה ובקופסא מסוימת, לפי משבצת שבחרנו. לכן אפשר לבנות 3 פונקציות עזר שיעזרו עם שלושת המטלות:
def same_column_indexes({ row, col }) do
0..8
|> Enum.to_list
|> List.delete(row)
|> Enum.map(fn i -> { i, col } end)
end
def same_row_indexes({ row, col }) do
0..8
|> Enum.to_list
|> List.delete(col)
|> Enum.map(fn i -> { row, i } end)
end
def same_box_indexes({ row, col }) do
for i <- 0..2 do
for j <- 0..2 do
{ (div(row, 3) * 3) + i, (div(col, 3) * 3) + j }
end
end
|> Enum.flat_map(fn x -> x end)
|> Enum.filter(fn { i, j } -> { i, j } != { row, col } end)
end
מה שכל פונקציית עזר עושה הוא לייצר את רשימת האינדקסים שנמצאים איתי באותה השורה, העמודה או הקופסא. הנה הסבר מלא על הראשונה (האחרות די דומות). השורה הראשונה בה מתארת את הקלט, כלומר טווח המספרים 0..8:
0..8
את זה הופכים לרשימה:
|> Enum.to_list
מהרשימה מוחקים את השורה שאני נמצא בה:
|> List.delete(row)
ואז הופכים את רשימת המספרים לרשימה של אינדקסים:
|> Enum.map(fn i -> { i, col } end)
ערך העמודה של כל האינדקסים זהה, וערך השורה מתחלף כדי לכסות את כל 8 השורות האחרות.
בקובץ הבדיקות sudoku_test.exs נלך להוסיף בדיקות ל-3 פונקציות העזר:
test "row indexes" do
assert(Sudoku.same_row_indexes({ 4, 2 }) == [
{ 4, 0 }, { 4, 1 }, { 4, 3 }, { 4, 4 }, { 4, 5 }, { 4, 6 }, { 4, 7 }, { 4, 8 }
])
assert(Sudoku.same_row_indexes({ 7, 1 }) == [
{ 7, 0 }, { 7, 2 }, { 7, 3 }, { 7, 4 }, { 7, 5 }, { 7, 6 }, { 7, 7 }, { 7, 8 }
])
end
test "column indexes" do
assert(Sudoku.same_column_indexes({ 4, 2 }) == [
{ 0, 2 }, { 1, 2 }, { 2, 2 }, { 3, 2 }, { 5, 2 }, { 6, 2 }, { 7, 2 }, { 8, 2 }
])
end
test "box indexes" do
assert(Sudoku.same_box_indexes({ 4, 2 }) == [
{ 3, 0 }, { 3, 1 }, { 3, 2 }, { 4, 0 }, { 4, 1 }, { 5, 0 }, { 5, 1 }, { 5, 2 }
])
end
פונקציית העזר האחרונה לפני שנמשיך לזהות מהלכים בטוחים היא print, פונקציה שתפקידה פשוט להדפיס את הלוח:
def print(game) do
for i <- 0..8 do
for j <- 0..8 do
v = Sudoku.get(game, {i, j})
if MapSet.size(v) == 1 do
" #{List.first(MapSet.to_list(v))} "
else
" . "
end
end
|> IO.puts
end
end
הפונקציה משתמשת באותן לולאות for עליהן כבר דיברנו רק שהפעם כל ערך בתוך הרשימה הוא מחרוזת - הסימן נקודה אם אנחנו לא בטוחים מה לרשום שם או הסיפרה שצריך לרשום אם יש רק אפשרות אחת. הלולאה הפנימית מייצרת רשימה של מחרוזות וכל הרשימה מנותבת ל IO.puts כדי להדפיס את כל המחרוזות ברשימה ובסוף תו ירידת שורה.
5. זיהוי מהלכים בטוחים על הלוח
סיימנו את עבודת ההכנה ואנחנו יכולים להתקדם ולתת לאליקסיר לזהות בשבילנו מהלכים בטוחים על לוח הסודוקו. הפונקציה הראשונה והארוכה יותר בחלק הזה מקבלת את לוח המשחק ואינדקס של משבצת ומשתמשת ב-3 פונקציות העזר שכתבנו כדי לזהות את כל הערכים שגילינו באותה השורה, עמודה וקופסא. אחרי זה מורידים מרשימת האפשרויות במשבצת את כל הערכים שמצאנו ומחזירים את רשימת האפשרויות החדשה.
קודם הקוד ואז ההסבר:
def process_constraints_at(game, index) do
constraint_indexes = [
same_row_indexes(index),
same_column_indexes(index),
same_box_indexes(index),
]
|> Enum.reduce(&Enum.concat/2)
constraint_values = Map.take(game, constraint_indexes)
|> Map.values
|> Enum.filter(fn v -> MapSet.size(v) == 1 end)
|> Enum.reduce(MapSet.new([]), &MapSet.union/2)
MapSet.difference(
Sudoku.get(game, index),
constraint_values
)
end
הפונקציה יחסית ארוכה וכוללת 3 פעולות מרכזיות: הפעולה הראשונה מגדירה את המשתנה constraint_indexes שיהיה רשימת כל האינדקסים איתי באותה השורה, באותה העמודה ובאותה הקופסא. הפעולה השניה מגדירה את המשתנה constraint_values ושומרת בו את כל הערכים שנמצאים באינדקסים שגילינו, והפעולה השלישית מחזירה את ההפרש בין מה שכרגע רשום במשבצת לבין כל הדברים שבטוח אסור לרשום שם.
נתחיל עם הפעולה הראשונה:
constraint_indexes = [
same_row_indexes(index),
same_column_indexes(index),
same_box_indexes(index),
]
|> Enum.reduce(&Enum.concat/2)
הקלט כאן הוא רשימה של רשימות כל האינדקסים אותן קיבלנו מפונקציות העזר, וקלט זה עובר ל Enum.reduce יחד עם הפונקציה Enum.concat. הפקודה concat מחברת רשימות ובכתיב הזה אנחנו מקבלים פשוט רשימה אחת ארוכה של כל האינדקסים.
אגב דרך אחרת לכתוב את זה באליקסיר היתה שימוש באופרטור ++ שהוא אופרטור חיבור רשימות:
constraint_indexes = same_row_indexes(index) ++ same_column_indexes(index) ++ same_box_indexes(index)
אבל בעיניי הכתיב הראשון קצת יותר נקי.
החלק השני כולל קצת יותר פעולות:
constraint_values = Map.take(game, constraint_indexes)
|> Map.values
|> Enum.filter(fn v -> MapSet.size(v) == 1 end)
|> Enum.reduce(MapSet.new([]), &MapSet.union/2)
הפעולה Map.take לוקחת מפה ורשימת מפתחות ומחזירה מפה חדשה רק עם הערכים והמפתחות שקיבלנו ברשימה. בהקשר שלנו היא תחזיר רק את המפתחות והערכים מתוך game שגובלים במשבצת שלנו (נמצאים איתה באותה שורה, עמודה או קופסה).
את התוצאה אנחנו שולחים ל:
|> Map.values
כדי לקבל רק את הערכים, כלומר רק את הדברים שרשומים על הלוח (או במשבצת שאנחנו עדיין לא בטוחים לגביה, את כל האפשרויות שאפשר לרשום באותה משבצת). בחישוב מהלכים בטוחים אני מעדיף לסנן משבצות שאני לא בטוח לגביהן ולכן הפקודה הבאה:
|> Enum.filter(fn v -> MapSet.size(v) == 1 end)
משאירה ברשימה רק את המשבצות שאנחנו יודעים בוודאות מה רשום בהן. בסוף אנחנו שולחים את הכל ל union:
|> Enum.reduce(MapSet.new([]), &MapSet.union/2)
כדי לקחת את כל הערכים שרשומים בכל המשבצות השכנות ולייצר מכולם קבוצה אחת גדולה.
הפעולה השלישית והאחרונה בפונקציה מורידה מקבוצת האפשרויות שאני חושב שמותר לרשום במשבצת שלי את כל הדברים שגיליתי שנמצאים איתי באותה השורה, עמודה או קופסא:
MapSet.difference(
Sudoku.get(game, index),
constraint_values
)
וזה גם ערך ההחזר של הפונקציה.
פונקציית הבדיקה הבאה מוודאת שהפונקציה כתובה כמו שצריך:
test "process constraints" do
data = """
8 . . . . 5 3 7 2
. . . . 8 6 . 9 .
. 3 . 2 . . 8 . .
5 6 . . . 4 1 3 9
. . . . 6 . . . .
3 4 7 9 . . . 6 5
. . 1 . . 7 . 2 .
. 2 . 6 5 . . . .
5 7 9 8 . . . . 4
"""
things_to_write_in_2_8 = Sudoku.build_from_data(data)
|> Sudoku.process_constraints_at({ 1, 8 })
assert(things_to_write_in_2_8 == MapSet.new([1]))
end
6. סריקת כל הלוח כדי לזהות את כל המהלכים הבטוחים
אנחנו יודעים איך לזהות מהלכים בטוחים במשבצת מסוימת ולכן הצעד הבא הוא לזהות מהלכים בטוחים על כל הלוח. ניסיון ראשון יכול להיראות כך:
def process_constraints(game) do
game
|> Enum.map(fn { index, _ } ->
{ index, process_constraints_at(game, index) }
end)
|> Map.new
end
הפונקציה שולחת את game ל map שתעבור על כל אחד מהאלמנטים ברשימה game, כלומר על כל אחת מהמשבצות, ותחליף את הערך של אותה המשבצת בתוצאה של process_constraints_at באינדקס זה. את התוצאה שולחים ל Map.new כדי לקבל לוח משחק חדש.
וזה עובד. חלקית. כי מהר מאוד אנחנו שמים לב שאחרי שזיהינו את כל המהלכים הבטוחים על הלוח ורשמנו אותם עשויים להתגלות מהלכים בטוחים נוספים, ואז נוספים וכך הלאה. היינו רוצים להמשיך לקרוא לפונקציה הזאת שוב ושוב עד שנסיים לגלות את כל המהלכים הבטוחים. קוד אליקסיר בשביל זה יראה כך:
def process_all_constraints(game) do
newgame = process_constraints(game)
if newgame == game do
newgame
else
process_all_constraints(newgame)
end
end
בגלל שכל מבני הנתונים הם Immutable, וכל פונקציה בסך הכל מחזירה את מבנה הנתונים החדש, קל מאוד להשוות בין התוצאה של process_constraints ללוח לפני הפעלת הפונקציה. אם הם זהים אנחנו יודעים שאין טעם להמשיך כי כבר מצאנו את כל המהלכים הבטוחים, אבל אם יש הבדל אנחנו יודעים שמצאנו מהלכים בטוחים חדשים ולכן אולי יהיו עוד.
במקום לסיים עם תוכנית בדיקה מסודרת אני רוצה להשתמש בפונקציה print ובלוח הדוגמא כדי לראות מה קורה כשמפעילים את process_all_constraints על הלוח:
test "process all constraints" do
data = """
8 . . . . 5 3 7 2
. . . . 8 6 . 9 .
. 3 . 2 . . 8 . .
5 6 . . . 4 1 3 9
. . . . 6 . . . .
3 4 7 9 . . . 6 5
. . 1 . . 7 . 2 .
. 2 . 6 5 . . . .
5 7 9 8 . . . . 4
"""
Sudoku.build_from_data(data)
|> Sudoku.process_all_constraints
|> Sudoku.print
end
והתוצאה:
localhost:sudoku ynonperek$ mix test test/sudoku_test.exs:63
Excluding tags: [:test]
Including tags: [line: "63"]
8 9 6 1 4 5 3 7 2
7 5 . 3 8 6 4 9 1
1 3 4 2 7 9 8 5 6
. 6 8 7 2 4 1 3 9
9 1 . 5 6 3 7 4 8
3 4 7 9 1 8 2 6 5
6 8 1 4 9 7 5 2 3
4 2 3 6 5 1 9 8 7
. 7 9 8 3 2 6 1 4
זה לא פתר את כל הלוח אבל בהחלט קירב אותנו. כמובן שזה רק צירוף מקרים בגלל שבחרתי לוח קל. ככל שלוחות הסודוקו "קשים" יותר כך יהיה קשה יותר למלא את הלוח באמצעות מהלכים בטוחים בלבד.
מה הלאה? בחלק הבא נלמד איך לבקש מאליקסיר לנחש מהלך, לנסות לראות אם הוא פותר את המשחק ואם לא לחזור אחורה כדי לנחש מהלך אחר.
את הקוד לכל התוכנית אתם יכולים למצוא בגיטהאב בקישור: