Site Logo
כניסה
  • בלוג
  • פיתוח פותר סודוקו אוטומטי ב Elixir - חלק 1

פיתוח פותר סודוקו אוטומטי ב Elixir - חלק 1

11/05/2019
יומי

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

תוכן עניינים

  1. מה עושים היום
  2. איך לייצג לוח סודוקו
  3. פיתוח שלד פרויקט
  4. כתיבת פונקציה לקריאת לוח ממחרוזת ובניית מבנה הנתונים
  5. כתיבת בדיקה לפונקציה

1. מה עושים היום

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

2. איך לייצג לוח סודוקו

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

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

game = [
    ["4", ".", ".", "8", ".", ".", "5", "9", "."],
    [".", "8", ".", ".", ".", "9", ".", ".", "."],
    [".", ".", ".", "2", "6", ".", ".", "4", "."],
    [".", ".", "8", ".", ".", ".", ".", ".", "3"],
    ["6", "7", ".", ".", "5", ".", ".", "1", "8"],
    ["1", ".", ".", ".", ".", ".", "2", ".", "."],
    [".", "6", ".", ".", "8", "1", ".", ".", "."],
    [".", ".", ".", "3", ".", ".", ".", "2", "."],
    [".", "9", "5", ".", ".", "7", ".", ".", "6"],
]

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

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

בניגוד לפייתון, אליקסיר לא עובדת טוב עם מערכים דו-מימדיים ולכן מבנה נתונים שיותר יתאים לשפה זו הוא המפה (בפייתון זה נקרא Dictionary). המפתח יהיה האינדקס והערך יהיה קבוצת כל הספרות שאפשר לרשום באינדקס זה. במשבצות שנקבל מהלוח הרשימה תכיל רק איבר יחיד. מבנה הנתונים של מפה באליקסיר נקרא Map ומבנה הנתונים ששומר קבוצת ספרות נקרא MapSet.

3. פיתוח שלד פרויקט

אם עדיין אין לכם אליקסיר ואתם רוצים לנסות אצלכם את הדוגמא תצטרכו להתקין את השפה מכאן:

https://elixir-lang.org/install.html

אחרי ההתקנה משורת הפקודה נרשום את הפקודה הבאה כדי ליצור שלד פרויקט חדש:

$ mix new sudoku

הפקודה יוצרת את הקבצים והתיקיות הבאים:

.
├── README.md
├── _build
│   ├── dev
│   │   └── lib
│   └── test
│       └── lib
├── config
│   └── config.exs
├── lib
│   └── sudoku.ex
├── mix.exs
└── test
    ├── sudoku_test.exs
    └── test_helper.exs

הקובץ הראשי של התוכנית הוא sudoku.ex שנמצא בתיקיה lib. קובץ הבדיקה נקרא sudoku_test.exs והוא נמצא בתיקיה test.

4. כתיבת פונקציה לקריאת לוח ממחרוזת ובניית מבנה הנתונים

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

בתור התחלה נניח שיש לנו את המחרוזת הבאה שמייצגת לוח משחק סודוקו:

4 . . 8 . . 5 9 .
. 8 . . . 9 . . .
. . . 2 6 . . 4 .
. . 8 . . . . . 3
6 7 . . 5 . . 1 8
1 . . . . . 2 . .
. 6 . . 8 1 . . .
. . . 3 . . . 2 .
. 9 5 . . 7 . . 6

נקודה מייצגת משבצת ריקה וסיפרה מייצגת משבצת שיש בה ערך.

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

  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

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

עכשיו לעניין שלנו - מה בעצם כתוב שם? הנה ההסבר שורה אחר שורה.

התחלנו עם שם המשתנה input_file_data. זוהי המחרוזת שראינו שמתארת את הלוח. מאחר והמשתנה כתוב כמו שהוא הוא פשוט עובר ישירות בתור קלט לפונקציה שבאה אחריו (זה מה שאומר סימן ה Pipeline שאנחנו רואים בתחילת כל שורה).

השורה השניה היא:

    |> String.split("\n")

