Sudoku Solver ใน C ++

สมมติว่าเรามีตารางซูโดกุ และเราต้องแก้ปัญหาเขาวงกตตัวเลขที่มีชื่อเสียงนี้ ซูโดกุ เรารู้ว่าซูโดกุเป็นตารางตัวเลข 9 x 9 และทั้งตารางถูกแบ่งออกเป็น 3 x 3 กล่อง มีกฎบางอย่างในการแก้ซูโดกุ

• เราต้องใช้ตัวเลข 1 ถึง 9 เพื่อแก้ปัญหานี้

• ไม่สามารถทำซ้ำหนึ่งหลักในหนึ่งแถว หนึ่งคอลัมน์ หรือในกล่อง 3 x 3 หนึ่งช่อง

เราจะพยายามแก้ปัญหาซูโดกุโดยใช้อัลกอริธึมย้อนรอย เมื่อเติมตัวเลขลงในเซลล์บางเซลล์ ระบบจะตรวจสอบว่าถูกต้องหรือไม่ เมื่อไม่ถูกต้องจะตรวจสอบหมายเลขอื่น หากตรวจสอบหมายเลขทั้งหมดตั้งแต่ 1-9 และไม่พบตัวเลขที่ถูกต้อง ระบบจะย้อนกลับไปที่ตัวเลือกก่อนหน้า

ดังนั้นหากอินพุตเป็นแบบ −

ผลลัพธ์จะเป็น −

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า isPresentInCol() ซึ่งจะรับสายและจำนวน

• สำหรับแต่ละแถว r ในตาราง ทำ

  • ถ้า grid[r, col] =num ให้คืนค่า true

• คืนค่าเท็จมิฉะนั้น

• กำหนดวิธีการที่เรียกว่า isPresentInRow() ซึ่งจะใช้แถวและจำนวน

• สำหรับแต่ละคอลัมน์ c ในตาราง ทำ

  • ถ้า grid[row, c] =num ให้คืนค่า true

• คืนค่าเท็จมิฉะนั้น

• กำหนดวิธีการที่เรียกว่า isPresentInBox() ซึ่งจะใช้ boxStartRow, boxStartCol, num

• สำหรับแต่ละแถว r ใน boxStartRow ถึง 3 แถวถัดไป ทำ

  • สำหรับแต่ละ col r ใน boxStartCol ไปยัง 3 คอลัมน์ถัดไป ทำ

    • ถ้า grid[r, c] =num ให้คืนค่า true

• คืนค่าเท็จมิฉะนั้น

• กำหนดวิธีการที่เรียกว่า findEmptyPlace() ซึ่งจะใช้แถวและคอลัมน์

• สำหรับแต่ละแถว r ในตาราง ทำ

  • สำหรับแต่ละคอลัมน์ c ในตาราง ทำ

    • ถ้า grid[r, c] =0 ให้คืนค่า true

• คืนค่าเท็จ

• กำหนดวิธีการที่เรียกว่า isValidPlace() ซึ่งจะใช้แถว, col, num

• ถ้า isPresentInRow(row, num) และ isPresentInCol(col, num) and isPresntInBox(row – row mod 3, col – col mod 3, num) ทั้งหมดเป็นเท็จ แล้วคืนค่า true

• กำหนดวิธีการที่เรียกว่าแก้ปัญหาซูโดกุ() ซึ่งจะใช้กริด

• หากไม่มีที่ว่างในกริดให้คืนค่าเป็น จริง

• สำหรับหมายเลข 1 ถึง 9 ทำ

  • ถ้า isValidPlace(แถว, คอลัมน์, ตัวเลข) แล้ว

    • grid[row, col] :=จำนวน

    • ถ้าแก้ปัญหาซูโดกุ =จริง ให้คืนค่าจริง

    • grid[row, col] :=0

• คืนค่าเท็จ

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include #define N 9using เนมสเปซ std;int grid[N][N] ={ {3, 0, 6, 5, 0, 8, 4, 0, 0}, {5, 2, 0, 0, 0, 0, 0, 0, 0}, {0, 8, 7, 0, 0, 0, 0, 3, 1}, {0, 0, 3, 0, 1, 0, 0, 8, 0}, {9, 0, 0, 8, 6, 3, 0, 0, 5}, {0, 5, 0, 0, 9, 0, 6, 0, 0}, {1, 3, 0, 0, 0, 0, 2, 5, 0}, {0, 0, 0, 0, 0, 0, 0, 7, 4}, {0, 0, 5, 2, 0, 6, 3, 0, 0}};bool isPresentInCol(int col, int num){ //ตรวจสอบว่ามี num อยู่ใน col หรือไม่สำหรับ (int row =0; row  
อินพุต
 <ก่อนหน้า>{3, 0, 6, 5, 0, 8, 4, 0, 0},{5, 2, 0, 0, 0, 0, 0, 0, 0},{0, 8, 7, 0, 0, 0, 0, 3, 1},{0, 0, 3, 0, 1, 0, 0, 8, 0}, {9, 0, 0, 8, 6, 3, 0, 0, 5},{0, 5, 0, 0, 9, 0, 6, 0, 0},{1, 3, 0, 0, 0, 0, 2, 5, 0},{0, 0, 0, 0, 0, 0, 0, 7, 4},{0, 0, 5, 2, 0, 6, 3, 0, 0}

ผลลัพธ์

3 1 6 | 5 7 8 | 4 9 25 2 9 | 1 3 4 | 7 6 84 8 7 | 6 2 9 | 5 3 1---------------------------2 6 3 | 4 1 5 | 9 8 79 7 4 | 8 6 3 | 1 2 58 5 1 | 7 9 2 | 6 4 3---------------------------1 3 8 | 9 4 7 | 2 5 66 9 2 | 3 5 1 | 8 7 47 4 5 | 2 8 6 | 3 1 9