הפונקציה String.split מקבלת מחרוזת ותו הפרדה וחותכת את המחרוזת לרשימה של מחרוזות קטנות יותר לפי תו ההפרדה. לכן הפלט של זה יהיה רשימה של מחרוזות שנראית בערך כך:

[
  "4 . . 8 . . 5 9 .\n",
  ". 8 . . . 9 . . .\n",
  ". . . 2 6 . . 4 .\n",
  ". . 8 . . . . . 3\n",
  "6 7 . . 5 . . 1 8\n",
  "1 . . . . . 2 . .\n",
  ". 6 . . 8 1 . . .\n",
  ". . . 3 . . . 2 .\n",
  ". 9 5 . . 7 . . 6\n",
]

ממשיכים לשורה הבאה:

    |> Enum.map(&String.trim/1)

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

ממשיכים עם עוד map והפעם הפונקציה שמפעילים על כל הרשימה היא הפונקציה split:

    |> Enum.map(&String.split/1)

אנחנו מכירים כבר את split שחותכת כל מחרוזת והופכת אותה לרשימה, מה שמביא אותנו למבנה של רשימה של רשימות:

[
    ["4", ".", ".", "8", ".", ".", "5", "9", "."],
    [".", "8", ".", ".", ".", "9", ".", ".", "."],
    [".", ".", ".", "2", "6", ".", ".", "4", "."],
    [".", ".", "8", ".", ".", ".", ".", ".", "3"],
    ["6", "7", ".", ".", "5", ".", ".", "1", "8"],
    ["1", ".", ".", ".", ".", ".", "2", ".", "."],
    [".", "6", ".", ".", "8", "1", ".", ".", "."],
    [".", ".", ".", "3", ".", ".", ".", "2", "."],
    [".", "9", "5", ".", ".", "7", ".", ".", "6"],
]

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

    |> Enum.filter(fn x -> !Enum.empty?(x) end)

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

השורה הבאה היא:

    |> Enum.flat_map(fn x -> x end)

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

אחרי הפעלת השורה אנחנו מקבלים פלט שנראה כך:

["4", ".", ".", "8", ".", ".", "5", "9", ".", ".", "8", ".", ".", ".", "9", ".",
 ".", ".", ".", ".", ".", "2", "6", ".", ".", "4", ".", ".", ".", "8", ".", ".",
 ".", ".", ".", "3", "6", "7", ".", ".", "5", ".", ".", "1", "8", "1", ".", ".",
 ".", ".", ...]

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

    |> Enum.with_index

והפלט שלה:

[
  {"4", 0},
  {".", 1},
  {".", 2},
  {"8", 3},
  {".", 4},
  {".", 5},
  {"5", 6},
  {"9", 7},
  {".", 8},
  {".", 9},
  {"8", 10},
  {".", 11},
  {".", 12},
  {".", 13},
  {"9", 14},
  {".", 15},
  {".", 16},
  {".", 17},
  {".", 18},
  {".", 19},
  {".", 20},
  {"2", 21},
  {"6", 22},
  {".", 23},
  {".", 24},
  {"4", 25},
  {".", 26},
  {".", 27},
  {".", 28},
  {"8", 29},
  {".", 30},
  {".", 31},
  {".", 32},
  {".", 33},
  {".", 34},
  {"3", 35},
  {"6", 36},
  {"7", 37},
  {".", 38},
  {".", 39},
  {"5", 40},
  {".", 41},
  {".", 42},
  {"1", 43},
  {"8", 44},
  {"1", 45},
  {".", 46},
  {".", 47},
  {".", ...},
  {...},
  ...
]

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

    |> Enum.filter(fn { val, _index } -> val != "." end)

והפלט של פונקציית הסינון הוא הרשימה:

[
  {"4", 0},
  {"8", 3},
  {"5", 6},
  {"9", 7},
  {"8", 10},
  {"9", 14},
  {"2", 21},
  {"6", 22},
  {"4", 25},
  {"8", 29},
  {"3", 35},
  {"6", 36},
  {"7", 37},
  {"5", 40},
  {"1", 43},
  {"8", 44},
  {"1", 45},
  {"2", 51},
  {"6", 55},
  {"8", 58},
  {"1", 59},
  {"3", 66},
  {"2", 70},
  {"9", 73},
  {"5", 74},
  {"7", 77},
  {"6", 80}
]

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

    |> Enum.map(fn { val, index } -> {
      { div(index, 9), rem(index, 9) },
      MapSet.new([String.to_integer(val)])
    }
    end)

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

[
  {{0, 0}, #MapSet<[4]>},
  {{0, 3}, #MapSet<[8]>},
  {{0, 6}, #MapSet<[5]>},
  {{0, 7}, #MapSet<[9]>},
  {{1, 1}, #MapSet<[8]>},
  {{1, 5}, #MapSet<[9]>},
  {{2, 3}, #MapSet<[2]>},
  {{2, 4}, #MapSet<[6]>},
  {{2, 7}, #MapSet<[4]>},
  {{3, 2}, #MapSet<[8]>},
  {{3, 8}, #MapSet<[3]>},
  {{4, 0}, #MapSet<[6]>},
  {{4, 1}, #MapSet<[7]>},
  {{4, 4}, #MapSet<[5]>},
  {{4, 7}, #MapSet<[1]>},
  {{4, 8}, #MapSet<[8]>},
  {{5, 0}, #MapSet<[1]>},
  {{5, 6}, #MapSet<[2]>},
  {{6, 1}, #MapSet<[6]>},
  {{6, 4}, #MapSet<[8]>},
  {{6, 5}, #MapSet<[1]>},
  {{7, 3}, #MapSet<[3]>},
  {{7, 7}, #MapSet<[2]>},
  {{8, 1}, #MapSet<[9]>},
  {{8, 2}, #MapSet<[5]>},
  {{8, 5}, #MapSet<[7]>},
  {{8, 8}, #MapSet<[6]>}
]

הפקודה האחרונה בשרשרת היא:

    |> Map.new

פקודה זו הופכת את רשימת הזוגות למבנה נתונים של מפה כך שנוכל לשלוף ערך בקלות לפי האינדקס. הנה הפונקציה במלואה שוב:

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

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

  def get(game, index) do
    Map.get(game, index, MapSet.new([1, 2, 3, 4, 5, 6, 7, 8, 9]))
  end

אני שומר את שתי הפונקציות בקובץ lib/sudoku.ex. אתם יכולים למצוא את כל הפרויקט שלי עם הפונקציות בגיטהאב בקישור:

https://github.com/ynonp/sudoku-solver-elixir/tree/part1

5. כתיבת בדיקה לפונקציה

נמשיך לכתיבת תוכנית בדיקה לפונקציה. בפרויקט אליקסיר יש לנו לכל מודול קובץ בדיקה שמתאים לו ששמור בתיקיה test ובמקרה שלנו קובץ הבדיקה הוא test/sudoku_test.exs. הנה תוכן הקובץ קודם כל ואז ההסבר:

defmodule SudokuTest do
  use ExUnit.Case
  doctest Sudoku

  test "build board from data file" do
    data = """
4 . . 8 . . 5 9 .
. 8 . . . 9 . . .
. . . 2 6 . . 4 .
. . 8 . . . . . 3
6 7 . . 5 . . 1 8
1 . . . . . 2 . .
. 6 . . 8 1 . . .
. . . 3 . . . 2 .
. 9 5 . . 7 . . 6
"""
    game = Sudoku.build_from_data(data)
    assert(Sudoku.get(game, { 0, 0 }) == MapSet.new([4]))
    assert(Sudoku.get(game, { 0, 3 }) == MapSet.new([8]))
    assert(Sudoku.get(game, { 0, 1 }) == MapSet.new([1, 2, 3, 4, 5, 6, 7, 8, 9]))
  end
end

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

כל קוד הפרויקט זמין בגיטהאב בקישור:

https://github.com/ynonp/sudoku-solver-elixir/tree/part1

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